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

DOI10.1016/S0020-0190(98)00065-9zbMATH Open1078.68642MaRDI QIDQ2583554FDOQ2583554

Ayumi Shinohara, Kouichi Hirata, Shinichi Shimozono

Publication date: 17 January 2006

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

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

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)

Cites Work

• Title not available (Why is that?)
• Occam's razor
• Computational limitations on learning from examples
• Title not available (Why is that?)
• 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
• On Approximate Solutions for Combinatorial Optimization Problems
• On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs
• The minimum consistent DFA problem cannot be approximated within any polynomial
• Lower bounds on learning decision lists and trees
• On the hardness of approximating the minimum consistent OBDD problem
• Hardness of indentifying the minimum ordered binary decision diagram

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)