A Boolean function $f: \{0, 1\}^n \rightarrow \{0, 1\}$ admits a canonical graphical representation in terms of a reduced ordered binary decision diagram (ROBDDs or BDDs for short). There are other variants and derivatives such as zero-suppressed BDDs, algebraic and multi-terminal decision diagrams, as well as propositional DAGs.

The lattice or Boolean-algebraic structure of the set $\{0, 1\}^n$ might also serve as a foundation for a (not necessarily efficient) graphical representation of functions $f: \{0, 1\}^n \rightarrow \{0, 1\}$.

I just need to know about other graphical (or lattice-based) representations of Boolean functions (or, more generally, functions into finite sets) that may be less popular than BDDs, possibly because they turned out to be inefficient or because they apply only to restricted families of functions (e.g., isotone or linearly separable functions), etc.

The literature of these graphical representations (and their applications) is vast and it is really hard (but still very useful) to know about less popular ones (at least to avoid their pitfalls).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.