TY - GEN

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

AU - Pitt, Leonard B

AU - Warmuth, Manfred K.

PY - 1989/12/1

Y1 - 1989/12/1

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

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

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

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

M3 - Conference contribution

AN - SCOPUS:0024900507

SN - 0818619589

T3 - Proc Struct Complexity Theor Fourth Ann Conf

BT - Proc Struct Complexity Theor Fourth Ann Conf

A2 - Anon, null

PB - Publ by IEEE

T2 - Proceedings: Structure in Complexity Theory - Fourth Annual Conference

Y2 - 19 June 1989 through 22 June 1989

ER -