TY - GEN

T1 - Minimum consistent DFA problem cannot be approximated within any polynomial

AU - Pitt, Leonard

AU - Warmuth, Manfred K.

PY - 1989/12/1

Y1 - 1989/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0024868429&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024868429&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0024868429

SN - 0897913078

T3 - Proc Twenty First Annu ACM Symp Theory Comput

SP - 421

EP - 432

BT - Proc Twenty First Annu ACM Symp Theory Comput

PB - Publ by ACM

T2 - Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing

Y2 - 15 May 1989 through 17 May 1989

ER -