Predictive Normal Forms for Composition in Categorical Grammars

Robert E. Wall, Kent Wittenburg


Abstract
Extensions to Categorial Grammars proposed to account for nonconstitutent conjunction and long-distance dependencies introduce the problem of equivalent derivations, an issue we have characterized as spurious ambiguity from the parsing perspective. In Wittenburg (1987) a proposal was made for compiling Categorial Grammars into predictive forms in order to solve the spurious ambiguity problem. This paper investigates formal properties o f grammars that use predictive versions of function composition. Among our results are (1) that grammars with predictive composition are in general equivalent to the originals if and only if a restriction on predictive rules is applied, (2) that modulo this restriction, the predictive grammars have indeed eliminated the problem of spurious ambiguity, and (3) that the issue o f equivalence is decidable, i.e., for any particular grammar, whether one needs to apply the restriction or not to ensure equivalence is a decidable question.
Anthology ID:
W89-0216
Volume:
Proceedings of the First International Workshop on Parsing Technologies
Month:
August
Year:
1989
Address:
Pittsburgh, Pennsylvania, USA
Editor:
Masaru Tomita
Venue:
IWPT
SIG:
SIGPARSE
Publisher:
Carnegy Mellon University
Note:
Pages:
152–161
Language:
URL:
https://aclanthology.org/W89-0216
DOI:
Bibkey:
Cite (ACL):
Robert E. Wall and Kent Wittenburg. 1989. Predictive Normal Forms for Composition in Categorical Grammars. In Proceedings of the First International Workshop on Parsing Technologies, pages 152–161, Pittsburgh, Pennsylvania, USA. Carnegy Mellon University.
Cite (Informal):
Predictive Normal Forms for Composition in Categorical Grammars (Wall & Wittenburg, IWPT 1989)
Copy Citation:
PDF:
https://aclanthology.org/W89-0216.pdf