Algorithms for Reduced Ordered Binary Decision Diagrams

Julius Michaelis, Maximilian P. L. Haslbeck, Peter Lammich and Lars Hupel

27 April 2016

Abstract

We present a verified and executable implementation of ROBDDs in Isabelle/HOL. Our implementation relates pointer-based computation in the Heap monad to operations on an abstract definition of boolean functions. Internally, we implemented the if-then-else combinator in a recursive fashion, following the Shannon decomposition of the argument functions. The implementation mixes and adapts known techniques and is built with efficiency in mind.
BSD License

Depends On

Topics

Related Entries

Theories