On the Use of Nondeterminism in BDD Models

Abstract

Nondeterminism has the flavor of a purely theoretical concept. Nevertheless, it is well-known that nondeterministic finite automata can model practical aspects of systems. But nondeterminism also is useful in BDD models. Disjunctive normal forms (DNFs) are mainly nondeterministic decision trees. Ordered functional decision diagrams (OFDDs) allow the limited use of EXOR-nondeterminism. Parity OBDDs are a common generalization of OBDDs, OFDDs, and ordered Kronecker decision diagrams and allow the full power of EXOR-nondeterminism. The usual OR-nondeterminism is allowed in limited form in partitioned OBDDs. Partitioned OBDDs also allow the use of different variable orderings and one may argue why and how they allow the repetition of tests. The efficiency of these representations of Boolean functions is discussed as well as the limitations of these BDD models.

Relevant Papers

(with B. Bollig): Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams .

(with B. Bollig): Partitioned BDDs vs. other BDD models.

(with S. Jukna, A. Razborov, P. Savicky): On P versus NP\cap co-NP for decision trees and read-once branching programs.

(with B. Bollig): A very simple function that requires exponential size read-once branching programs.

(with M. Loebbing, D. Sieling): Parity OBDDs cannot be handled efficiently enough.

Other Papers