Article

Free access

Efficient learning of typical finite automata from random walks

Authors:

Linda SellieAuthors Info & Claims

STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing

Pages 315 - 324

https://doi.org/10.1145/167088.167191

Published: 01 June 1993 Publication History

PDF eReader

References

[1]

Dana Angluin. On the complexity of minimum inference of regular sets. Information and Control, 39:337-350, 1978.

Google Scholar

[2]

Dana Angluin. Learning regular sets from queries and counterexamples. Information and Computation, 75:87-106, November 1987.

Digital Library

Google Scholar

[3]

Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Nathan Linial, and Steven Phillips. Biased random walks. In Proceedings of the Twenty-Fourth Annual A CM Symposium on the Theory of Computing, pages 1-9, May 1992.

Digital Library

Google Scholar

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

Google Scholar

[5]

Avrim Blum. Some tools for approximate 3-coloring. In 31st Annual Symposium on Foundations of Computer Science, pages 554-562, October 1990.

Digital Library

Google Scholar

[6]

B. Chor and O. Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM Journal on Computing, 17:230-261, 1988.

Digital Library

Google Scholar

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

Digital Library

Google Scholar

[8]

M. Feder, N. Merhav, and M. Gutman. Universal prediction of individual sequences. IEEE Transactions on Information Theory, 38:1258-1270, 1992.

Digital Library

Google Scholar

[9]

William Feller. An Introduction to Probability and its Applications, volume 1. John Wiley and Sons, third edition, 1968.

Google Scholar

[10]

E. Mark Gold. System identification via state characterization. Automatica, 8:621-636, 1972.

Digital Library

Google Scholar

[11]

E. Mark Gold. Complexity of automaton identification from given data. Information and Control, 37:302-320, 1978.

Google Scholar

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

Digital Library

Google Scholar

[13]

Michael Keams and Leslie G. Valiant. Cryptographic limitations on learning Boolean formulae and finite automata. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 433--444, May 1989. To appear, Journal of the Association for Computing Machinery.

Digital Library

Google Scholar

[14]

Kevin J. Lang. Random DFA's can be approximately learned from sparse uniform examples. In Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory, pages 45-52, July 1992.

Digital Library

Google Scholar

[15]

Nick Littlestone. Learning when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2:285- 318, 1988.

Digital Library

Google Scholar

[16]

Leonard Pitt and Leslie G. Valiant. Computational limitations on learning from examples. Journal of the Association for Computing Machinery, 35(4):965-984, October 1988.

Digital Library

Google Scholar

[17]

Leonard Pitt and Manfred K. Warmuth. Prediction-preserving reducibility. Journal of Computer and System Sciences, 41 (3):430--467, December 1990.

Digital Library

Google Scholar

[18]

Leonard Pitt and Manfred K. Warmuth. The minimum consistent DFA problem cannot be approximated within any polynomial. Journal of the Association for Computing Machinery, 40(1):95-142, January 1993.

Digital Library

Google Scholar

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

Google Scholar

[20]

Ronald L. Rivest and Robert E. Schapire. Inference of finite automata using homing sequences. In Proceedings of the Twenty First Annual A CM Symposium on Theory of Computing, pages 411--420, May 1989. To appear, Information and Computation.

Digital Library

Google Scholar

[21]

Ronald L. Rivest and Robert Sloan. Learning complicated concepts reliably and usefully. In Proceedings AAAI-88, pages 635-639, August 1988.

Google Scholar

[22]

M. Santha and U. V. Vazirani. Generating quasi-random sequences from semi-random sources. Journal of Computer and System Sciences, 33(1 ):75-87, August 1986.

Digital Library

Google Scholar

[23]

B. A. Trakhtenbrot and Ya. M. Barzdin'. Finite Automata: Behavior and Synthesis. North-Holland, 1973.

Google Scholar

[24]

L. G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134--1142, November 1984.

Digital Library

Google Scholar

[25]

U. V. Vazirani. Strong communication complexity or generating quasi-random sequences from two communicating semirandom sources. Combinatorica, 7:375-392, 1987.

Digital Library

Google Scholar

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

Digital Library

Google Scholar

Cited By

View all

Vain JKanter GAnier A(2019)Learning Timed Automata from Interaction TracesIFAC-PapersOnLine10.1016/j.ifacol.2019.12.09752:19(205-210)Online publication date: 2019
https://doi.org/10.1016/j.ifacol.2019.12.097
Angluin DChen D(2015)Learning a Random DFA from Uniform Strings and State InformationProceedings of the 26th International Conference on Algorithmic Learning Theory - Volume 935510.1007/978-3-319-24486-0_8(119-133)Online publication date: 4-Oct-2015
https://dl.acm.org/doi/10.1007/978-3-319-24486-0_8
Abney S(2010)Statistical methods in language processingWIREs Cognitive Science10.1002/wcs.1112:3(315-322)Online publication date: 22-Sep-2010
https://doi.org/10.1002/wcs.111
Show More Cited By

Index Terms

Efficient learning of typical finite automata from random walks

Recommendations

A Model for Random Random-Walks on Finite Groups

A model for a random random-walk on a finite group is developed where the group elements that generate the random-walk are chosen uniformly and with replacement from the group. When the group is the d-cube Z^d₂, it is shown that if the generating set is ...
Efficient distributed random walks with applications
PODC '10: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing

We focus on the problem of performing random walks efficiently in a distributed network. Given bandwidth constraints, the goal is to minimize the number of rounds required to obtain a random walk sample. We first present a fast sublinear time ...
Fast Random Walks on Finite Graphs and Graph Topological Information
ICNC '11: Proceedings of the 2011 Second International Conference on Networking and Computing

A random walk on a graph is a process in which a particle on a vertex repeatedly moves to its adjacent vertex according to transition probability, which is given in advance. The behavior of random walks depend on its transition probability, and the ``...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing

June 1993

812 pages

ISBN:0897915917

DOI:10.1145/167088

Chairmen:
Rao Kosaraju
John Hopkins Univ., Baltimore, MD
,
David Johnson
AT&T Bell Lab.
,
Alok Aggarwal
IBM T. J. Watson Research Center,Yorktown Heights, NY

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC93

Sponsor:

SIGACT

STOC93: 25th Annual ACM Symposium on the Theory of Computing

May 16 - 18, 1993

California, San Diego, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
582
Total Downloads

Downloads (Last 12 months)52
Downloads (Last 6 weeks)8

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Vain JKanter GAnier A(2019)Learning Timed Automata from Interaction TracesIFAC-PapersOnLine10.1016/j.ifacol.2019.12.09752:19(205-210)Online publication date: 2019
https://doi.org/10.1016/j.ifacol.2019.12.097
Angluin DChen D(2015)Learning a Random DFA from Uniform Strings and State InformationProceedings of the 26th International Conference on Algorithmic Learning Theory - Volume 935510.1007/978-3-319-24486-0_8(119-133)Online publication date: 4-Oct-2015
https://dl.acm.org/doi/10.1007/978-3-319-24486-0_8
Abney S(2010)Statistical methods in language processingWIREs Cognitive Science10.1002/wcs.1112:3(315-322)Online publication date: 22-Sep-2010
https://doi.org/10.1002/wcs.111
Javed FMernik MGray JBryant B(2008)MARSInformation and Software Technology10.1016/j.infsof.2007.08.00350:9-10(948-968)Online publication date: 1-Aug-2008
https://dl.acm.org/doi/10.1016/j.infsof.2007.08.003
Whiteford TKwong R(2007)PROBABILISTIC FAULT DIAGNOSIS IN DISCRETE EVENT SYSTEMS WITH INCOMPLETE MODELSIFAC Proceedings Volumes10.3182/20070613-3-FR-4909.0001940:6(97-102)Online publication date: 2007
https://doi.org/10.3182/20070613-3-FR-4909.00019
Roch S(2007)On learning thresholds of parities and unions of rectangles in random walk modelsRandom Structures & Algorithms10.1002/rsa.2016231:4(406-417)Online publication date: 31-Jan-2007
https://doi.org/10.1002/rsa.20162
Holmes MIsbell CCohen WMoore A(2006)Looping suffix tree-based inference of partially observable hidden stateProceedings of the 23rd international conference on Machine learning10.1145/1143844.1143896(409-416)Online publication date: 25-Jun-2006
https://dl.acm.org/doi/10.1145/1143844.1143896
Kontorovich LCortes CMohri M(2006)Learning linearly separable languagesProceedings of the 17th international conference on Algorithmic Learning Theory10.1007/11894841_24(288-303)Online publication date: 7-Oct-2006
https://dl.acm.org/doi/10.1007/11894841_24
Ravikumar BXiong X(2005)Implementing sequential and parallel programs for the homing sequence problemAutomata Implementation10.1007/3-540-63174-7_10(120-131)Online publication date: 6-Jun-2005
https://doi.org/10.1007/3-540-63174-7_10
Friedman JJoux ARoichman YStern JTillich J(2005)The action of a few random permutations on r-tuples and an application to cryptographySTACS 9610.1007/3-540-60922-9_31(375-386)Online publication date: 7-Jun-2005
https://doi.org/10.1007/3-540-60922-9_31
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

Cited By

Index Terms

Recommendations

A Model for Random Random-Walks on Finite Groups

Efficient distributed random walks with applications

Fast Random Walks on Finite Graphs and Graph Topological Information