On the complexity of the hidden weighted bit function for various BDD models
Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener (1999)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener (1999)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Matthias Krause (1992)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Beate Bollig (2001)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Branching programs are a well established computation model for Boolean functions, especially read-once branching programs have been studied intensively. In this paper the expressive power of nondeterministic read-once branching programs, more precisely the class of functions representable in polynomial size, is investigated. For that reason two restricted models of nondeterministic read-once branching programs are defined and a lower bound method is presented. Furthermore, the first...
Wilsin Gosti, Tiziano Villa, Alex Saldanha, Alberto Sangiovanni-Vincentelli (2007)
International Journal of Applied Mathematics and Computer Science
Similarity:
We address the problem of encoding the state variables of a finite state machine such that the BDD representing the next state function and the output function has the minimum number of nodes. We present an exact algorithm to solve this problem when only the present state variables are encoded. We provide results on MCNC benchmark circuits.
Stasys Jukna (1995)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Dejan Mančev, Branimir Todorović (2014)
International Journal of Applied Mathematics and Computer Science
Similarity:
Dejan Mančev, Branimir Todorović (2014)
International Journal of Applied Mathematics and Computer Science
Similarity:
Patrick Bellot, Djamil Sarni (1988)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Henrik Brosenne, Matthias Homeister, Stephan Waack (2002)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the complexity of Boolean functions represented by well-structured graph-driven parity-FBDDs in terms of invariants of the function represented and the graph-ordering used. As a consequence, we derive a lower bound criterion and prove an exponential lower bound for certain linear...