Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs

DOI10.1051/ITA:2002011MaRDI QIDQ4800256zbMATH OpenOpenAlexFDO

Authors Henrik Brosenne, Matthias Homeister, Stephan Waack

Publication date 15 July 2003

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=ITA_2002__36_3_229_0, http://www.numdam.org/item?id=ITA_2002__36_3_229_0/, https://eudml.org/doc/92699

zbMATH Keywords

polynomial time algorithm

Mathematics Subject Classification ID

Data structures (68P05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• scientific article; zbMATH DE number 1834649
• On the size of binary decision diagrams representing Boolean functions
• scientific article; zbMATH DE number 1759434
• On the descriptive and algorithmic power of parity ordered binary decision diagrams
• Graph driven BDDs -- a new data structure for Boolean functions

Cites work

• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 512863 (Why is no real title available?)
• scientific article; zbMATH DE number 1500660 (Why is no real title available?)
• scientific article; zbMATH DE number 1834649 (Why is no real title available?)
• Branching Programs and Binary Decision Diagrams
• Entropy of contact circuits and lower bounds on their complexity
• Graph driven BDDs -- a new data structure for Boolean functions
• Graph-Based Algorithms for Boolean Function Manipulation
• Linear codes are hard for oblivious read-once parity branching programs
• Matrix multiplication via arithmetic progressions
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• On the descriptive and algorithmic power of parity ordered binary decision diagrams
• On the size of binary decision diagrams representing Boolean functions
• Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication

Cited in

(3)

• scientific article; zbMATH DE number 1834649 (Why is no real title available?)
• Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
• scientific article; zbMATH DE number 1418344 (Why is no real title available?)

This page was built for publication: Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4800256)