The size of reduced OBDD's and optimal read-once branching programs for almost all Boolean functions

DOI10.1109/12.324559MaRDI QIDQ4419798zbMATH OpenOpenAlexFDO

Authors Ingo Wegener

Publication date 16 October 2003

Published in IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/12.324559

Mathematics Subject Classification ID

Boolean functions (06E30) Analysis of algorithms and problem complexity (68Q25) Boolean functions (94D10)

Recommendations

• On the size of binary decision diagrams representing Boolean functions
• scientific article; zbMATH DE number 1948534
• On random orderings of variables for parity ordered binary decision diagrams
• Optimal ordered binary decision diagrams for read-once formulas
• Variable orderings and the size of OBDDs for random partially symmetric Boolean functions

Cited in

(15)

• Efficient data structures for Boolean functions
• Optimal ordered binary decision diagrams for read-once formulas
• On the evolution of the worst-case OBDD size
• Randomized OBDD-based graph algorithms
• On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs
• Ordered binary decision diagrams and the Shannon effect
• On the use of binary decision diagrams for solving problems on simple games
• Better upper bounds on the QOBDD size of integer multiplication
• Single-faced Boolean functions and their minimization
• A fast symbolic transformation based algorithm for reversible logic synthesis
• Randomized OBDD-based graph algorithms
• On the minimization of (complete) ordered binary decision diagrams
• Size of OBDD representation of 2-level redundancies functions
• The size of reduced OBDDs and optimal read-once branching programs for almost all Boolean functions
• Forms of representation for simple games: sizes, conversions and equivalences

This page was built for publication: The size of reduced OBDD's and optimal read-once branching programs for almost all Boolean functions

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