The minimum consistent DFA problem cannot be approximated within any polynomial
Authors:
- Leonard PittLPLeonard Pitt
- Manfred K. WarmuthMWManfred K. Warmuth
Open Access
- 2 January 1993
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 40 (1) , 95-142
Abstract
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 with fewer than opt k states, where opt is the number of states in the minimum state 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 expression, or a regular grammar that is consistent with the sample. A similar nonapproximability result is presented for the problem of finding small consistent linear grammars. For the case of finding minimum consistent DFAs when the alphabet is not of constant size but instead is allowed to vary with the problem specification, the slightly stronger lower bound on approximability of opt (1-ϵ)log log opt is shown for any ϵ > 0.Keywords
This publication has 10 references indexed in Scilit:
- On the necessity of Occam algorithmsTheoretical Computer Science, 1992
- Learning Integer LatticesSIAM Journal on Computing, 1992
- Equivalence of models for polynomial learnabilityInformation and Computation, 1991
- Negative Results for Equivalence QueriesMachine Learning, 1990
- Computational limitations on learning from examplesJournal of the ACM, 1988
- Learning regular sets from queries and counterexamplesInformation and Computation, 1987
- A theory of the learnableCommunications of the ACM, 1984
- On the complexity of minimum inference of regular setsInformation and Control, 1978
- Complexity of automaton identification from given dataInformation and Control, 1978
- The Complexity of Near-Optimal Graph ColoringJournal of the ACM, 1976