5 papers
Tabular Parsing
Mark-Jan Nederhof, Giorgio Satta
This is a tutorial on tabular parsing, on the basis of tabulation of nondeterministic push-down automata. Discussed are Earley's algorithm, the Cocke-Kasami-Younger algorithm, tabu…
Probabilistic Parsing Strategies
Mark-Jan Nederhof, Giorgio Satta
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 constructi…
Restrictions on Tree Adjoining Languages
Giorgio Satta, William Schuler
Several methods are known for parsing languages generated by Tree Adjoining Grammars (TAGs) in O(n^6) worst case running time. In this paper we investigate which restrictions on TA…
Prefix Probabilities from Stochastic Tree Adjoining Grammars
Mark-Jan Nederhof, Anoop Sarkar, Giorgio Satta
Language models for speech recognition typically use a probability model of the form Pr(a_n | a_1, a_2, ..., a_{n-1}). Stochastic grammars, on the other hand, are typically used to…
A Variant of Earley Parsing
Mark-Jan Nederhof, Giorgio Satta
The Earley algorithm is a widely used parsing method in natural language processing applications. We introduce a variant of Earley parsing that is based on a ``delayed'' recognitio…