On the size of binary decision diagrams representing Boolean functions

DOI10.1016/0304-3975(94)00181-HzbMath0874.68283OpenAlexW2054195481MaRDI QIDQ673087

Harry B. III Hunt, Yuri Breitbart, Daniel J. Rosenkrantz

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)00181-h

zbMATH Keywords

Boolean functionsbinary decision diagramsbranching programs

Mathematics Subject Classification ID

Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence (68T35)

Related Items

On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs, Ordered binary decision diagrams and the Shannon effect, Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs, Efficient data structures for Boolean functions, Lower bounds on the OBDD size of two fundamental functions' graphs, On the OBDD representation of some graph classes, Randomization and nondeterminism are comparable for ordered read-once branching programs, On symbolic OBDD-based algorithms for the minimum spanning tree problem, On efficient implicit OBDD-based algorithms for maximal matchings, Graph driven BDDs -- a new data structure for Boolean functions, Symbolic topological sorting with OBDDs, Representation of graphs by OBDDs, On the OBDD size for graphs of bounded tree- and clique-width, On the relative succinctness of sentential decision diagrams, A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs, Bounds on the OBDD-size of integer multiplication via universal hashing, On the descriptive and algorithmic power of parity ordered binary decision diagrams, On the evolution of the worst-case OBDD size, Lower bounds for linearly transformed OBDDs and FBDDs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial size \(\Omega\)-branching programs and their computational power
• Time-space trade-offs for branching programs
• Functional test generation using binary decision diagrams
• A lower bound for read-once-only branching programs
• Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits
• Lower bounds for depth-restricted branching programs
• Some bounds on the complexity of predicate recognition by finite automata
• Bounds for Width Two Branching Programs
• Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
• Graph-Based Algorithms for Boolean Function Manipulation
• On the complexity of branching programs and decision trees for clique functions
• Binary decision tree test functions
• Binary Decision Diagrams
• Finding the optimal variable ordering for binary decision diagrams