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, 9780897913072
    DOIs
    StatePublished - 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

    • General Engineering

    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