Thomas Icard
Stanford University
A probabilistic Chomsky–Schützenberger hierarchy of grammars is introduced and studied, with the aim of understanding the expressive power of generative models. We offer characterizations of the distributions definable at each level of the hierarchy, including probabilistic regular, context-free, (linear) indexed, context-sensitive, and unrestricted grammars, each corresponding to familiar probabilistic machine classes. Special attention is given to distributions on (unary notations for) positive integers. Unlike in the classical case where the "semi-linear" languages all collapse into the regular languages, using analytic tools adapted from the classical setting we show there is no collapse in the probabilistic hierarchy: more distributions become definable at each level. We also address related issues such as closure under probabilistic conditioning.
Keywords Probabilistic computation  Chomsky hierarchy  Generative models
Categories (categorize this paper)
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Translate to english
Revision history

Download options

PhilArchive copy

 PhilArchive page | Other versions
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Aspects of the Theory of Syntax.Noam Chomsky - 1965 - Cambridge, MA, USA: MIT Press.
Computing Machinery and Intelligence.Alan M. Turing - 1950 - Mind 59 (October):433-60.
Psychological Predicates.Hilary Putnam - 1967 - In W. H. Capitan & D. D. Merrill (eds.), Art, Mind, and Religion. University of Pittsburgh Press. pp. 37--48.

View all 28 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Languages, Machines, and Classical Computation.Luis M. Augusto - 2021 - London, UK: College Publications.
Aspects of the Theory of Syntax.Noam Chomsky - 1965 - Cambridge, MA, USA: MIT Press.
The Formal Theory of Grammar. [REVIEW]L. J. - 1975 - Review of Metaphysics 28 (3):557-558.
Mentalistic Turn, a Critical Evaluation of Chomsky.Kalyan Sen Gupta - 1990 - K.P. Bagchi & Co. In Collaboration with Jadavpur University.
Mechanisms and Generative Material Models.Sim-Hui Tee - 2019 - Synthese 198 (7):6139-6157.


Added to PP index

Total views
659 ( #11,932 of 2,506,017 )

Recent downloads (6 months)
148 ( #4,274 of 2,506,017 )

How can I increase my downloads?


My notes