Representation of Boolean Functions
Czech version
The course is organized by
Department of Theoretical Computer Science and Mathematical Logic
of the Faculty of Mathematics and Physics, Charles University in Prague.
Annotation
The models for representation of Boolean functions are discussed,
namely Boolean circuits and formulas, DNF, CNF, decision trees
and different types of binary decision diagrams. Some of the models
may be used as a data structure for algorithms, which perform
operations on the Boolean functions. We will be mainly interested
in the proofs of some of the known results, which compare the
expressive power of the models.
Synopsis
- Partial input, subcube, monomial, DNF, implicant, primary implicant.
- Clause, CNF, implicate, prime implicate.
- Dual function, monotone, self-dual and linear funciotns.
- Boolean formulas, circuits.
- Binary decision tree, binary decision diagrams (BDD), read-once BDD, OBDD.
- Diagram of mutual relationships between the studied models, proofs of embeddings in it.
- The maximum complexity of representing functions using circuits and binary decision diagrams.
- Bounds on the complexity of functions in DNF, CNF, decision trees.
- Bounds on the complexity of OBDD and read-once BDD.
- Diagram of mutual relationships between the studied models, proofs of strict inclusions and incomparabilitites.
- Operations with functions represented by OBDD.
- The relationship between the depth and size of a decision tree and the complexity
of the function expressed by both DNF and CNF.
- Operations with functions represented using decision trees.
- Nonuniform Turing machine, relationship to Boolean models, Karp-Lipton theorem.
- Probabilistic non-equivalence test for read-once decision diagrams.
- BPP is contained in P/poly, so is representable by polynomial size circuits.
- Lower bounds for decision trees using Fourier transform of the Boolean functions.
Bibliography
I. Wegener.
Branching Programs and Binary Decision Diagrams - Theory and Applications.
SIAM Monographs on Discrete Mathematics and Applications, 2000.