Learning fallible finite state automata

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Learning fallible finite state automata

Full text

Pdf (1.02 MB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the sixth annual conference on Computational learning theory table of contents

Santa Cruz, California, United States

Pages: 218 - 227

Year of Publication: 1993

ISBN:0-89791-611-5

Authors

Dana Ron
Ronitt Rubinfeld

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): 19, Downloads (12 Months): 39, Citation Count: 3

Additional Information:

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/168304.168336 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.

	Ang87	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]
	AL88	Dana Angluin , Philip Laird, Learning From Noisy Examples, Machine Learning, v.2 n.4, p.343-370, April 1988 [doi>10.1023/A:1022873112823]
	AS91	Dana Angluin , Donna K. Slonim, Learning monotone DNF with an incomplete membership oracle, Proceedings of the fourth annual workshop on Computational learning theory, p.139-146, August 05-07, 1991, Santa Cruz, California, United States
	BEHW87	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]
	FKRRSS93	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 [doi>10.1145/167088.167191]
	GKS90	S.A. Goldman, M. J. Kearns, and R. E. Schapire. Exact identification of circuits using fixed points of amplification functions. In Proceedings of the 81st Annual Symposium on Foundations of Computer Science, pages 193-202. IEEE Computer Society Press, 1990.
	GM92	Sally A. Goldman , H. David Mathias, Learning k-term DNF formulas with an incomplete membership oracle, Proceedings of the fifth annual workshop on Computational learning theory, p.77-84, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130394]
	Kea93	Michael Kearns, Efficient noise-tolerant learning from statistical queries, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.392-401, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167200]
	KL88	Michael Kearns , Ming Li, Learning in the presence of malicious errors, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.267-280, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62238]
	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]
	PW90	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]
	RR92	D. Ron and R. Rubinfeld. Learning and Correcting Fallible Finite State Automata. Technical Report 92-14, Hebrew University Department of Computer Science, 1992.
	RS87	R. Rivest and R. Schapire. Diversity-based inference of finite automata. In Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, pages 78-87. IEEE Computer Science Press, 1987.
	RS89	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]
	Sak91	Yasubumi Sakakibara, On learning from queries and counterexamples in the presence of noise, Information Processing Letters, v.37 n.5, p.279-284, March 14, 1991 [doi>10.1016/0020-0190(91)90220-C]
	Slo88	Robert Sloan, Types of noise in data for concept learning, Proceedings of the first annual workshop on Computational learning theory, p.91-96, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	SS92	Yasubumi Sakakibara , Rani Siromoney, A noise model on learning sets of strings, Proceedings of the fifth annual workshop on Computational learning theory, p.295-302, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130418]
	SV88	George Shackelford , Dennis Volper, Learning k-DNF with noise in the attributes, Proceedings of the first annual workshop on Computational learning theory, p.97-103, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	Val84	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]
	Val85	L.G. Valiant. Learning disjunctions of conjunctions. In Proceedings of the 9th International Jo,nt Conference on Artsficial Inteligence, pages 560-566. Morgan Kaufmann, 1985.

CITED BY 3

	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
	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 Angluin , Mārtiņš Kriķis, Learning with malicious membership queries and exceptions (extended abstract), Proceedings of the seventh annual conference on Computational learning theory, p.57-66, July 12-15, 1994, New Brunswick, New Jersey, United States