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

DOI10.1016/S0020-0190(98)00065-9MaRDI QIDQ2583554zbMATH OpenFDO

Authors Shinichi Shimozono, Kouichi Hirata, Ayumi Shinohara

Publication date 17 January 2006

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

zbMATH Keywords

ApproximationComputational complexityData structuresCombinatorial problemsFinite state machine minimization

Mathematics Subject Classification ID

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

Recommendations

• The minimum consistent DFA problem cannot be approximated within any polynomial
• Minimal consistent DFA revisited
• On the hardness of approximating the minimum consistent OBDD problem
• Minimizing nfa's and regular expressions
• STACS 2005

Cites work

• scientific article; zbMATH DE number 3427224 (Why is no real title available?)
• scientific article; zbMATH DE number 1306875 (Why is no real title available?)
• Complexity of automaton identification from given data
• Computational limitations on learning from examples
• Hardness of indentifying the minimum ordered binary decision diagram
• Improving the variable ordering of OBDDs is NP-complete
• Lower bounds on learning decision lists and trees
• Occam's razor
• On Approximate Solutions for Combinatorial Optimization Problems
• On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs
• On the complexity of minimum inference of regular sets
• On the hardness of approximating the minimum consistent OBDD problem
• The minimum consistent DFA problem cannot be approximated within any polynomial

Cited in

(4)

• Hardness of indentifying the minimum ordered binary decision diagram
• On the hardness of approximating the minimum consistent OBDD problem
• A new algorithm for the construction of minimal acyclic DFAs.
• The minimum consistent DFA problem cannot be approximated within any polynomial

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

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