On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs

DOI10.1016/0020-0190(94)00048-4zbMath0803.68049OpenAlexW1972591946MaRDI QIDQ1330665

Christoph Meinel, Jordan Gergov

Publication date: 21 July 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00048-4

zbMATH Keywords

Boolean functionsdata structuresCADbranching programsefficient algorithmsBDDdecision graphsBoolean manipulationcomputer-aided circuit designcomputer-aided logic synthesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Computer science aspects of computer-aided design (68U07)

Related Items

Learning ordered binary decision diagrams, On the hardness of approximating the minimum consistent acyclic DFA and decision diagram.

Cites Work

• On the size of binary decision diagrams representing Boolean functions
• Equivalence of free Boolean graphs can be decided probabilistically in polynomial time
• Modified branching programs and their computational power
• Graph-Based Algorithms for Boolean Function Manipulation
• Binary Decision Diagrams
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item