The minimum consistent DFA problem cannot be approximated within any polynomial

摘要

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 not=NP, it is shown that for any constant k, no polynomial-time algorithm can be guaranteed to find a consistent DFA of size opt/sup k/, 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.