Probabilistic Languages: A Review and Some Open Questions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Probabilistic Languages: A Review and Some Open Questions

Full text

Pdf (1.53 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 12 , Issue 4 (December 1980) table of contents

Pages: 361 - 379

Year of Publication: 1980

ISSN:0360-0300

Author

C. S. Wetherell

Bell Laboratories, Murray Hill, New Jersey

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 71, Citation Count: 29

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

	AHO73	Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
	AHO78	Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
	BOOT73	BOOTH, T. L., AND THOMPSON, R. A. "Applying probability measures to abstract languages," IEEE Trans. Comput. C-22 (1973), 442-450.
	FU75	Fu, K. S., AND BOOTH, T. L. "Grammatical inference--Introduction and survey," IEEE Trans. Syst., Man, Cybet. SMC-~ (1975), 95-111, 409-423.
	HOPC69	John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
	HUTC72	HUTCHINS, S.E. "Moments of string and derivation lengths of stochastic contextfree grammars," Inf. Sci. 4 (1972), 179-191.
	JUST75	JUSTESES, J., AND LARSEN, K. J. "Probabilistic context-free grammars that achieve capacity," Inf. Control 29 (1975), 268-285.
	KNUT71	KNUTH, D. E. "An empirical study of FORTRAN programs," Soflw. Prac. Exper. 1 (1971), 105-134.
	KUIC70	KUICH, W. "On the entropy of contextfree languages," Inf. Control 16 (1970), 173-200.
	KUIC71	KUICH, W., AND MAURER, H. "The structure generating function and entropy of mple languages," Inf. Control 19 (1971), 195-203.
	SOUL74	SOULE, S. "Entropies of probabilistic grammars," Inf. Control 25 (1974), 55-74.
	STEW72	STEWART, G.W. Introduction to matrix computations, Academic Press, New York, 1972.
	THOM74	THOMPSON, R. A. "Determination of probabilistic grammars for functionally specified probability-measure languages," IEEE Trans. Comput. C-23 (1974), 603- 614.
	THOM76	THOMPSON, R.A. "Language correction using probabilistic grammars," IEEE Trans. Comput. C-23 (1976), 275-286.
	WETH75	Charles Stanley Wetherell, Problems of error correction for programming languages., 1975

CITED BY 29

	Rafael C. Carrasco , Jose Oncina , Jorge Calera-Rubio, Stochastic Inference of Regular Tree Languages, Machine Learning, v.44 n.1-2, p.185-197, July-August 2001
	R. A. Sharman , F. Jelinek , R. Mercer, Generating a grammar for statistical training, Proceedings of the workshop on Speech and Natural Language, p.267-274, June 24-27, 1990, Hidden Valley, Pennsylvania
	C. S. Wetherell, Error Data Values in the Data-Flow Language VAL, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.226-238, April 1982
	R. Chaudhuri , A. N. V. Rao, Approximating grammar probabilities: solution of a conjecture, Journal of the ACM (JACM), v.33 n.4, p.702-705, Oct. 1986
	C. Shanmugamani , Robert W. Neufeld , V. Santhanam, Error recovery in LL(1) parsers using probabilistic grammar (abstract), Proceedings of the 1986 ACM fourteenth annual conference on Computer science, p.492, February 1986, Cincinnati, Ohio, United States
	F. Casacuberta, Some Relations Among Stochastic Finite State Networks Used in Automatic Speech Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.7, p.691-695, July 1990
	Zhiyi Chi , Stuart Geman, Estimation of probabilistic context-free grammars, Computational Linguistics, v.24 n.2, June 1998
	Mark-Jan Nederhof , Giorgio Satta, Left-to-right parsing and bilexical context-free grammars, Proceedings of the first conference on North American chapter of the Association for Computational Linguistics, p.272-279, April 29-May 04, 2000, Seattle, Washington
	Rieks op den Akker , Hugo ter Doest, Weakly restricted stochastic grammars, Proceedings of the 15th conference on Computational linguistics, August 05-09, 1994, Kyoto, Japan
	Timothy Hickey , Jacques Cohen, Automating program analysis, Journal of the ACM (JACM), v.35 n.1, p.185-220, Jan. 1988
	Anna Corazza , Renato De Mori , Roberto Gretter , Giorgio Satta, Optimal Probabilistic Evaluation Functions for Search Controlled by Stochastic Context-Free Grammars, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.16 n.10, p.1018-1027, October 1994
	Jason Eisner , Giorgio Satta, Efficient parsing for bilexical context-free grammars and head automaton grammars, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.457-464, June 20-26, 1999, College Park, Maryland
	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
	Anna Corazza , Renato De Mori , Roberto Gretter , Giorgio Satta, Computation of Probabilities for an Island-Driven Parser, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.9, p.936-950, September 1991
	Jacques Cohen, Bioinformatics—an introduction for computer scientists, ACM Computing Surveys (CSUR), v.36 n.2, p.122-158, June 2004
	Daowen Qiu , Huaiqing Wang, A probabilistic model of computing with words, Journal of Computer and System Sciences, v.70 n.2, p.176-200, March 2005
	John Hale, A probabilistic earley parser as a psycholinguistic model, Second meeting of the North American Chapter of the Association for Computational Linguistics on Language technologies 2001, p.1-8, June 01-07, 2001, Pittsburgh, Pennsylvania
	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
	Anoop Sarkar, Conditions on consistency of probabilistic Tree Adjoining Grammars, Proceedings of the 17th international conference on Computational linguistics, p.1164-1170, August 10-14, 1998, Montreal, Quebec, Canada
	Jose Luis Verdu-Mas , Rafael C. Carrasco , Jorge Calera-Rubio, Parsing with Probabilistic Strictly Locally Testable Tree Languages, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.7, p.1040-1050, July 2005
	Mark-Jan Nederhof , Giorgio Satta, Kullback-Leibler distance between probabilistic context-free grammars and probabilistic finite automata, Proceedings of the 20th international conference on Computational Linguistics, p.71-es, August 23-27, 2004, Geneva, Switzerland
	Dimitrios Lymberopoulos , Abhijit S. Ogale , Andreas Savvides , Yiannis Aloimonos, A sensory grammar for inferring behaviors in sensor networks, Proceedings of the fifth international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA
	Mark-Jan Nederhof , Giorgio Satta, Estimation of consistent probabilistic context-free grammars, Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, p.343-350, June 04-09, 2006, New York, New York
	Giorgio Satta , Enoch Peserico, Some computational complexity results for synchronous context-free grammars, Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, p.803-810, October 06-08, 2005, Vancouver, British Columbia, Canada
	José Borges , Mark Levene, A fine grained heuristic to capture web navigation patterns, ACM SIGKDD Explorations Newsletter, v.2 n.1, p.40-50, June, 2000
	Joan-Andreu Sánchez , José-Migual Benedí, Consistency of Stochastic Context-Free Grammars From Probabilistic Estimation Based on Growth Transformations, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.9, p.1052-1055, September 1997
	David V. Pynadath , Michael P. Wellman, Generalized Queries on Probabilistic Context-Free Grammars, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.1, p.65-77, January 1998
	Taisuke Sato , Yoshitaka Kameya , Kenichi Kurihara, Variational Bayes via propositionalized probability computation in PRISM, Annals of Mathematics and Artificial Intelligence, v.54 n.1-3, p.135-158, November 2008
	Taisuke Sato , Yoshitaka Kameya, Parameter learning of logic programs for symbolic-statistical modeling, Journal of Artificial Intelligence Research, v.15 n.1, p.391-454, July 2001