Minimum consistent DFA problem cannot be approximated within any polynomial

Leonard Pitt, Manfred K. Warmuth

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The minimum consistent DFA (deterministic finite automaton) problem is that of finding a DFA with as few states as possible that is consistent with a given sample (a finite collection of words, each labeled as to whether the DFA found should accept or reject). Assuming that P ≠ NP, it is shown that for any constant k, no polynomial time algorithm can be guaranteed to find a consistent DFA of size optk, where opt is the size of a smallest 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 grammar, or a regular expression that is consistent with the sample. Similar hardness results are described for the problem of finding small consistent linear grammars.

Original languageEnglish (US)
Title of host publicationProc Twenty First Annu ACM Symp Theory Comput
PublisherPubl by ACM
Pages421-432
Number of pages12
ISBN (Print)0897913078
StatePublished - Dec 1 1989
EventProceedings of the Twenty First Annual ACM Symposium on Theory of Computing - Seattle, WA, USA
Duration: May 15 1989May 17 1989

Publication series

NameProc Twenty First Annu ACM Symp Theory Comput

Other

OtherProceedings of the Twenty First Annual ACM Symposium on Theory of Computing
CitySeattle, WA, USA
Period5/15/895/17/89

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint

Dive into the research topics of 'Minimum consistent DFA problem cannot be approximated within any polynomial'. Together they form a unique fingerprint.

Cite this