Leonard Pitt
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 optk 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 logopt is shown for any ϵ > 0.
- 1 ~ABE, N. Learning commutative deterministic finite state automata in polynomial time. In ~Proceedings of the 1st International Workshop on Algorithmic Learning Theot3,, Japanese Society ~for Artificial Intelligence, Tokyo, Japan, 1990, pp. 223-235.Google Scholar
- 2 ~ANGLUIN, D. An application of the theory of computational complexity to the study of ~inductive inference. Ph.D. dissertation, Electrical Engineering and Computer Science Depart- ~ment, University of California at Berkeley, Berkeley, Calif., 1976. Google Scholar
- 3 ~ANGLU1N, D. Learning regular sets from queries and counterexamplcs, lnf Comput. 75, 2 ~(1987), 87-106. Google Scholar
- 4 ~ANGLUIN, D. Negative results for equivalence queries. Mach. Learn. 5, 2 (1990), t21-150. Google Scholar
- 5 ~ANGLUIN, D. On the complexity of minimum inference of regular sets. blf Cont. 39, 3 ~(1978), 337-350.Google Scholar
- 6 ~BLUMER, A.? EHRENFEUCHT, A., HAUSSLER, D., AND WARMUTH, M. Occam's razor, bzf Proc. ~Lett. 24 (1987), 377-380. Google Scholar
- 7 ~BOARD, R., AND PITI', L. On the necessity of Occam algorithms. Theoret. Comput. Set. 100 ~(1992), 157-184. Google Scholar
- 8 ~F_,HRENFEUCHT, A., AND ZEIGER, P. Complexity measures for regular expressions. J. Compztt. ~Syst. Sci. 12, 2 (1976), 134-146.Google Scholar
- 9 ~GAREY, M., AND JOHNSON, D. The complexity of near-optimal graph coloring. J AC3,1 23, 1 ~(June 1976), 43 49. Google Scholar
- 10 ~GAREY, M., AND JOHNSON, D. Computers and bztractability: A Guide to tile Theon' of ~NP-completeness. W. H. Freeman, San Francisco, Calif., 1979. Google Scholar
- 11 ~GOLD, E.M. Complexity of automaton identification from given data. bzf Control 37 (1978), ~302-320.Google Scholar
- 12 ~HANCOCK, T. On the difficulty of finding small consistent decision trees. Unpublished ~manuscript, Aiken Computation Laboratory, Harvard Univ., Cambridge, Mass., 1989.Google Scholar
- 13 ~HAUSSLER, D., KEARNS, M., LITTLESTONE, N., AND WARMUTH, M.K. Equivalence of models ~for polynomial learnability. Inf. Comlmt. 95 (1991), 129-16l. Google Scholar
- 14 ~HELMBOLD, D., SLOAN, R., AND WARMUTH, M.K. Learning integer lattices. SIAM J. Cornput. ~21, 2 (1992), 240-266. Google Scholar
- 15 ~HOPCROFT, J. E., AND ULLMAN, J. D. Introduction to Automata Theory, Languages, and ~Computation. Addison-Wesley, Reading, Mass., 1979. Google Scholar
- 16 ~KEARNS, M., AND VALIANT, L.G. Cryptographic limitations on learning Boolean formulae ~and finite automata. In Proceedings of the 21st Ammal ACM Symposium on Theory of ~Computing (Seattle, Wash., May 15-17). ACM, New York, 1989, pp. 433-444. Google Scholar
- 17 ~KOLAmS, PH. G., AND THAKUR, M. N. Approximation properties of NP minimization ~problems. In Proceedmgs of the 6th Anmtal IEEE Conference on Structure in Complexi.O' Theoly. ~IEEE Computer Society Press, Washington, D.C., 1991, pp. 353-366.Google Scholar
- 18 ~LI, M., AND VAZIRANI, U. On the learnability of finite automata. In Proceedings of the 1988 ~Workshop on Computational Learning Theon/. Morgan-Kaufmann, San Mateo, Calif., 1988, pp. ~359-370. Google Scholar
- 19 ~NIVEN, I., AND ZUCKERMAN, H. S. ,/L*z Introduction to the Theory of Nurnhelx. Wiley. New ~York, 1972.Google Scholar
- 20 ~PANCONESl, A., AND RAN JAN, D. Quantifiers and approximation. In Proceedings of the 22nd ~Annual ACM Symposium on Theory of' Computing, (Baltimore, Md., May 14-16). ACM, New ~York, 1990, pp. 446 456. Google Scholar
- 21 ~PAPADIMITRIOU, C. H., AND YANNAKAKIS, M. Optimization, approximation, and complexity ~classes. In Proceedings of the 20th Annual A CM Symposium on Theoo' of Computing (Chicago, ~II1., May 2 4). ACM, New York, 1988, pp. 229-234. Google Scholar
- 22 ~PITT, L., AND VALIANT, L.G. Computational limitations on learning from examples. J. ACM ~35, 4 (Oct. 1988), 965-984. Google Scholar
- 23 ~SCHAEFER, T.J. The complexity of satisfiability problems. In Proceedings of the }Oth Annual ~ACM Symposium on Theoly of Computing (San Diego, Calif., May I 3). ACM, New York, ~1978, pp. 216-226. Google Scholar
- 24 ~TRAKHTENBROT, 13. A., AND BARZDIN, YA. M. Finite Automata. North-Holland, Amsterdam, ~1973, pp. 98-99.Google Scholar
- 25 ~VALIANT, L. a. A theory of the learnable. Commun. A CM 27, 1l (Nov 1984), 1134-1142. Google Scholar
Index Terms
- The minimum consistent DFA problem cannot be approximated within any polynomial
Recommendations
The minimum consistent DFA problem cannot be approximated within and polynomial
STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computingThe 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 ...
Synchronization of some DFA
TAMC'07: Proceedings of the 4th international conference on Theory and applications of models of computationAword w is called synchronizing (recurrent, reset, directable) word of deterministic finite automaton (DFA) if w brings all states of the automaton to an unique state. Černy conjectured in 1964 that every n- state synchronizable automaton possesses a ...
Free bits, PCPs and non-approximability-towards tight results
FOCS '95: Proceedings of the 36th Annual Symposium on Foundations of Computer ScienceThe first part of this paper presents new proof systems and improved non-approximability results. In particular we present a proof system for NP using logarithmic randomness and two amortized free bits, so that Max clique is hard within N/sup 1/3/ and ...
Comments