@inproceedings{a2202933cd684247bed886c66d4078b9,

title = "Minimum consistent DFA problem cannot be approximated within any polynomial",

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.",

author = "Leonard Pitt and Warmuth, {Manfred K.}",

year = "1989",

doi = "10.1145/73007.73048",

language = "English (US)",

isbn = "0897913078",

series = "Proc Twenty First Annu ACM Symp Theory Comput",

publisher = "Publ by ACM",

pages = "421--432",

booktitle = "Proc Twenty First Annu ACM Symp Theory Comput",

note = "Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing ; Conference date: 15-05-1989 Through 17-05-1989",

}