The Minimum Consistent DFA Problem Cannot be Approximated Within any Polynomial

Leonard Pitt, Manfred K. Warmuth

Research output: Contribution to journalArticlepeer-review

Abstract

The minimum consistent DFA problem is that of finding a DFA with as few states as possible that is consistent with a given sample 1993. Assuming that P ≠ NP, it is shown that for any constant k, no polynomial-time algorithm can be guaranteed to find a consistent DFA with fewer than optk states, where opt is the number of states in the minimum state DFA consistent with the sample. This result holds even if the alphabet is of constant size two, and if the algorithm is allowed to produce an NFA, a regular expression, or a regular grammar that is consistent with the sample. A similar nonapproximability result is presented for the problem of finding small consistent linear grammars. For the case of finding minimum consistent DFAs when the alphabet is not of constant size but instead is allowed to vary with the problem specification, the slightly stronger lower bound on approximability of opt(1-ε)log logopt is shown for any ε > 0.

Original languageEnglish (US)
Pages (from-to)95-142
Number of pages48
JournalJournal of the ACM (JACM)
Volume40
Issue number1
DOIs
StatePublished - Feb 1 1993

Keywords

  • approximation algorithms
  • minimization of finite state machines
  • nonapproximability

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'The Minimum Consistent DFA Problem Cannot be Approximated Within any Polynomial'. Together they form a unique fingerprint.

Cite this