4 papers · 1 filter
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…
Practical experiments with regular approximation of context-free languages
Mark-Jan Nederhof
Several methods are discussed that construct a finite automaton given a context-free grammar, including both methods that lead to subsets and those that lead to supersets of the or…
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…