On the Use of Nondeterminism in BDD Models
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.
(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 M. Loebbing, D. Sieling): Parity OBDDs cannot be handled efficiently enough.
Other PapersAvailable at this URL (poseidon.informatik.uni-dortmund.de/~wegener/schriftv.html)
|You are not logged in|
|©2002-2018 U.C. Regents|