Partially Ordered Multiset Context-free Grammars and Free-word-order Parsing

Mark-Jan Nederhof, Giorgio Satta, Stuart Shieber


Abstract
We present a new formalism, partially ordered multiset context-free grammars (poms-CFG), along with an Earley-style parsing algorithm. The formalism, which can be thought of as a generalization of context-free grammars with partially ordered right-hand sides, is of interest in its own right, and also as infrastructure for obtaining tighter complexity bounds for more expressive context-free formalisms intended to express free or multiple word-order, such as ID/LP grammars. We reduce ID/LP grammars to poms-grammars, thereby getting finer-grained bounds on the parsing complexity of ID/LP grammars. We argue that in practice, the width of attested ID/LP grammars is small, yielding effectively polynomial time complexity for ID/LP grammar parsing.
Anthology ID:
W03-3020
Volume:
Proceedings of the Eighth International Conference on Parsing Technologies
Month:
April
Year:
2003
Address:
Nancy, France
Venues:
IWPT | WS
SIG:
SIGPARSE
Publisher:
Note:
Pages:
171–182
Language:
URL:
https://www.aclweb.org/anthology/W03-3020
DOI:
Bib Export formats:
BibTeX MODS XML EndNote
PDF:
http://aclanthology.lst.uni-saarland.de/W03-3020.pdf