Hardness of indentifying the minimum ordered binary decision diagram

DOI10.1016/S0166-218X(99)00226-7zbMath0965.68076MaRDI QIDQ1841888

Shuzo Yajima, Yasuhiko Takenaga

Publication date: 29 July 2001

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

ordered binary decision diagram

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Boolean functions (06E30)

Related Items

The complexity of minimizing and learning OBDDs and FBDDs ⋮ On the hardness of approximating the minimum consistent acyclic DFA and decision diagram.

Cites Work

• Unnamed Item
• Unnamed Item
• A theory of the learnable
• Graph-Based Algorithms for Boolean Function Manipulation
• Computational limitations on learning from examples
• Binary Decision Diagrams
• Improving the variable ordering of OBDDs is NP-complete
• On the hardness of approximating the minimum consistent OBDD problem