On the learnability and usage of acyclic probabilistic finite automata

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the learnability and usage of acyclic probabilistic finite automata

Full text

Pdf (1.14 MB)

Source

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

Santa Cruz, California, United States

Pages: 31 - 40

Year of Publication: 1995

ISBN:0-89791-723-5

Authors

Dana Ron	Institute of Computer Science and Center for Neural Computation, Hebrew University, Jerusalem 91904, Israel
Yoram Singer	Institute of Computer Science and Center for Neural Computation, Hebrew University, Jerusalem 91904, Israel
Naftali Tishby	Institute of Computer Science and Center for Neural Computation, Hebrew University, Jerusalem 91904, Israel

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 20, Citation Count: 8

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/225298.225302 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	Naoki Abe , Manfred K. Warmuth, On the Computational Complexity of Approximating Distributions by Probabilistic Automata, Machine Learning, v.9 n.2-3, p.205-260, July 1992 [doi>10.1007/BF00992677]
	2	L E Baum and T. Petne~ Statistical inference for probabilistic functions of finite state markov chains. Annals of Mathemaucal Statistics, 37, 1966~
	3	Y. Bengio, Y. le Cun, and D. Henderson. Globally trained handwritten word recognizer using spatial representation, convolutional neural networks, and hidden Markov models, tn Advances in Neural lnformauon Processing Systems, volume 6. Morgan Kaufmann, 1993.
	4	Rafael C. Carrasco , José Oncina, Learning Stochastic Regular Grammars by Means of a State Merging Method, Proceedings of the Second International Colloquium on Grammatical Inference and Applications, p.139-152, September 21-23, 1994
	5	FR Chen. Identification of contextual factos for pronounciation networks. In Proc. of lEEE ConJ on Acoustics, Speech and Stgnal Processing, pages 753-756, 1990
	6	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]
	7	Michael Kearns , Yishay Mansour , Dana Ron , Ronitt Rubinfeld , Robert E. Schapire , Linda Sellie, On the learnability of discrete distributions, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.273-282, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195155]
	8	N. Merhav and Y. Ephraim. Maximum likelihood hidden Markov modeling using a dominant sequence of states IEEE Trans. on ASSP, 39(9).2111-2115, 1991.
	9	R. Plamondon and C.G Leedtiam, editors. Computer Processmg of Handwriting. World Scientific. 1990.
	10	R. Plamondon, C Y Suen, and M.L. Simner, editors. Computer Recognition and Human Production of Handwriting. World Scientific, 1989.
	11	Lawrence R. Rabiner, A tutorial on hidden Markov models and selected applications in speech recognition, Readings in speech recognition, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
	12	L.R Rabiner and B. H. Juang. An introduction to hidden markov models. IEEEASSPMagazine, 3(1):4-16, 1986.
	13	M.D. Riley. A statistical model for generating pronounication networks. In Proc. of lEEE Conf on Acoustics, Speech and Signal Processing, pages 737-740, 1991.
	14	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 [doi>10.1145/180139.181006]
	15	D. Ron. Y. Singer, and T Tishby. On the, learnabdity and usage of acyclic probabilistlc finite automata. Technical Report CS- TR-23, Hebrew Umversity, 1995.
	16	D. Sankoff and J.B. Kruskal. Tune warps, strmg edits and mc~cromolecules, the theoo' and practice of sequence comparisot,. Addison-Wesley, Reading Mass, 1983.
	17	Y Singer and N. Tishby. Dynamical encoding of cursive handwriting. Biological Cybe. rnetics, 71 (3):227-237, 1994.
	18	Y. Singer and N Tishby. An adaptive cursive handwriting recognition system. Technical Report CS-TR-22, Hebrew University, 1995.
	19	Andreas Stolcke , Stephen M. Omohundro, Hidden Markov Model} Induction by Bayesian Model Merging, Advances in Neural Information Processing Systems 5, [NIPS Conference], p.11-18, November 30-December 03, 1992
	20	C. C. Tappert , C. Y. Suen , T. Wakahara, The State of the Art in Online Handwriting Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.8, p.787-808, August 1990 [doi>10.1109/34.57669]
	21	B A. Trakhtenbrot and Ya. M Brazdin' Finite Automata: Behawor and Synthesis. North-Holland. 1973.

CITED BY 8

	Alexander Clark , Franck Thollard, Partially distribution-free learning of regular languages from positive samples, Proceedings of the 20th international conference on Computational Linguistics, p.85-es, August 23-27, 2004, Geneva, Switzerland
	Enrique Vidal , Franck Thollard , Colin de la Higuera , Francisco Casacuberta , Rafael C. Carrasco, Probabilistic Finite-State Machines-Part I, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.7, p.1013-1025, July 2005
	Shlomo Argamon , Ido Dagan , Yuval Krymolowski, A memory-based approach to learning shallow natural language patterns, Proceedings of the 17th international conference on Computational linguistics, August 10-14, 1998, Montreal, Quebec, Canada
	Enrique Vidal , Frank Thollard , Colin de la Higuera , Francisco Casacuberta , Rafael C. Carrasco, Probabilistic Finite-State Machines-Part II, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.7, p.1026-1039, July 2005
	Alexander Clark , Franck Thollard, PAC-learnability of Probabilistic Deterministic Finite State Automata, The Journal of Machine Learning Research, 5, p.473-497, 12/1/2004
	Alexander Clark, Learning deterministic context free grammars: The Omphalos competition, Machine Learning, v.66 n.1, p.93-110, January 2007
	Glenn Ammons , Rastislav Bodík , James R. Larus, Mining specifications, ACM SIGPLAN Notices, v.37 n.1, p.4-16, Jan. 2002
	Matthew Young-Lai , Frank Wm. Tompa, Stochastic Grammatical Inference of Text Database Structure, Machine Learning, v.40 n.2, p.111-137, Aug. 2000