Article

Free access

The minimum consistent DFA problem cannot be approximated within and polynomial

Authors:

M. K. WarmuthAuthors Info & Claims

STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing

Pages 421 - 432

https://doi.org/10.1145/73007.73048

Published: 01 February 1989 Publication History

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 opt^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 described for the problem of funding small consistent linear grammars.

References

[1]

D. Angluin. An applicati~on of the theory of computational complexity to the study of inductive inference. 1976. Ph.D. Thesis, Electrical Engineering and Computer Science Departnlent, University of Callfornia, Berkeley.

Digital Library

[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]

A. Blumer, A. Ehrenfcucht, D. Haussler, and M. Warmuth. Occam's razor. Inform. Process. Letters, 24:377- 380, 1987.

Digital Library

[6]

M. Garey and D. Johnson. The complexity of nearoptimal graph'coloring. J. ACM, 23(1):43-49, 1976.

Digital Library

[7]

M. Garey and D. Johnson. Cornp~tev# and Ir~tractability: A Guide to the Theory of NP. completeness. W. H. Freeman, San Francisco, California, 1979.

Digital Library

[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]

D. Haussler, M. Kearns, N. Littlestone, and M. K. Warmuth. Equivalence of Models for Polynomial Learnability. In Proceedings of the 1st Workshop on Computational Learning Theory, Morgan Kaufrnann, San Mateo, CA, August 1988.

Digital Library

[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]

J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison- Wesley, Reading, Massachussetts, 1979.

Digital Library

[13]

M. Kearns and L. G. Valiant. Cryptographic limitations on learning Boolean formulae and finite automata. In Proceedings o.f the 21st Annual A CM Symposium on Theory of Computing, Assoc. Comp. Mach.~ New York, May 1989. Begins next page of these proceedings.

Digital Library

[14]

M. Li and U. Vazirani. On the learnability of finite automata. In Proceedings of the 1st Workshop on Computational Learning Theory, Morgan Kaufmann, San Mateo, California, August 1988.

Digital Library

[15]

C. H. Papadixnitriou and M. Yannakakis. Optimizatlon, approximation, and complexity classes. In Proceedings of the ~Oth Annual A CM Symposium on Theory of Computing, pages 229-234, Assoc. Comp. Mach., New York, May 1988.

Digital Library

[16]

L. Pitt and L. G. Valiant. Computational limitations on learning from examples. J. A C'M, 35(4):965-984, 1988.

Digital Library

[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]

T. J. Schaefer. The complexity of satis~ability problens. In Proceedings of the l Oth Annual A CM Symposium on Theory of Computing, pages 216-226, Assoc. Comp. Mach., New York, 1978.

Digital Library

[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. Comm. Assoc. Cornp. Mach., 27(11):1134-1142, 1984.

Digital Library

Cited By

Florêncio CVerwer S(2012)Regular inference as vertex coloringProceedings of the 23rd international conference on Algorithmic Learning Theory10.1007/978-3-642-34106-9_10(81-95)Online publication date: 29-Oct-2012
https://dl.acm.org/doi/10.1007/978-3-642-34106-9_10
H??gberg J(2011)A randomised inference algorithm for regular tree languagesNatural Language Engineering10.1017/S135132491100006417:2(203-219)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1017/S1351324911000064
Verwer SWeerdt MWitteveen C(2011)The efficiency of identifying timed automata and the power of clocksInformation and Computation10.1016/j.ic.2010.11.023209:3(606-625)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1016/j.ic.2010.11.023
Show More Cited By

Index Terms

The minimum consistent DFA problem cannot be approximated within and polynomial
1. Theory of computation
  1. Formal languages and automata theory
    1. Formalisms
      1. Algebraic language theory
      2. Rewrite systems
    2. Grammars and context-free languages

Recommendations

The minimum consistent DFA problem cannot be approximated within any polynomial

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 ...
Synchronization of some DFA
TAMC'07: Proceedings of the 4th international conference on Theory and applications of models of computation

Aword 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 ...
Minimal consistent DFA from sample strings
Abstract
We review the grammatical inference problem for regular languages which aims to generate a deterministic finite automaton from a representative set of training sample strings known to be in or not in the language. Although the general problem of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing

February 1989

600 pages

ISBN:0897913078

DOI:10.1145/73007

Editor:
D. S. Johnson

Copyright © 1989 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC89

Sponsor:

SIGACT

STOC89: 21st Annual ACM Symposium on the Theory of Computing

May 14 - 17, 1989

Washington, Seattle, USA

Acceptance Rates

STOC '89 Paper Acceptance Rate 56 of 196 submissions, 29%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
560
Total Downloads

Downloads (Last 12 months)66
Downloads (Last 6 weeks)9

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Florêncio CVerwer S(2012)Regular inference as vertex coloringProceedings of the 23rd international conference on Algorithmic Learning Theory10.1007/978-3-642-34106-9_10(81-95)Online publication date: 29-Oct-2012
https://dl.acm.org/doi/10.1007/978-3-642-34106-9_10
H??gberg J(2011)A randomised inference algorithm for regular tree languagesNatural Language Engineering10.1017/S135132491100006417:2(203-219)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1017/S1351324911000064
Verwer SWeerdt MWitteveen C(2011)The efficiency of identifying timed automata and the power of clocksInformation and Computation10.1016/j.ic.2010.11.023209:3(606-625)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1016/j.ic.2010.11.023
Gabel MSu ZHarrold MMurphy G(2008)JavertProceedings of the 16th ACM SIGSOFT International Symposium on Foundations of software engineering10.1145/1453101.1453150(339-349)Online publication date: 9-Nov-2008
https://dl.acm.org/doi/10.1145/1453101.1453150
Shahbaz M(2006)Incremental Inference of Black-Box Components to Support Integration TestingProceedings of the Testing: Academic & Industrial Conference on Practice And Research Techniques10.1109/TAIC-PART.2006.14(71-74)Online publication date: 29-Aug-2006
https://dl.acm.org/doi/10.1109/TAIC-PART.2006.14
Dupont PMiclet LVidal E(2005)What is the search space of the regular inference?Grammatical Inference and Applications10.1007/3-540-58473-0_134(25-37)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-58473-0_134
Rivest R(2005)Cryptography and machine learningAdvances in Cryptology — ASIACRYPT '9110.1007/3-540-57332-1_36(427-439)Online publication date: 28-May-2005
https://doi.org/10.1007/3-540-57332-1_36
Rivest RSchapire R(2005)Inference of finite automata using homing sequencesMachine Learning: From Theory to Applications10.1007/3-540-56483-7_22(51-73)Online publication date: 6-Jun-2005
https://doi.org/10.1007/3-540-56483-7_22
Kearns MValiant L(2005)Cryptographic limitations on learning Boolean formulae and finite automataMachine Learning: From Theory to Applications10.1007/3-540-56483-7_21(29-49)Online publication date: 6-Jun-2005
https://doi.org/10.1007/3-540-56483-7_21
Kinber E(2005)Learning a class of regular expressions via restricted subset queriesAnalogical and Inductive Inference10.1007/3-540-56004-1_16(232-243)Online publication date: 29-May-2005
https://doi.org/10.1007/3-540-56004-1_16
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents