Paper: A Tractable Extension Of Linear Indexed Grammars

ACL ID E95-1011
Title A Tractable Extension Of Linear Indexed Grammars
Venue Annual Meeting of The European Chapter of The Association of Computational Linguistics
Session Main Conference
Year 1995
Authors

Vijay-Shanker and Weir (1993) show that Linear Indexed Grammars (I_IG) can be processed in polynomial time by ex- ploiting constraints which make possible the extensive use of structure-sharing. This paper describes a formalism that is more powerful than I_IG, but which can also be processed in polynomial time using similar techniques. The formal- ism, which we refer to as Partially Lin- ear PATR (PI_PATR) manipulates feature structures rather than stacks.