The minimum consistent DFA problem cannot be approximated within and 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 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 described for the problem of funding small consistent linear grammars.

REFERENCES

• 1: Dana Charmian Angluin, An application of the theory of computational complexity to the study of inductive inference., 1976
• 2: D. Anghdn. Negative Results for Equivalence Queries. Technical Report YALEU/DCS/RR-648, Department of Computer Science, Yale University, September 1988.
• 3: D. Angluln. On the complexity of mlnJmum inference of regular sets. inform. Contr., 39(3):337-350, 1978.
• 4: D. Angluln. Private commlxaication. 1988.
• 5: 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]
• 6: 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]
• 7: 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
• 8: E. M. Gold. Complexity of automaton identification from given data. Inform. Contr., 37:302-320, 1978.
• 9: T. Hancock. Finding the smallest consistent decision tree is NP-hard. 1989. Unpublished manuscript, Hatyard University.
• 10: David Haussler , Michael Kearns , Nick Littlestone , Manfred K. Warmuth, Equivalence of models for polynomial learnability, Proceedings of the first annual workshop on Computational learning theory, p.42-55, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 11: D. Helmbold, R. Sloan, and Manfred K. Warmuth. Bootstrapping One-sided Learning. 1988. Extended abstract, Dept. of Computer and Information Sciences, University of California at Santa Cruz.
• 12: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 13: 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]
• 14: 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
• 15: 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]
• 16: 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]
• 17: L. Pitt and M. K. Warmuth. The Minimum Consistent DFA Problem Cannot be Approximated within any Polynomial. Teclmical Report UIUCDCS-R-89-1499, University of Illinois at Urbana-Champaign, February 1989.
• 18: 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]
• 19: B. A. Trakhtenbrot and Ya. M. Barzdin. Finite Automata. North-Holland, Amsterdam, 1973. pp. 98-99.
• 20: 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.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Algebraic language theory

Additional 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)
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Algorithms, Theory