The minimum consistent DFA problem cannot be approximated within any polynomial

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-&egr;)log logopt is shown for any &egr; > 0.

REFERENCES

• 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.
• 2: Dana Charmian Angluin, An application of the theory of computational complexity to the study of inductive inference., 1976
• 3: Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
• 4: Dana Angluin, Negative Results for Equivalence Queries, Machine Learning, v.5 n.2, p.121-150, Jun. 1990 [doi>10.1023/A:1022692615781]
• 5: ~ANGLUIN, D. On the complexity of minimum inference of regular sets. blf Cont. 39, 3 ~(1978), 337-350.
• 6: Alselm Blumer , Andrzej Ehrenfeucht , David Haussler , Manfred K. Warmuth, Occam's razor, Information Processing Letters, v.24 n.6, p.377-380, 6 April 1987 [doi>10.1016/0020-0190(87)90114-1]
• 7: Raymond Board , Leonard Pitt, On the necessity of Occam algorithms, Theoretical Computer Science, v.100 n.1, p.157-184, June 22, 1992 [doi>10.1016/0304-3975(92)90367-O]
• 8: ~F_,HRENFEUCHT, A., AND ZEIGER, P. Complexity measures for regular expressions. J. Compztt. ~Syst. Sci. 12, 2 (1976), 134-146.
• 9: M. R. Garey , D. S. Johnson, The Complexity of Near-Optimal Graph Coloring, Journal of the ACM (JACM), v.23 n.1, p.43-49, Jan. 1976 [doi>10.1145/321921.321926]
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: ~GOLD, E.M. Complexity of automaton identification from given data. bzf Control 37 (1978), ~302-320.
• 12: ~HANCOCK, T. On the difficulty of finding small consistent decision trees. Unpublished ~manuscript, Aiken Computation Laboratory, Harvard Univ., Cambridge, Mass., 1989.
• 13: David Haussler , Michael Kearns, Equivalence of models for polynomial learnability, Information and Computation, v.95 n.2, p.129-161, Dec. 1991 [doi>10.1016/0890-5401(91)90042-Z]
• 14: David Helmbold , Robert Sloan , Manfred K. Warmuth, Learning integer lattices, SIAM Journal on Computing, v.21 n.2, p.240-266, April 1992 [doi>10.1137/0221019]
• 15: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 16: M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
• 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.
• 18: Ming Li , Umest Vazirani, On the learnability of finite automata, Proceedings of the first annual workshop on Computational learning theory, p.359-370, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 19: ~NIVEN, I., AND ZUCKERMAN, H. S. ,/L*z Introduction to the Theory of Nurnhelx. Wiley. New ~York, 1972.
• 20: A. Panconesi , D. Ranjan, Quantifiers and approximation, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.446-456, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100275]
• 21: Christos Papadimitriou , Mihalis Yannakakis, Optimization, approximation, and complexity classes, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.229-234, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62233]
• 22: Leonard Pitt , Leslie G. Valiant, Computational limitations on learning from examples, Journal of the ACM (JACM), v.35 n.4, p.965-984, Oct. 1988 [doi>10.1145/48014.63140]
• 23: Thomas J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing, p.216-226, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804350]
• 24: ~TRAKHTENBROT, 13. A., AND BARZDIN, YA. M. Finite Automata. North-Holland, Amsterdam, ~1973, pp. 98-99.
• 25: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Decision problems

General Terms:
Algorithms, Languages, Theory

Keywords:
approximation algorithms, minimization of finite state machines, nonapproximability