A note on the expressive power of probabilistic context free grammars
Journal of Logic, Language and Information 15 (3) (2006)
| Abstract | We examine the expressive power of probabilistic context free grammars (PCFGs), with a special focus on the use of probabilities as a mechanism for reducing ambiguity by filtering out unwanted parses. Probabilities in PCFGs induce an ordering relation among the set of trees that yield a given input sentence. PCFG parsers return the trees bearing the maximum probability for a given sentence, discarding all other possible trees. This mechanism is naturally viewed as a way of defining a new class of tree languages. We formalize the tree language thus defined, study its expressive power, and show that the latter is beyond context freeness. While the increased expressive power offered by PCFGs helps to reduce ambiguity, we show that, in general, it cannot be decided whether a PCFG removes all ambiguities. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,701 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesTheo Janssen, Gerard Kok & Lambert Meertens (1977). On Restrictions on Transformational Grammars Reducing the Generative Power. Linguistics and Philosophy 1 (1):111 - 118.
Mati Pentus (1997). Product-Free Lambek Calculus and Context-Free Grammars. Journal of Symbolic Logic 62 (2):648-660.
Paulo A. S. Veloso, Renata P. de Freitas, Petrucio Viana, Mario Benevides & Sheila R. M. Veloso (2007). On Fork Arrow Logic and its Expressive Power. Journal of Philosophical Logic 36 (5):489 - 509.
Makoto Kanazawa (2010). Second-Order Abstract Categorial Grammars as Hyperedge Replacement Grammars. Journal of Logic, Language and Information 19 (2).
Daniel Feinstein & Shuly Wintner (2008). Highly Constrained Unification Grammars. Journal of Logic, Language and Information 17 (3).
Stephan Kepser & Jim Rogers (2011). The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-Free Tree Grammars. Journal of Logic, Language and Information 20 (3):361-384.
Philippe de Groote & Sylvain Pogodalla (2004). On the Expressive Power of Abstract Categorial Grammars: Representing Context-Free Formalisms. Journal of Logic, Language and Information 13 (4).
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads1 ( #274,830 of 549,090 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
