Journal of Logic, Language and Information 15 (3):219-231 (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||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Theo 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):137-161.
Daniel Feinstein & Shuly Wintner (2008). Highly Constrained Unification Grammars. Journal of Logic, Language and Information 17 (3):345-381.
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.
Christopher D. Manning & Kristina Toutanova, Feature Selection for a Rich HPSG Grammar Using Decision Trees.
Dan Klein & Christopher D. Manning, An Ç ´Ò¿ Μ Agenda-Based Chart Parser for Arbitrary Probabilistic Context-Free Grammars.
Philippe de Groote & Sylvain Pogodalla (2004). On the Expressive Power of Abstract Categorial Grammars: Representing Context-Free Formalisms. [REVIEW] Journal of Logic, Language and Information 13 (4):421-438.
Sorry, there are not enough data points to plot this chart.
Added to index2009-01-28
Total downloads1 ( #291,386 of 722,813 )
Recent downloads (6 months)0
How can I increase my downloads?