Efficient learning of typical finite automata from random walks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Efficient learning of typical finite automata from random walks

Full text

Pdf (1.38 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 315 - 324

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Yoav Freund
Michael Kearns
Dana Ron
Ronitt Rubinfeld
Robert E. Schapire
Linda Sellie

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 28, Citation Count: 18

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/167088.167191 What is a DOI?

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.

	1	Dana Angluin. On the complexity of minimum inference of regular sets. Information and Control, 39:337-350, 1978.
	2	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]
	3	Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Nathan Linial , Steven Phillips, Biased random walks, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.1-9, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129713]
	4	Ya. M. Barzdin'. Deciphering of sequential networks in the absence of an upper limit on the number of states. Soviet Physics Doklady, 15(2):94-97, August 1970.
	5	Avrim Blum. Some tools for approximate 3-coloring. In 31st Annual Symposium on Foundations of Computer Science, pages 554-562, October 1990.
	6	Benny Chor , Oded Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM Journal on Computing, v.17 n.2, p.230-261, April 1988 [doi>10.1137/0217015]
	7	Thomas Dean, Dana Angluin, Kenneth Basye, Sean Engelson, Leslie Kaelbling, Evangelos Kokkevis, and Oded Maron. Inferring finite automata with stochastic output functions and an application to map learning. In Proceedings Tenth National Conference on Artificial Intelligence, pages 208-214, July 1992.
	8	M. Feder, N. Merhav, and M. Gutman. Universal prediction of individual sequences. IEEE Transactions on Information Theory, 38:1258-1270, 1992.
	9	William Feller. An Introduction to Probability and its Applications, volume 1. John Wiley and Sons, third edition, 1968.
	10	E. Mark Gold. System identification via state characterization. Automatica, 8:621-636, 1972.
	11	E. Mark Gold. Complexity of automaton identification from given data. Information and Control, 37:302-320, 1978.
	12	David Haussler, Nick Littlestone, and Manfred K. Warmuth. Predicting {0, 1}-functions on randomly drawn points. In 29th Annual Symposium on Foundations of Computer Science, pages 100-109, October 1988.
	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	Kevin J. Lang, Random DFA's can be approximately learned from sparse uniform examples, Proceedings of the fifth annual workshop on Computational learning theory, p.45-52, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130390]
	15	Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
	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	Leonard Pitt , Manfred K. Warmuth, Prediction-preserving reducibility, Journal of Computer and System Sciences, v.41 n.3, p.430-467, Dec. 1990 [doi>10.1016/0022-0000(90)90028-J]
	18	Leonard Pitt , Manfred K. Warmuth, The minimum consistent DFA problem cannot be approximated within any polynomial, Journal of the ACM (JACM), v.40 n.1, p.95-142, Jan. 1993 [doi>10.1145/138027.138042]
	19	Ronald L. Rivest and Robert E. Schapire. Diversity-based inference of finite automata. In 28thAnnual Symposium on Foundations of Computer Science, pages 78-87, October 1987. To appear, Journal of the Association for Computing Machinery.
	20	R. L. Rivest , R. E. Schapire, Inference of finite automata using homing sequences, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.411-420, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73047]
	21	Ronald L. Rivest and Robert Sloan. Learning complicated concepts reliably and usefully. In Proceedings AAAI-88, pages 635-639, August 1988.
	22	Miklos Santha , Umesh V Vazirani, Generating quasi-random sequences from semi-random sources, Journal of Computer and System Sciences, v.33 n.1, p.75-87, Aug. 1986 [doi>10.1016/0022-0000(86)90044-9]
	23	B. A. Trakhtenbrot and Ya. M. Barzdin'. Finite Automata: Behavior and Synthesis. North-Holland, 1973.
	24	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]
	25	Umesh Vazirani, Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources, Combinatorica, v.7 n.4, p.375-392, Dec, 1987 [doi>10.1007/BF02579325]
	26	U. V. Vazirani and V. V. Vazirani. Random polynomial time is equal to slightly-random polynomial time. In 26th Annual Symposium on Foundations of Computer Science, pages 417- 428, October 1985.

CITED BY 18

	Dana Ron , Yoram Singer , Naftali Tishby, On the learnability and usage of acyclic probabilistic finite automata, Proceedings of the eighth annual conference on Computational learning theory, p.31-40, July 05-08, 1995, Santa Cruz, California, United States
	Dana Ron , Ronitt Rubinfeld, Learning fallible finite state automata, Proceedings of the sixth annual conference on Computational learning theory, p.218-227, July 26-28, 1993, Santa Cruz, California, United States
	Michael A. Bender , Antonio Fernández , Dana Ron , Amit Sahai , Salil Vadhan, The power of a pebble: exploring and mapping directed graphs, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.269-278, May 24-26, 1998, Dallas, Texas, United States
	Funda Ergün , S. Ravi Kumar , Ronitt Rubinfeld, On learning bounded-width branching programs, Proceedings of the eighth annual conference on Computational learning theory, p.361-368, July 05-08, 1995, Santa Cruz, California, United States
	Peter L. Bartlett , Paul Fischer , Klaus-Uwe Höffgen, Exploiting random walks for learning, Proceedings of the seventh annual conference on Computational learning theory, p.318-327, July 12-15, 1994, New Brunswick, New Jersey, United States
	Dana Ron , Ronitt Rubinfeld, Exactly learning automata with small cover time, Proceedings of the eighth annual conference on Computational learning theory, p.427-436, July 05-08, 1995, Santa Cruz, California, United States
	Dana Ron , Yoram Singer , Naftali Tishby, Learning probabilistic automata with variable memory length, Proceedings of the seventh annual conference on Computational learning theory, p.35-46, July 12-15, 1994, New Brunswick, New Jersey, United States
	Dana Ron , Ronitt Rubinfeld, Exactly Learning Automata of Small Cover Time, Machine Learning, v.27 n.1, p.69-96, April 1997
	Peter L. Bartlett , Paul Fischer , Klaus-Uwe Höffgen, Exploiting random walks for learning, Information and Computation, v.176 n.2, p.121-135, 01 August 2002
	Daniel Gildea , Daniel Jurafsky, Learning bias and phonological-rule induction, Computational Linguistics, v.22 n.4, p.497-530, December 1996
	William W. Cohen, The dual DFA learning problem (extended abstract): hardness results for programming by demonstration and learning first-order representations, Proceedings of the ninth annual conference on Computational learning theory, p.29-40, June 28-July 01, 1996, Desenzano del Garda, Italy
	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
	Michael P. Holmes , Charles Lee Isbell, Jr, Looping suffix tree-based inference of partially observable hidden state, Proceedings of the 23rd international conference on Machine learning, p.409-416, June 25-29, 2006, Pittsburgh, Pennsylvania
	David Carmel , Shaul Markovitch, Exploration Strategies for Model-based Learning in Multi-agent Systems: Exploration Strategies, Autonomous Agents and Multi-Agent Systems, v.2 n.2, p.141-172, June 1999
	William W. Cohen, Hardness Results for Learning First-Order Representations and Programming by Demonstration, Machine Learning, v.30 n.1, p.57-87, Jan. 1998
	Faizan Javed , Marjan Mernik , Jeff Gray , Barrett R. Bryant, MARS: A metamodel recovery system using grammar inference, Information and Software Technology, v.50 n.9-10, p.948-968, August, 2008
	Leonid (Aryeh) Kontorovich , Corinna Cortes , Mehryar Mohri, Kernel methods for learning languages, Theoretical Computer Science, v.405 n.3, p.223-236, October, 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