Random DFA's can be approximately learned from sparse uniform examples

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Random DFA's can be approximately learned from sparse uniform examples

Full text

Pdf (857 KB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the fifth annual workshop on Computational learning theory table of contents

Pittsburgh, Pennsylvania, United States

Pages: 45 - 52

Year of Publication: 1992

ISBN:0-89791-497-X

Author

Kevin J. Lang

NEC Research Institute, 4 Independence Way, Princeton NJ

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 52, Citation Count: 19

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/130385.130390 What is a DOI?

ABSTRACT

Approximate inference of finite state machines from sparse labeled examples has been proved NP-hard when an adversary chooses the target machine and the training set [Ang78, KV89, PW89]. We have, however, empirically found that DFA's are approximately learnable from sparse data when the target machine and training set are selected at random.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Ang78	D. Angluin. (1978) On the Complexity of Minimum Inference of Regular Sets. Information and Control, Vol. 39, pp. 337-350.
	KV89	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]
	PM88	S. K. Park , K. W. Miller, Random number generators: good ones are hard to find, Communications of the ACM, v.31 n.10, p.1192-1201, Oct. 1988 [doi>10.1145/63039.63042]
	PW89	L. Pitt , M. K. Warmuth, The minimum consistent DFA problem cannot be approximated within and polynomial, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.421-432, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73048]
	TB73	B. Trakhtenbrot and Ya. Barzdin'. (1973) Finite Automata: Behavior and Synthesis. North-Holland Publishing Company, Amsterdam.
	V78	L. Veelenturf. (1978) Inference of Sequential Machines from Sample Computations. IEEE Transactions on Computers, Vol. 27, pp. 167-170.

CITED BY 19

	Rajesh Parekh , Vasant G. Honavar, Learning DFA from Simple Examples, Machine Learning, v.44 n.1-2, p.9-35, July-August 2001
	Arlindo L. Oliveira , João P. M. Silva, Efficient Algorithms for the Inference of Minimum Size DFAs, Machine Learning, v.44 n.1-2, p.93-119, July-August 2001
	Jorge M. Pena , Arlindo L. Oliveira, A new algorithm for the reduction of incompletely specified finite state machines, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.482-489, November 08-12, 1998, San Jose, California, United States
	Yoav Freund , Michael Kearns , Dana Ron , Ronitt Rubinfeld , Robert E. Schapire , Linda Sellie, Efficient learning of typical finite automata from random walks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.315-324, May 16-18, 1993, San Diego, California, United States
	Amos Beimel , Francesco Bergadano , Nader H. Bshouty , Eyal Kushilevitz , Stefano Varricchio, Learning functions represented as multiplicity automata, Journal of the ACM (JACM), v.47 n.3, p.506-530, May 2000
	A. Vahed , C. W. Omlin, A machine learning method for extracting symbolic knowledge from recurrent neural networks, Neural Computation, v.16 n.1, p.59-71, January 2004
	Orlando Cicchello , Stefan C. Kremer, Inducing grammars from sparse data sets: a survey of algorithms and results, The Journal of Machine Learning Research, 4, p.603-632, 12/1/2003
	François Denis , Aurélien Lemay , Alain Terlutte, Learning regular languages using RFSAs, Theoretical Computer Science, v.313 n.2, p.267-294, 17 February 2004
	Simon M. Lucas , T. Jeff Reynolds, Learning Deterministic Finite Automata with a Smart State Labeling Evolutionary Algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.7, p.1063-1074, July 2005
	Kenneth L. Ingham , Anil Somayaji , John Burge , Stephanie Forrest, Learning DFA representations of HTTP for protecting web applications, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.5, p.1239-1255, April, 2007
	Julien Carme , Rémi Gilleron , Aurélien Lemay , Joachim Niehren, Interactive learning of node selecting tree transducer, Machine Learning, v.66 n.1, p.33-67, January 2007
	Alan D. Blair , Jordan B. Pollack, Analysis of dynamical recognizers, Neural Computation, v.9 n.5, p.1127-1142, July 1, 1997
	Henrik Jacobsson, The Crystallizing Substochastic Sequential Machine Extractor: CrySSMEx, Neural Computation, v.18 n.9, p.2211-2255, September 2006
	Andreas Birkendorf , Hans Ulrich Simon, Using computational learning strategies as a tool for combinatorial optimization, Annals of Mathematics and Artificial Intelligence, v.22 n.3-4, p.237-257, 1998
	Christophe Damas , Bernard Lambeau , Pierre Dupont , Axel van Lamsweerde, Generating Annotated Behavior Models from End-User Scenarios, IEEE Transactions on Software Engineering, v.31 n.12, p.1056-1073, December 2005
	Pierre Dupont , Bernard Lambeau , Christophe Damas , Axel van Lamsweerde, THE QSM ALGORITHM AND ITS APPLICATION TO SOFTWARE BEHAVIOR MODEL INDUCTION, Applied Artificial Intelligence, v.22 n.1-2, p.77-115, January 2008
	Tsungnan Lin , C. Lee Giles, Group-Linking Method: A Unified Benchmark for Machine Learning with Recurrent Neural Network, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E90-A n.12, p.2916-2929, December 2007
	Neil Walkinshaw , Kirill Bogdanov , Mike Holcombe , Sarah Salahuddin, Improving dynamic software analysis by applying grammar inference principles, Journal of Software Maintenance and Evolution: Research and Practice, v.20 n.4, p.269-290, July 2008
	Leonid (Aryeh) Kontorovich , Boaz Nadler, Universal Kernel-Based Learning with Applications to Regular Languages, The Journal of Machine Learning Research, 10, p.1095-1129, June 2009