Daniel Kral: Ordered binary decision diagrams (OBDDs) and parity order decision
binary diagrams have proved their importance as data structures representing
Boolean functions. In addition to parity OBDDs we study their generalization
which we call parity AOBDDs, give the algebraic characterization theorem
and compare their minimal size to the size of parity OBDDs.
We prove the existence of node-minimal parity (A)OBDDs without arcs
testing conditions x_i=0, and give an efficient algorithm for finding such
parity
(A)OBDDs. We define so-called uniqueness conditions, use them to obtain
a canonical form for parity OBDDs and discuss similar results for parity
AOBDDs.
Algorithms for minimalization and finding the form which satisfies
the uniqueness conditions for parity OBDDs running in time O(S^3) and for
parity AOBDDs running in time O(nS^3) are presented; both the algorithms
are quite simple.
All our results are also extended to the case of shared parity OBDDs
and shared parity AOBDDs - data structures for representation of Boolean
function sequences.
S. Žák: Branching programy s omezenou neurcitosti. Netradicni pohled na sekvencni pocitani. Nova metoda dolnich odhadu
pro obecne branching programy. Pokus o zachyceni pojmu "jednoducha" funkce.
Dolni meze.
Miklos Ajtai: Determinism versus Non-Determinism for Linear Time RAMs
with Memory Restrictions Electronic Colloquium on Computational Complexity, ECCC
Report TR98-077, 1998
Miklos Ajtai: A Non-linear Time Lower Bound for Boolean Branching
Programs Electronic Colloquium on Computational Complexity, ECCC
Report TR99-026, 1999
