Minimum consistent DFA problem cannot be approximated within any polynomial

Leonard B Pitt, Manfred K. Warmuth

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

Abstract

Summary form only given, as follows. The minimum consistent DFA 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 presented for the problem of finding small consistent linear grammars.

Original languageEnglish (US)
Title of host publicationProc Struct Complexity Theor Fourth Ann Conf
Editors Anon
PublisherPubl by IEEE
Number of pages1
ISBN (Print)0818619589
StatePublished - Dec 1 1989
EventProceedings: Structure in Complexity Theory - Fourth Annual Conference - Eugene, OR, USA
Duration: Jun 19 1989Jun 22 1989

Publication series

NameProc Struct Complexity Theor Fourth Ann Conf

Other

OtherProceedings: Structure in Complexity Theory - Fourth Annual Conference
CityEugene, OR, USA
Period6/19/896/22/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