Probabilistic Parsing Strategies

2002/11/14 by Mark-Jan Nederhof, Nederhof, Mark-Jan, Giorgio Satta +1
Computer Science · #Computation and Language (cs.CL) #F.4.3 #FOS: Computer and information sciences #I.2.7 #Natural Language Processing Techniques #Speech and dialogue systems #cs.CL #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.cs/0211017

36 pages, 1 figure

arxiv created 2002/11/14 · openalex publication_date 2002/11/14 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

We present new results on the relation between purely symbolic context-free parsing strategies and their probabilistic counter-parts. Such parsing strategies are seen as constructions of push-down devices from grammars. We show that preservation of probability distribution is possible under two conditions, viz. the correct-prefix property and the property of strong predictiveness. These results generalize existing results in the literature that were obtained by considering parsing strategies in isolation. From our general results we also derive negative results on so-called generalized LR parsing.

Related

• An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities
• Parsing with Principles and Probabilities
• Probabilistic Parsing Using Left Corner Language Models
• A probabilistic top-down parser for minimalist grammars
• Parsing Inside-Out