On the hardness of approximating the minimum consistent OBDD problem

DOI10.1007/3-540-61422-2_125zbMath1502.68133OpenAlexW1582081218MaRDI QIDQ5054808

Kouichi Hirata, Ayumi Shinohara, Shinichi Shimozono

Publication date: 9 December 2022

Published in: Algorithm Theory — SWAT'96 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61422-2_125

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (2)

Hardness of indentifying the minimum ordered binary decision diagram ⋮ On the hardness of approximating the minimum consistent acyclic DFA and decision diagram.

Cites Work

• Unnamed Item
• Learning regular sets from queries and counterexamples
• On the necessity of Occam algorithms
• Reduction of OBDDs in linear time
• Lower bounds on learning decision lists and trees
• Queries and concept learning
• A theory of the learnable
• Computational limitations on learning from examples
• The minimum consistent DFA problem cannot be approximated within any polynomial
• Complexity of automaton identification from given data
• On the complexity of minimum inference of regular sets
• New approximation algorithms for graph coloring
• On the hardness of approximating minimization problems

This page was built for publication: On the hardness of approximating the minimum consistent OBDD problem