Geodesic
Characterizing the complexity of boolean functions represented by well-structured graph-driven parity-FBDDs
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 3, pp. 229-247

Voir la notice de l'article provenant de la source Numdam

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 code functions. The second main result of this paper is a polynomial time algorithm that minimizes the number of nodes in a graph-driven parity-FBDD.

DOI : 10.1051/ita:2002011
Classification : 68Q10, 68Q60, 68P05
Keywords: well-structured graph-driven parity-FBDDs, lower bounds, minimization algorithm, complexity theory, data structures for boolean functions 
@article{ITA_2002__36_3_229_0,
     author = {Brosenne, Henrik and Homeister, Matthias and Waack, Stephan},
     title = {Characterizing the complexity of boolean functions represented by well-structured graph-driven {parity-FBDDs}},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {229--247},
     publisher = {EDP-Sciences},
     volume = {36},
     number = {3},
     year = {2002},
     doi = {10.1051/ita:2002011},
     mrnumber = {1958241},
     zbl = {1032.68081},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2002011/}
}
TY  - JOUR
AU  - Brosenne, Henrik
AU  - Homeister, Matthias
AU  - Waack, Stephan
TI  - Characterizing the complexity of boolean functions represented by well-structured graph-driven parity-FBDDs
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2002
SP  - 229
EP  - 247
VL  - 36
IS  - 3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita:2002011/
DO  - 10.1051/ita:2002011
LA  - en
ID  - ITA_2002__36_3_229_0
ER  - 
%0 Journal Article
%A Brosenne, Henrik
%A Homeister, Matthias
%A Waack, Stephan
%T Characterizing the complexity of boolean functions represented by well-structured graph-driven parity-FBDDs
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2002
%P 229-247
%V 36
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita:2002011/
%R 10.1051/ita:2002011
%G en
%F ITA_2002__36_3_229_0
Brosenne, Henrik; Homeister, Matthias; Waack, Stephan. Characterizing the complexity of boolean functions represented by well-structured graph-driven parity-FBDDs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 3, pp. 229-247. doi: 10.1051/ita:2002011

Cité par Sources :