On the hardness of approximating the minimum consistent acyclic DFA and decision diagram.

DOI10.1016/S0020-0190(98)00065-9zbMath1078.68642MaRDI QIDQ2583554

Ayumi Shinohara, Kouichi Hirata, Shinichi Shimozono

Publication date: 17 January 2006

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

zbMATH Keywords

Computational complexityData structuresApproximationCombinatorial problemsFinite state machine minimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Cites Work

• Occam's razor
• On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs
• Hardness of indentifying the minimum ordered binary decision diagram
• On Approximate Solutions for Combinatorial Optimization Problems
• 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
• Improving the variable ordering of OBDDs is NP-complete
• Lower bounds on learning decision lists and trees
• On the hardness of approximating the minimum consistent OBDD problem
• Unnamed Item
• Unnamed Item

This page was built for publication: On the hardness of approximating the minimum consistent acyclic DFA and decision diagram.