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 rewritten but also how their 
associated stacks are modified. 1_16, which were 
first described by Gazdar (1988), are constrained 
such that stacks are passed from the mother to at 
most a single daughter. 
For I_IG, the size of the domain of nontermi- 
nals and associated stacks (the analogue of the 
nonterminals in CFG) is not bound by the gram- 
mar. However, Vijay-Shanker and Weir (1993) 
demonstrate that polynomial time performance 
75 
can be achieved through the use of structure- 
sharing made possible by constraints in the way 
that LI6 use stacks. Although stacks of un- 
bounded size can arise during a derivation, it is 
not possible for a LIG to specify that two depen- 
dent, unbounded stacks must appear at distinct 
places in the derivation tree. Structure-sharing 
can therefore be used effectively because check- 
ing the applicability of rules at each step in the 
derivation involves the comparison of structures 
of limited size. 
Our goal is to generalize the constraints inher- 
ent in LIG to a formalism that manipulates fea- 
ture structures rather than stacks. As a guidl 
ing heuristic we will avoid formalisms that gen- 
erate tree sets with an unbounded number of un- 
bounded, dependent branches. It appears that the 
structure-sharing techniques used with LIG cannot 
be generalized in a straightforward way to such 
formalisms. 
Suppose that we generalize LIG to allow the 
stack to be passed from the mother to two daugh- 
ters. If this is done recursion can be used to pro- 
duce an unbounded number of unbounded, depen- 
dent branches. An alternative is to allow an un- 
bounded stack to be shared between two (or more) 
daughters but not with the mother. Thus, rules 
may mention more than one unbounded stack, but 
the stack associated with the mother is still asso- 
ciated with at most one daughter. We refer to 
this extension as Partially Linear Indexed Gram- 
mars (PLIG). 
Example 1 The PLIG with the following produc- 
tions generates the language 
{ anbmcnd m In, m > 1 } 
and the tree set shown in Figure 1. Because a sin- 
gle PUG production may mention more than one 
unbounded stack, variables (x, y) are introduced to 
distinguish between them. The notation A\[xa\] is 
used to denote the nonterminal A associated with 
any stack whose top symbol is ~r. 
A\[x\] --+ aA\[¢a\], 
B\[x~\] -~ bBb\], 
C\[~\] -~ cCb\], 
D\[xa\] --* dD\[x\], 
A\[x\] ~ B\[y\]C\[x\]D\[y\], 
B\[~\] -~ b, 
C\[~\] -~ c, 
D\[a\] ---* d. 
Example 2 A PLIG with the following produc- 
tions generates the k-copy language over { a,b }*, 
i.e., the language 
{w' Iwe {o,b}" } 
An 
a A\[~\] 
a A\[cr n \] 
B\[,~ m\] 
b B\[~\] 
b 
C\[c~ n\] D\[~ m\] 
c C\[o-"-'\] d v\[o-"-'\] 
c c\[~\] d D\[o-\] 
e d 
Figure 1: Tree set for {a"bmc'd "~ In,m >_ 1 } 
where k > 1. 
sD 
k copies 
A\[xch\] --~ a A\[x\], A\[z~J ~ b A\[x\]. 
Example 3 PLIG can "count" to any fixed k, i.e., 
a PLIG with the following productions generates the 
language 
{a?...a n In>O} 
where k > 1. 
S~ --* Al\[z\]...Ak\[z\], 
Al\[xa\] ~ al Al\[x\], AI~ --~ A, 
Ak \[x~r\] --+ ak Ak \[x\], Ak ~ --* A. 
In PLIG, stacks shared amongst siblings cannot 
be passed to the mother. As a consequence, there 
is no possibility that recursion can be used to in- 
crease the number of dependent branches. In fact, 
the number of dependent branches is bounded by 
the length of the right-hand-side of productions. 
By the same token, however, PUG may only gen- 
erate structural descriptions in which dependent 
76 
rll rl2 
A\[r, d S2\[c~( r,,, r~)\] 
a A\[rn-1\] 
a A\[n\] / b B\[rn-1\] C\[rn\] 
b BIll\] 
J 
b c C\[rl\] / 
where rl = ~1 and ri+l = ~2(ri) 
Figure 2: Tree set for { anbncn In > 1 } 
branches begin at nodes that are siblings of one 
another. Note that the tree shown in Figure 2 
is unobtainable because the branch rooted at 7/1 
is dependent on more than one of the branches 
originating at its sibling r/2. 
This limitation can be overcome by moving to 
a formalism that manipulates trees rather than 
stacks. We consider an extension of CFG in which 
each nonterminal A is associated with a tree r. 
Productions now specify how the tree associated 
with the mother is related to the trees associ- 
ated with the daughters. We denote trees with 
first order terms. For example, the following pro- 
duction requires that the x and y subtrees of the 
mother's tree are shared with the B and C daugh- 
ters, respectively. In addition, the daughters have 
in common the subtree z. 
A\[ao(x,y)\] --* B\[ch(z, z)\] 
z)\] 
There is a need to incorporate some kind of 
generalized notion of linearity into such a system. 
Corresponding to the linearity restriction in \[16 
we require that any part of the mother's tree is 
passed to at most one daughter. Corresponding 
to the partial linearity of PIAG, we permit subtrees 
that are not shared with the mother to be shared 
amongst the daughters. Under these conditions, 
the tree set shown in Figure 2 can be generated. 
current q • 
state 
ai-1 ai ai + l 
I I 
I A t 
first ' T ' last 
nonblank ~ aj \[ an " nonblank 
symbol current symbol 
symbol 
Figure 3: Encoding a Turing Machine 
The nodes 71 and r/2 share the tree rn, which oc- 
curs twice at the node r/2. At r12 the two copies of 
rn are distributed across the daughters. 
The formalism as currently described can be 
used to simulate arbitrary Turing Machine com- 
putations. To see this, note that an instanta- 
neous description of a Turing Machine can be en- 
coded with a tree as shown in Figure 3. Moves 
of the Turing Machine can be simulated by unary 
productions. The following production may be 
glossed: "if in state q and scanning the symbol X, 
then change state to q~, write the symbol Y and 
move left" 1 
A\[q(W(x), X, y)\] --* A\[q'(x, W, r(y))\] 
One solution to this problem is to prevent a sin- 
gle daughter sharing more than one of its subtrees 
with the mother. However, we do not impose this 
restriction because it still leaves open the possi- 
bility of generating trees in which every branch 
has the same length, thus violating the condition 
that trees have at most a bounded number of un- 
bounded, dependent branches. Figure 4 shows 
how a set of such trees can be generated by il- 
lustrating the effect of the following production. 
A\[c~(cr(x, y), a(x', y'))\] ---* A\[a(z, x)\] 
A\[cr(z, y)\] 
d\[~(z, z')\] u')\] 
To see this, assume (by induction) that all four 
of the daughter nonterminals are associated with 
the full binary tree of height i (v 0. All four of 
these trees are constrained to be equal by the 
production given above, which requires that they 
have identical left (i.e. z) subtrees (these subtrees 
must be the full binary tree vi-1). Passing the 
right subtrees (x, y, z' and //I) to the mother as 
shown allows the construction of a full binary tree 
with height i + 1 (ri+l). This can be repeated an 
1There will be a set of such productions for each 
tape symbol W. 
77 
A f ~ 
Ti+l 
0. 0. 
A 0. A.0. 
V~V~ V~V~ 
A 0. IA 0. 
I 
I /' D\[B \[\] 
77/%. A%. 
ri- l = \[7\] 
Figure 4: Building full binary trees 
unbounded number of times so that all full binary 
trees are produced. 
To overcome both of these problems we impose 
the following additional constraint on the produc- 
tions of a grammar. We require that subtrees of 
the mother that are passed to daughters that share 
subtrees with one another must appear as siblings 
in the mother's tree. Note that this condition rules 
out the production responsible for building full bi- 
nary trees since the x, y, x' and y' subtrees are not 
siblings in the mother's tree despite the fact that 
all of the daughters share a common subtree z. 
Moreover, since a daughter shares subtrees with 
itself, a special case of the condition is that sub- 
trees occurring within some daughter can only ap- 
pear as siblings in the mother. This condition also 
rules out the Turing Machine simulation. We refer 
to this formalism as Partially Linear Tree Gram- 
mars (PLTG). As a further illustration of the con- 
straints places on shared subtrees, Figure 5 shows 
a local tree that could appear in a derivation tree. 
This local tree is licensed by the following produc- 
tion which respects all of the constraints on PLT6 
productions. 
A\[0.1(f2(xl, x2, x3), f3(x4, 0.4))1 --* 
B\[0.~(~, ~, xl)\] 
c\[0.~(0.~, ~)1 D\[0.8(~=, ~, ~)\] 
Note that in Figure 5 the daughter nodes labelled 
B and D share a common subtree and the sub- 
trees shared between the mother and the B and D 
daughters appear as siblings in the tree associated 
i fl 
0"2 0.3 
\[\] \[\] \[\] \[\] f~ 
\[\] \[\] D I \[\] \[\] \[\] 
Figure 5: A PLTG local tree 
with the mother. 
Example 4 The PLTG with the following produc- 
tions generates the language 
{a"b"c ~ In >_ 1 } 
and the tree set shown in Figure 2. 
Sl \[frO\] ""+ A\[x\] $2 If(x, x)\], 
&\[f(~, y)\] --+ Bid &\[y\], &Ix\] 
-~ c\[d, 
A\[a2(x)\] --* aA\[x\], 
B\[0.~(~)\] -~ b~\[~\], 
C\[0.2(x)\] -~ cC\[~\], 
A\[fl\] -- a, 
B\[0.1\] --~ b, 
C\[0.d -~ c. 
Example 5 The PLTG with the following produc- 
tions generates the language of strings consisting 
of k copies of strings of matching parenthesis, i.e., 
the language 
where k k 1 and D is the set of strings in { (,) }* 
that have balanced brackets, i. e, the Dyck language 
over { (,) }. 
s\[\] -~,A\[x\]. A\[x\]: AB -~ ~, 
Y 
k copies 
A\[fl(x)\] --* ( A\[z\] ), A\[a2(x, y)\] --~ A\[z\] A\[y\]. 
3 Trees to Feature Structures 
Finally, we note that acyclic feature structures 
without re-entrancy can be viewed as trees with 
branches labelled by feature names and atomic 
values only found at leaf nodes (interior nodes 
78 
being unlabelled). Based on this observation, 
we can consider the constraints we have formu- 
lated for the tree system PI_TG as constraints on 
a unification-based grammar formalism such as 
PARR. We will call this system Partially Linear 
PATR (PI_PATR). Having made the move from trees 
to feature structures, we consider the possibility 
of re-entrancy in PI_PATR. 
Note that the feature structure at the root 
of a PI_PATR derivation tree will not involve re- 
entrancy. However, for the following reasons we 
believe that this does not constitute as great a 
limitation as it might appear. In unification-based 
grammar, the feature structure associated with 
the root of the tree is often regarded as the struc- 
ture that has been derived from the input (i.e., 
the output of a parser). As a consequence there 
is a tendency to use the grammar rules to accu- 
mulate a single, large feature structure giving a 
complete encoding of the analysis. To do this, un- 
bounded feature information is passed up the tree 
in a way that violates the constraints developed in 
this paper. Rather than giving such prominenc.e 
to the root feature structure, we suggest that the 
entire derivation tree should be seen as the object 
that is derived from the input, i.e., this is what 
the parser returns. Because feature structures as- 
sociated with all nodes in the tree are available, 
feature information need only be passed up the 
tree when it is required in order to establish de- 
pendencies within the derivation tree. When this 
approach is taken, there may be less need for re- 
entrancy in the root feature structure. Further- 
more, re-entrancy in the form of shared feature 
structures within and across nodes will be found 
in PI_PATR (see for example Figure 5). 
4 Generative Capacity 
HG are more powerful than CI=G and are known to 
be weakly equivalent to Tree Adjoining Grammar, 
Combinatory Categorial Grammar, and Head 
Grammar (Vijay-Shanker and Weir, 1994). PI_IG 
are more powerful than I_IG since they can gener- 
ate the k-copy language for any fixed k (see Exam- 
ple 2). Slightly more generally, PI_IG can generate 
the language 
{w~\]weR} 
for any k > 1 and regular language R. We be- 
lieve that the language involving copies of strings 
of matching brackets described in Example 5 can- 
not be generated by PI_IG but, as shown in Exam- 
pie 5, it can be generated by P/T(:; and therefore 
PLPATR. Slightly more generally, PLTG can gener- 
ate the language 
{w k Iw~L } 
for any k > 1 and context-free language L. It 
appears that the class of languages generated by 
PI_TG is included in those languages generated by 
Linear Context-Free Rewriting Systems (Vijay- 
Shanker et al., 1987) since the construction in- 
volved in a proof of this underlies the recognition 
algorithm discussed in the next section. 
As is the case for the tree sets of 16, 1_16 and 
Tree Adjoining Grammar, the tree sets generated 
by PI_TG have path sets that. are context-free lan- 
guages. In other words, the set of all strings la- 
belling root to frontier paths of derivation trees 
is a context-free language. While the tree sets 
of lAG and Tree Adjoining Grammars have inde- 
pendent branches, PI_T6 tree sets exhibit depen- 
dent branches, where the number of dependent 
branches in any tree is bounded by the grammar. 
Note that the number of dependent branches in 
the tree sets of 16 is not bounded by the grammar 
(e.g., they generate sets of all full binary trees). 
5 Tractable Recognition 
In this section we outline the main ideas un- 
derlying a polynomial time recognition algorithm 
for PlPATR that generalizes the CKY algorithm 
(Kasami, 1965; Younger, 1967). The key to this 
algorithm is the use of structure sharing tech- 
niques similar to those used to process I_lG effi- 
ciently (Vijay-Shanker and Weir, 1993). To un- 
derstand how these techniques are applied in the 
case of PLPATR, it is therefore helpful to consider 
first the somewhat simpler case of I_lG. 
The CKY algorithm is a bottom-up recognition 
algorithm for CI=G. For a given grammar G and 
input string al ... a,~ the algorithm constructs an 
array P, having n 2 elements, where element P\[i, j\] 
stores all and only those nonterminals of G that 
derive the substring ai...aj. A naive adapta- 
tion of this algorithm for I_lG recognition would 
involve storing a set of nonterminals and their as- 
sociated stacks. But since stack length is at least 
proportional to the length of the input string, 
the resultant algorithm would exhibit exponen- 
tial space and time complexity in the worst case. 
Vijay-Shanker and Weir (1993) showed that the 
behaviour of the naive algorithm can be improved 
upon. In I_lG derivations the application of a rule 
cannot depend on more than a bounded portion 
of the top of the stack. Thus, rather than storing 
the whole of the. potentially unbounded stack in 
a particular array entry, it suffices to store just 
79 
A\[~acr'\] 
(a) ///~ y 
ai B\[a~\] 
ap aq 
B\[a'~r\] 
(b) 
a T aq A\[~'~ro"\] 
ai Bloc'or\] aj 
a T aq 
Figure 6: "Context-Freeness' in I_IG derivations 
a bounded portion together with a pointer to the 
residue. 
Consider Figure 6. Tree (a) shows a LIG deriva- 
tion of the substring hi...aj from the object 
A\[aaa'\]. In this derivation tree, the node labelled 
B\[aa\] is a distinguished descendant of the root s 
and is the first point below A\[c~rcr ~\] at which the 
top symbol (or) of the (unbounded) stack aa is ex- 
posed. This node is called the terminator of the 
node labelled A\[acr\]. It is not difficult to show that 
only that portion of the derivation below the ter- 
minator node is dependent on more than the top 
of the stack ha. It follows that for any stack a'a, 
if there is a derivation of the substring %...he 
from B\[c~'c~\] (see tree (b)), then there is a cor- 
responding derivation of ai...aj from A\[al~rcr '\] 
(see tree (c)). This captures the sense in which 
I_IG derivations exhibit "context-freeness". Effi- 
cient storage of stacks can therefore be achieved 
by storing in Pit, j\] just that bounded amount of 
information (nonterminal plus top of stack) rele- 
vant to rule application, together with a pointer to 
any entry in Pip, q\] representing a subderivation 
from an object B\[c~'a\]. 
2The stack aa associated with B is "inherited" 
from the stack associated with A at the root of the 
tree. 
Before describing how we adapt this technique 
to the case of PLPATR we discuss the sense in 
which PLPATR derivations exhibit a "context- 
freeness" property. The constraints on PLPATR 
which we have identified in this paper ensure that 
these feature values can be manipulated indepen- 
dently of one another and that they behave in 
a stack-like way. As a consequence, the storage 
technique used effectively for LIG recognition may 
be generalized to the case of PLPATR. 
Suppose that we have the derived tree shown 
in Figure 7 where the nodes at the root of the 
subtrees T1 and 7"2 are the so-called f-terminator 
and g-terminator of the tree's root, respectively. 
Roughly speaking, the f-terminator of a node is 
the node from which it gets the value for the fea- 
ture f, Because of the constraints on the form 
of PLPATR productions, the derivations between 
the root of 7- and these terminators cannot in gen- 
eral depend on more than a bounded part of the 
feature structures \[\] and \[-~. At the root of the 
figure the feature structures \[-i-\] and \[\] have been 
expanded to show the extent of the dependency in 
this example. In this case, the value of the feature 
in \[-~ must be a, whereas, the feature g is Y not 
fixed. Furthermore, the value of the feature g in 
must be b, whereas, the feature f is not fixed. 
This means, for example, that the applicability of 
the productions used on the path from the root 
of rl to the root of r depends on the feature f in 
\[\] having the value a but does not depend on the 
value of the feature g in \[~\]. Note that in this tree 
the value of the feature g in \[-~ is \[,:c\] 
FI= 9 Fa 
and the value of the feature f in \[~ is 
F~= g:d 
Suppose that, in addition to the tree shown in 
Figure 7 the grammar generates the pair of trees 
shown in Figure 8. Notice that while the feature 
structures at the root of r~ and r4 are not compat- 
ible with ~ and \[~\], they do agree with respect 
to those parts that are fully expanded at v's root 
node. The "context-freeness" of PI_PATR means 
that given the three trees shown in Figures 7 and 8 
the tree shown in Figure 9 will also be generated 
by the grammar. 
This gives us a means of efficiently storing the 
potentially unbounded feature structures associ- 
ated with nodes in a derivation tree (derived fea- 
ture structures). By analogy with the situation for 
80 
g: F1 
9:b 
ap aq ar as 
Figure 7: Terminators in PLPATR 
\['i \]\] \[!,F\]\] f : c j f : g : d j4 g: g F~ g: 
ap aq ar as 
Figure 8: Compatible subderivations 
9 F~ \]\[7\] 
g g: 
ap aq ar as 
Figure 9: Alternative derivation 
LIG, derived feature structures can be viewed as 
consisting of a bounded part (relevant to rule ap- 
plication) plus unbounded information about the 
values of features. For each feature, we store in 
the recognition array a bounded amount of in- 
formation about its value locally, together with a 
pointer to a further array element. Entries in this 
element of the recognition array that are compat- 
ible (i.e. unifiable) with the bounded, local infor- 
mation correspond to different possible values for 
the feature. For example, we can use a single en- 
try in the recognition array to store the fact that 
all of the feature structures that can appear at the 
root of the trees in Figure 9 derive the substring 
ai...aj. This entry would be underspecified, for 
example, the value of feature \[-~ would be spec- 
ified to be any feature stored in the array entry 
for the substring ap... aq whose feature f had the 
value a. 
However, this is not the end of the story. In con- 
trast to LIG, PLPATR licenses structure sharing on 
the right hand side of productions. That is, par- 
tial linearity permits feature values to be shared 
between daughters where they are not also shared 
with the mother. But in that case, it appears 
that checking the applicability of a production at 
some point in a derivation must entail the com- 
parison of structures of unbounded size. In fact, 
this is not so. The PLPATR recognition algorithm 
employs a second array (called the compatibility 
array), which encodes information about the com- 
patibility of derived feature structures. Tuples of 
compatible derived feature structures are stored 
in the compatibility array using exactly the same 
approach used to store feature structures in the 
main recognition array. The presence of a tuple 
in the compatibility array (the indices of which 
encode which input substrings are spanned) in- 
dicates the existence of derivations of compatible 
feature structures. Due to the "context-freeness" 
of PLPATR, new entries can be added to the com- 
patibility array in a bottom-up manner based on 
existing entries without the need to reconstruct 
complete feature structures. 
6 Conclusions 
In considering ways of extending LIG, this paper 
has introduced the notion of partial linearity and 
shown how it can be manifested in the form of 
a constrained unification-based grammar formal- 
ism. We have explored examples of the kinds of 
tree sets and string languages that this system can 
generate. We have also briefly outlined the sense 
in which partial linearity gives rise to "context- 
freeness" in derivations and sketched how this can 
81 
be exploited in order to obtain a tractable recog- 
nition algorithm. 
7 Acknowledgements 
We thank Roger Evans, Gerald Gazdar~ Aravind 
Joshi, Bernard Lang, Fernando Pereira, Mark 
Steedman and K. Vijay-Shanker for their help. 
References 
Martin Emele. 1991. Unification with lazy non- 
redundant copying. In 29 th meeting Assoc. 
Comput. Ling., pages 323--330, Berkeley, CA. 
G. Gazdar. 1988. Applicability of indexed gram- 
mars to natural languages. In U. Reyle and 
C. Rohrer, editors, Natural Language Parsing 
and Linguistic Theories, pages 69--94. D. Rei- 
del, Dordrecht, Holland. 
Dale Gerdemann. 1989. Using restrictions to 
optimize unification parsing. In International 
Workshop of Parsing Technologies, pages 8-- 
17, Pittsburgh, PA. 
Kurt Godden. 1990. Lazy unification. In 28 th 
meeting Assoc. Comput. Ling., pages 180--187, 
Pittsburgh, PA. 
S. P. Harrison and T. M. Ellison. 1992. Restric- 
tion and termination in parsing with feature- 
theoretic grammars. Computational Linguis- 
tics, 18(4):519--531. 
L. Karttunen and M. Kay. 1985. Structure shar- 
ing with binary trees. In 23 th meeting Assoc. 
Comput. Ling., pages 133--136. 
T. Kasami. 1965. An efficient recognition and 
syntax algorithm for context-free languages. 
Technical Report AF-CRL-65-758, Air Force 
Cambridge Research Laboratory, Bedford, MA. 
Kiyoshi Kogure. 1990. Strategic lazy incremental 
copy graph unification. In 13 °` International 
Conference on Comput. Ling., pages 223--228, 
Helsinki. 
P. C. N. Pereira. 1985. A structure-sharing 
representation for unification-based grammar 
formalisms. In 23 ~h meeting Assoc. Comput. 
Ling., pages 137--144. 
S. M. Shieber. 1984. The design of a computer 
language for linguistic information. In 10 th 
International Conference on Comput. Ling., 
pages 363-366. 
S. M. Shieber. 1985. Using restriction to ex- 
tend parsing algorithms for complex-feature- 
based formalisms. In 23 rd meeting Assoc. Corn- 
put. Ling., pages 82-93. 
Hideto Tomabechi. 1991. Quasi-destructive 
graph unification. In 29 th meeting Assoc. Corn- 
put. Ling., pages 315--322, Berkeley, CA. 
K. Vijay-Shanker and D. J. Weir. 1993. Parsing 
some constrained grammar formalisms. Com- 
putational Linguistics, 19(4):591--636. 
K. Vijay-Shanker and D. a. Weir. 1994. The 
equivalence of four extensions of context-free 
grammars. Math. Syst. Theory, 27:511-546. 
K. Vijay-Shanker, D. J. Weir, and A. K. Joshi. 
1987. Characterizing structural descriptions 
produced by various grammatical formalisms. 
In 25 th meeting Assoc. Comput. Ling., pages 
104-111. 
David Wroblewski. 1987. Nondestructive graph 
unification. In 6 th National Conference on Arti- 
ficial Intelligence, pages 582--587, Seattle, WA. 
D. H. Younger. 1967. Recognition and parsing of 
context-free languages in time n 3. Information 
and Control, 10(2):189-208. 
82 
