A Tractable Extension of Linear Indexed Grammars

A Tractable Extension of Linear Indexed Grammars Bill Keller and David Weir School of Cognitive and Computing Sciences University of Sussex Falmer, Brighton BN1 9QH UK b±11. keller/david, we±r~lcogs, sus sex. ac. uk Abstract 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. 1 Introduction Unification-based grammar formalisms can be viewed as generalizations of Context-Free Gram- mars (CFG) where the nonterminal symbols are replaced by an infinite domain of feature struc- tures. Much of their popularity stems from the way in which syntactic generalization may be el- egantly stated by means of constraints amongst features and their values. Unfortunately, the ex- pressivity of these formalisms can have undesir- able consequences for their processing. In naive implementations of unification grammar parsers, feature structures play the same role as nonter- minals in standard context-free grammar parsers. Potentially large feature structures are stored at intermediate steps in the computation, so that the space requirements of the algorithm are ex- pensive. Furthermore, the need to perform non- destructive unification means that a large propor- tion of the processing time is spent copying feature structures. One approach to this problem is to refine pars- ing algorithms by developing techniques such as restrictions, structure-sharing, and lazy unifica- tion that reduce the amount of structure that is stored and hence the need for copying of features structures (Shieber, 1985; Pereira, 1985; Kart- tunen and Kay, 1985; Wroblewski, 1987; Gerde- mann, 1989; Godden, 1990; Kogure, 1990; Emele, 1991; Tomabechi, 1991; Harrison and Ellison, 1992)). While these techniques can yield signifi- cant improvements in performance, the generality of unification-based grammar formalisms means that there are still cases where expensive process- ing is unavoidable. This approach does not ad- dress the fundamental issue of the tradeoff be- tween the descriptive capacity of a formalism and its computational power. In this paper we identify a set of constraints that can be placed on unification-based grammar formalisms in order to guarantee the existence of polynomial time parsing algorithms. Our choice of constraints is motivated by showing how they generalize constraints inherent in Linear Indexed Grammar (l_lG). We begin by describing how con- straints inherent in I.IG admit tractable process- ing algorithms and then consider how these con- straints can be generalized to a formalism that manipulates trees rather than stacks. The con- straints that we identify for the tree-based sys- tem can be regarded equally well as constraints on unification-based grammar formalisms such as PArR (Shieber, 1984). 2 From Stacks to Trees An Indexed Grammar (IG) can be viewed as a CFG in which each nonterminal is associated with a stack of indices. Productions specify not only how nonterminals can be …

Content truncated to 500 words