Linear Context-Free Rewriting Systems and Deterministic Tree-Walking 
Transducers* 
David J. Weir 
School of Cognitive and Computing Sciences 
University of Sussex 
Falmer, Brighton BN1 9QH 
davidw @ cogs. sussex, ac. uk 
Abstract 
We show that the class of string languages gener- 
ated by linear context-free rewriting systems is equal 
to the class of output languages of deterministic tree- 
walking transducers. From equivalences that have pre- 
viously been established we know that this class of lan- 
guages is also equal to the string languages generated 
by context-free hypergraph grammars, multicompo- 
nent tree-adjoining grammars, and multiple context- 
free grammars and to the class of yields of images of 
the regular tree languages under finite-copying top- 
down tree transducers. 
Introduction 
In \[9\] a comparison was made of the generative capac- 
ity of a number of grammar formalisms. Several were 
found to share a number of characteristics (described 
below) and the class of such formalisms was called lin- 
ear context-free rewriting systems. This paper shows 
how the class of string languages generated by linear 
context-free rewriting systems relates to a number of 
other systems that have been studied by formal lan- 
guage theorists. In particular, we show that the class 
of string languages generated by linear context-free 
rewriting systems is equal to the class of output lan- 
guages of deterministic tree-walking transducers \[1\]. 
A number of other equivalences have already been 
established. In \[10\] it was shown that linear context- 
free rewriting systems and multicomponent tree ad- 
joining grammars \[6\] generate the same string lan- 
guages. The multiple context-free grammars of \[7\] are 
equivalent to linear context-free systems. This follows 
*I would like to thank Joost Engelfriet for drawing my 
attention to context-free hypergraph grammars and their 
relationship to deterministic tree-walking automata. 
from the fact that multiple context-free grammars are 
exactly that subclass of the linear context-free rewrit- 
ing systems in which the objects generated by the 
grammar are tuples of strings. The class of output 
languages of deterministic tree-walking transducers is 
known to be equal to the class of yields of images of the 
regular tree languages under finite-copying top-down 
tree transducers \[4\] and in \[3\] it was shown that it also 
equal to the string languages generated by context-free 
hypergraph grammars \[2, 5\]. 
We therefore have a number of Characterizations of 
the same class of languages and results that have been 
established for the class of languages associated with 
one system carry over to the others. This is particu- 
larly fruitful in this case since the output languages of 
deterministic tree-walking transducers have been well 
studied (see \[4\]). 
In the remainder of the paper we describe linear 
context-free rewriting systems and deterministic tree- 
walking transducers and outline the equivalence proof. 
We then describe context-free hypergraph grammars 
and observe that they are a context-free rewriting sys- 
tem. 
Linear Context-Free Rewriting Systems 
Linear context-free rewriting systems arose from the 
observation that a number of grammatical formalisms 
share two properties. 
1. Their derivation tree sets can be generated by a 
context-free grammar. 
2. Their composition operations are size-preserving, 
i.e., when two or more substructures are com- 
bined only a bounded amount of structure is 
added or deleted. 
136 
Examples of formalisms that. satisfy these condi- 
tions are head grammars \[8\], tree adjoining gram- 
mars \[6\], multicomponent tree adjoining grammars \[6\] 
and context-free hypergraph grammars. It was 
shown \[9\] that a system satisfying the above conditions 
generates languages that are semilinear and can be 
recognized in polynomial time. The definition of lin- 
ear context-free rewriting systems is deliberately not 
specific about the kinds of structures being manipu- 
lated. In the case of head grammars these are pairs of 
strings whereas tree adjoining grammars manipulate 
trees and context-free hypergraph grammars manipu- 
late graphs. 
In \[9\] size-preserving operations are defined for ar- 
bitrary structures in terms of properties of the cor- 
responding functions over the terminal yield of the 
structures involved. The yield is taken to be a tuple 
of terminal strings. We call the function associated 
with a composition operation the yield function of 
that operation. The yield function of Of of a com- 
position operation f gives the yield of the structure 
f(cl,ldots, cn) based on the yield of the structures 
el, • •., am. 
Let ~ be an alphabet of terminal symbols, f is an 
n-ary linear regular operation over tuples of strings 
in ~ if it can be defined with an equation of the form 
f((xl,1,..., xl,k,),..., (ran,l,..., xn,k,,)) ---- (tl,...,tk) 
where each k i > O, n >_ 0 and each ti is a string of 
variables (x's) and symbols in ~ and where the equa- 
tion is regular (all the variables appearing on one side 
appear on the other) and linear (the variables appear 
only once on the left and right). 
For example, the operations of head grammars can 
be define with the equations1: 
wrap((Xl, ~2), (Yl, Y2)) : (XlYl, Y2X2) 
concl((xl, x2) , (Yl, Y2)) = (xx, x2y, y2) 
C0n¢2((,~1, X2) , (Yl, Y2)) = (2?IX2Yl, Y2) 
Thus, we have 
wrap( (ab, ca), (ac, bc) ) = (abac, bcca) 
concl( (ab, ca), (ac, bc) ) = (ab, caaebc) 
conc2( (ab, ca), (ac, be)) = (abcaac, be) 
A generalized context-free grammar (gcfg) \[8\] 
is denoted G = (VN, S, F, P) where 
1These operations differ from (but are equivalent to) 
those used in \[8\] 
VN is a finite set of nonterminal symbols, 
S is a distinguished member of VN, 
F is a finite set of function symbols and 
P is a finite set of productions of the form 
A --+ f(A1,..., A,) 
where n > 0, f C F, and A, AI,...,Am C VN. 
With a grammatical formalism we associate an in- 
terpretation function m that maps symbols in F 
onto the formalism's composition operations. For ex- 
ample, in a typical head grammar the set F might 
include { W, el, C2} where re(W) = wrap, m(Cl) = 
concl and re(C2) = conc2. 
A formalism is a linear context-free rewriting 
system (lefts) if every grammar can be expressed as 
a gcfg and its interpretation function m maps sym- 
bols onto operations whose yield functions are linear 
regular operations. 
In order to simplify the remaining discussion we as- 
sume that m maps directly onto the yield functions 
themselves. 
The language L(G) generated by a gcfg G = 
(VN, S, F, P) with associated interpretation function 
m is defined as 
L(G) = 
where 
* A =:=V re(f) G 
ifA--~f0 EP 
* A ~ m(/)(tl,...,tn) G 
ifA --* f(A1,...,An) E P and 
Ai ~--~ ti (l < i < n). G 
We denote the class of all languages generated by 
lefrs as LCFRL. 
Deterministic Tree-Walking Transduc- 
ers 
A deterministic tree-walking transducer is an automa- 
ton whose inputs are derivation trees of some context- 
free grammar. The automaton moves around the tree 
starting at the root. At each point in the computation, 
depending on the label of the current node and the 
state of the finite state control, the automaton moves 
137 
up, down or stays at the current node and outputs a 
string. The computation ends when the machine tries 
to move to the parent of the root node. 
We denote a deterministic tree-walking trans- 
ducer (dtwt) by M - (Q, G, A, 6, q0, F) where 
Q is a finite set of states, 
G = (VN, VT, S, P) is a context-free grammar without 
e-rules, 
A is a finite set of output symbols, 
6 : Q × (VN U VT) ---+ Q × D × A* is the transition 
function where 
D = {stay, up} O {d(k) \[ k > 1 }, 
q0 E Q is the initial state and 
F C_ Q is the set of final states. 
A configuration of M is a 4-tuple (q, 7, r/, w) where 
q E Q is the current state, 7 is the derivation tree of 
G under consideration, r/is a node in 7 or T (where 1" 
can be thought of as the parent of the root ofT), and 
w E A* is the output string produced up to that point 
in the computation. We have 
(q, 7, r/, w) \['-M (qt, "\[, r/,, WW/) 
if the label of r/is X, ~f(q, X) = (q', d, w') such that 
when d = stay then T/' = r/, when d = d(i) then 7/' is 
the ith child of r/(if it exists), and when d = up then 
r/' is the parent of r/(T if r/is the root of 7). 
The output language OUT(M) of M is the set of 
strings: 
{weA*I (q0,7, r/r, e) b~/ (q f, 7, T, w), 
ql E F and 
7 is a derivation tree of G with root r/r } 
where F-~ is the reflexive transitive closure of \['-M" 
We denote the class of all languages OUT(M) where 
M is a dtwt as OUT(DTWT). 
Consider the dtwt 
M = ({qo, ql,q2, q3},G,{a,b,c,d},~f, qo,{q3}) 
where G = ({S},{e},S,{S-*A,A-~A,A-*e}) 
and the relevant component of 6 is defined as follows. 
6(q0, s) = (q0, d(1), e) 
6(q0, A) = (q0, d(1), a) 
6(ql, S) = (q2, d(1), e) 
6(q2, A) = (q2, d(1), c) 
6(q3, 5') -~ (q3, up, e) 
6(qo, e) = (ql, up, e) 
6(qz, A) = (qz, up, b) 
~f(q~, e) = (q3, up, e) 
6(q3, A) = (q3, up, d) 
It can be seen that OUT(M) = { anbnc'~d '~ In > 1 }. 
Equivalence 
In this section we outline a two part proof that 
OUT(DTWT) = LCFRL. 
OUT(DTWT) C_ LCFRL 
Consider a dtwt M = (Q, E, G, A, 6, qo, F) where G = 
(VN, VT, S, P). For convenience we assume that M is 
a dtwt without stay moves (see Lemma 5.1 in \[3\] for 
proof that this can be done). 
Given a derivation tree of G, and a node r/in this 
tree, we record the strings contributed to the output 
between the first and last visit to nodes in the subtree 
rooted at r/. These contributed terminal strings can 
be viewed as a k tuple where k is the number of times 
that the transducer enters and then leaves the subtree. 
For each production X --* X1 ...Xn in P and each 
p E Q we call 
C((X,p, .) -.+ (X1, e, 0)... (Xn, ¢, 0)) 
C((A, p, .) (XI, e, 0)... (Xn, e, 0)) simulates all sub- 
computations of M that start in state p at a node 
labelled X that has been expanded using the pro- 
duction X --* X1...Xn. The node labelled A may 
be visited several times, but each time the machine 
must be in a different state (otherwise, being deter- 
ministic, it would loop indefinitely). The sequence of 
visits is recorded as a string of states. The compo- 
nent of the rule that is underlined indicates which of 
the children or parent is currently being visited. The 
call C((X, a, ¢) -~ (Xl, al, il)... (Xn, an, in)) is made 
when a computation is being simulated in which the 
node labelled A has been visited \]a\[ times (\[a\[ de- 
notes the length of a) such that on the ith visit the 
machine was in the state indicated by the ith symbol 
in a. al,..., an are used in a similar way to encode 
the state of the machine during visits to each child 
node. ¢ is a string of terms that is used to encode the 
output produced between the first and last visit to the 
subtree rooted at the node labelled A. Ultimately, it 
has the form .tl ....-tk. where each ti encodes the 
composition of the ith component of the tuple. The 
notation used for each ti is identical to that used in 
the equations used to define lefts composition opera- 
tions given earlier, i.e., each ti is a string of output 
symbols and x's. il,...,in are used to encode the 
number of times that a given child has been visited 
from above. This gives the number of times the sub- 
tree rooted at that node has been visited and, hence, 
encodes which component of the tuple was completed 
most recently. Thus, for each j, 1 _< j _< n, the sim- 
ulation has moved from the parent to the jth child ij 
138 
times. This number is used to determine which com- 
ponent of the tuple derived from the jth node should 
contribute to the parent's current component. When 
a move is made from the parent node to the jth child 
we add the variable xj,/~+x to the term currently being 
constructed for the parent node. In other words, the 
next component of the parent output is the ij + l th 
component of its jth child. 
The call 
C((X, a, ¢) --* 
(X1, oq, ix)... (Xj, aj, ij)... (Xn, an, in)) 
sumulates the machine visiting the jth child of a node 
expanded using the rule X --~ X1 ... Xn. 
From M the gcfg G' is constructed such that G' = 
(V~, 5", F, P') where 
vk = {S'}u {(X,a) lXeVNUVTand 
non-repeating a e Q*} 
and the procedure C determines P' and F where for 
each production A -~ X1 ... Xn in P and each p E Q 
we call 
C((A,p, .) --* (Xx, c, 0)...(X~, e, 0)) 
In addition, for each a E VT and each p E Q we call 
C((a, p, .)) -~ 
C is defined as follows. 
Case 1. 
C((X, ap, ¢) ---* (X1, oq, ix)... (Xn, an, in)) 
Note that if n = 0 then X E VT, otherwise, X E VN. 
If 6(p, X) = (q, up, w) then 
(X, ap) --~ f((Xl, ~1),..., (Xn, otn)) E P' 
for a new function f E F where re(f) is defined by 
f((xl,...,mix),..., (xl,.:., mi,)) '= (tl,...,tk) 
where Cw. = 41 "..." tk'. (note that when ij = 0 for 
some j then (Xl,..., xij) will appear as e), in addition, 
for each p' in Q that does not appear in ap call 
C((X, o~pp', ew.) ---* (Xl, ~1, i1)... (Xn, O~n, in)) 
Note that • has been placed after ew. This indicates 
that we have finished with the current component of 
the tuple. 
Otherwise, if 6(p,X) = (q,d(j),w) and 1 _< j < n 
then call 
c((x, ap, ¢w=j,~j+x) 
(xt,oq,it)...(xj,ajq,# + 1)...(Xn,o~,~,i,O) 
Note that if Xj E VT then it is not possible for the 
machine to move down the tree any further. 
Case 2. 
c((x, ¢) --. 
(X1, (~1, il)... (Xj, ajp, ij)... (Xn, an, in)) 
If 6(p, Xj) = (q, up, w) then call 
(Xl, al, il)... (Xj, ajp, ij)... (Xn, an, in)) 
Note that ¢ will end with xj,ii and the ijth compoent 
of the yield at As. will end in w. 
Otherwise, if 6(p, Xj) = (q,d(k), w) then if Xj E VN 
for each p' in Q and not in aiP call 
c((x, a, ¢) --. 
(Xl, ot\], it)... (Xj, %pp', ij) . .. (Xn, an, in)) 
This simulates the next visit to this node (which must 
be from below) in the (guessed) state p'. 
In addition to the productions added by C, include 
in P~ the production S ~ ---. ( S, qootq! ) for each qi E F 
and a E Q* such that aootqi is non-repeating and 
/f(q, S) = (qI, up, w) for some w where q is the last 
symbol in q0a. 
A complete proof would establish that the following 
equivalence holds. 
(Aa) ~ (wt,...,w,) 
if and only if there is a derivation tree 7 of G with 
root ~?r labelled A such that a = at...an for some 
al,...,an E Q+ and for each i (1 < i < n) 
7, 7, f, 
where ai = pia\[ = a\['qi for some c~, a~' E Q*. 
Consider the application of this construction to ex- 
ample the dtwt given earlier. The grammar contains 
the following productions (where productions contain- 
ing useless nonterminals have been omitted). 
(S, qoqlq3) --~ A((A, qoqlq2q3)) 
139 
where fl((Xlj, Xl,2)) -- Xl,lX1,2 
(A, qoqlq2qa) --* f2((A, qoqlq2qa)) 
= 
(A, qoqlq2q3) --~ f3((e, qoq2)) 
where = 
(e, qoq2) ~ f40 
where 140 = (e, e). 
By renaming nonterminal we get the four produc- 
tions 
S --* fl(A) A -. f2(A) 
A ---* f3(e) e ---* f40 
LCFRL C_ OUT(DTWT) 
Consider the gcfg G -- (VN, S, F, P) and mapping m 
that interprets the symbols in F. Without loss of gen- 
erality we assume that no nonterminal appears more 
than once on the right of a production and that for 
each A E VN there is some rank(A) = k such that 
only k-tuples are derived from A. 
We define a dtwt M = (Q, ~, G ~, liT, 6, qo, F) where 
G ~ is a context-free grammar that generates derivation 
trees of G in the following way. A derivation involving 
the use of a production zr will he represented by a tree 
whose root is labelled by zr = A --* f(A1,..., Am) with 
n subtrees encoding the derivations from A1,..., An. 
The roots of these subtrees will be labelled by the 
n productions used to rewrite the A1,...,An. Let 
lhs(~r) = A and rhs(~r) = { AI,..., An }. 
The dtwt M walks around a derivation tree 7 of 
G' in such a way that it outputs the yield of 7. Each 
subtree of 7 rooted at a node ~/labelled by the produc- 
tion ~r will be visited on k = rank(lhsOr)) occasions by 
M. During the ith visit to the subtree M will output 
the ith component of the tuple. We therefore include 
in Q k states { 1,...,k} that are used to keep track 
of which tuple is being considered. This will gener- 
ally involve visiting children of y as determined by 
the equation used to define function used in 7r. Addi- 
tional states in Q are used to keep track of these visits 
as follows. When the lth child of T/ has finished its 
ruth component, M will move back up to y in state 
(Az,m). Since no nonterminal appears twice on the 
right of a production it is possible for M to determine 
the value of l from At while at y. 
For each production ~r = A --* f(A1,...,An) E P 
where f is interpreted as the function defined by the 
equation 
f((xX,1,.-.,Xl,kl),.-.,(Xnj,..-,Xn,k,))= (tl,...,tk) 
we include the following components in the definition 
of 6. 
For each i (1 < i < k) 
• if ti = wxl,m¢, where w is a possibly empty ter- 
minal string then let 
6(i, ~) = (m, down(O, w) 
• if ti = w (in which case it is time to move up the 
tree) let 
6(i, ~r) = (( lhs(Ir), i), up, w) 
For each B E rhs(~r) and each m, 1 <_ m <_ rank(B), 
let 
6((B, m), 7r) = (q, move, w) 
where (q, move, w) is determined as follows. For some 
unique I we know that B is the lth nonterminal on the 
right-hand side of 7r. There is a unique ti such that 
ti = ¢lXZ,mw¢2 where w is a possibly empty string of 
terminals. 
Case 1:¢2 is empty 
In this case the ith component of the current node is 
complete. Thus, q = (lhs(r), i) and move = up. 
Case 2:¢2 begins with the variable xv,m, 
In this case the machine M must find the m'th compo- 
nent of the/'th child. Thus, q = m' and move = d(l'). 
It should be clear that the start state q0 should be 
1 and the set of final states F = { (S, rank(S)) }. 
A complete proof would involve verifying that the 
following equivalence holds. 
(Aa) ~ (wl,...,Wn) 
if and only if there is a derivation tree 7 of G' with 
root ~r labelled 7r such that lhs(lr) = A and for each i 
(1 < i < n) 
(i, 7, ~/r, e) t-~4 ((A, i), 7, t, w~) 
We apply the construction to the grammar pro- 
duced in the illustration of the first construction. 
First, we name the productions of the grammar 
7rl = S --~ fl(A) ~r2 = A --* f2(A) 
140 
~3 = A ---* f3(e) 7r4 = e --* f40 
The construction gives a machine in which the func- 
tion 5 is defined as follows. 
di(1, rl) = (1, d(1), e) 
&(1, ~r2) = (1, d(1), a) 
5(2, ~2) = (2, d(1), e) 
5(1, 7rz) = (1, d(1), a) 
5(2, r3) = (2, d(1), c) 
5(1, ~r4) = ((e, 1), up, e) 
5(2, ~,) = fie, 2), up, ~) 
6((A, 1), rl) = (2, d(1), e) 
6((A, 2), 7rl) : ((S, 1), up, e) 
6((A, 1), r~) = ((A, 1), up, b) 
5((A, 2), 7r2) = ((A, 2), up, d) 
5((e, 1), 7rz) = ((A, 1), up, b) 
5((e, 2), r3) = ((A, 2), up, d) 
The context-free grammar whose derivation trees 
are to be transduced has the following productions. 
";l'l "~ 71"2 7l'1 -"+ 7r3 
We denote a hypergraph as a five tuple H 
( V, E, ~, incident, label) where 
V is a finite set of nodes, 
E is a finite set of edges, 
E is a finite set of edge labels, 
incident : E --* V* is the incidence function and 
label : E --+ ~ is the edge labelling function 
For example, in the above graph 
V = {vl,v2, vz, v4}, E = {el,e2,e3}, 
= { a, b, c}, incident(el) = (v2, vl, v4), 
i,,cide.t(e2) = (v4, vl), incident(e3) = (v3), 
label(e,) = a, label(e2) - b and label(e3) -- c. 
A string can be encoded with a string hyper- 
graph \[5\]. The string bcaab is encoded with the fol- 
lowing graph. 
71"2 ~ 71"2 71"2 ~ 71"3 71"3 ~ 7i'4 
Context-Free Hypergraph Grammars 
In this section we describe context-free hypergraph 
gramars since they are an example of a lcfrs involv- 
ing the manipulation of graphs, zThe class of string 
languages generated by context-free hypergraph gram- 
mars is equal to OUT(DTWT) \[3\] and the above result 
shows that they are also equal to LCFRS. 
A directed hypergraph is similar to a standard 
graph except that its (hyper)edges need not simply go 
from one node to another but may be incident with 
any number of nodes. If an edge is incident with n 
nodes then it is a n-edge. The n nodes that are inci- 
dent to some edge are linearly ordered. For example, 
in the figure below, dots denote nodes and labelled 
square boxes are edges. The edge labelled a is a 3- 
edge, the edge labelled b is a 2-edge and the edge 
labelled c is a 1-edge. When the number of nodes 
incident to an edge exceeds 2, numbered tentacles are 
used to indicate the nodes that are incident to the 
edge. The numbers associated with the tentacles com- 
ing from an edge indicate the linear order of the nodes 
that are incident to that edge. 2-edges are shown in 
the standard way and 1-edges can be used as a way of 
associating labels with nodes as shown. 
@ 
141 
b c a a b 
We denote a context-free hypergraph gram- 
mar (cfhg) as four tuple G = (VN, VT, S, P) where 
VN is a finite nonterminal alphabet, 
VT is a finite terminal alphabet, 
S E VN is the initial nonterminal and 
P is a finite set of productions e -* H where 
H = (V, E, VN O VT, incident, label) 
is a hypergraph and 
e E E is a nonterminal edge in H, i.e., label(e) E VN. 
Consider the application of a production e --* H to a 
graph H ~ at a node e p in H ~ with the same nonterminal 
label as e. The resulting graph is obtained from H ~ 
by replacing e ~ by the graph H with e removed from 
it. This involves merging of nodes. In particular, the 
ith node incident with e is merged with the ith node 
incident with e ~. We require that all edges with the 
same label have the same number of incident nodes. A 
derivation begins with a graph containing a single edge 
labelled S and no edges. A derivation is completed 
when there are no nonterminal nodes in the graph. 
The string language associated with a cfhg G is de- 
noted STR(G). The class of languages generated by 
all cfhg is denoted STR(CFHG). 
Due to lack of space, rather than a complete formal 
definition of cfhg derivations, we present an illustra- 
tive example. Consider the three productions shown 
below. Note that the edge on the left-hand-side of the 
production is indicated with a double box. 
1 
4 
a 
Below we show the steps in a derivation of the string 
aabbccdd involving these productions. Note that the 
set of graphs derived corresponds to the string lan- 
guage { anbncnd n I n > 0 }. 
D 
a 
d 
a 
b j° ~t 
C 
d 
a 
b 1 
C 
d 
a a 
° b 
"~..~£ 
C 
d d 
It is clear from their definition that cfhg satisfy the 
conditions for being a lcfrs given earlier. As has been 
observed \[3\] it is possible to represent the set of deriva- 
tions of a given cfhg with a set of trees that can be 
generated by a context-free grammar. The composi- 
tion operation of cfhg in which a node is replaced by 
a graph is clearly size-preserving since it does not in- 
volve duplication or deletion of an unbounded number 
of nodes or edges. 
Additional Remarks 
We end by elaborating on the relationship between 
lcfrs, dtwt and cfhg in terms of the following complex- 
ity measures. 
• The maximum of rank(A) nonterminals A of a 
gcfg. Let LCFRLk be the class of languages gen- 
erated by gcfg of some lcfrs whose nonterminals 
have rank k or less, i.e., derive at most k tuples. 
• The crossing number of a dtwt M. This is the 
maximum number of times that it visits any given 
subtree of an input tree. Let OUT(DTWTk) 
be the class of languages output by dtwt whose 
crossing number does not exceed k. 
• The maximum number of tentacles of the nonter- 
minals of a cfhg. Let STR(CFI-IGk) be the class 
of languages associated with cfhg whose nonter- 
minals have at most k tentacles. 
It has been shown (Theorem 6.1 in \[3\]) that 
OUT(DTWTk) = STR(CFHGg.k) = STR(CFHG2k+I) 
It can be seen from the above constructions that 
LCFRLk = OUT(DTWTk) 
= STR(CFHG2k) 
= STR(CFHG2k+I) 

References 
\[1\] A. V. Aho and J. D. Ullman. Translations on a 
context-free grammar. Inf. Control, 19:439-475, 
1971. 
\[2\] M. Bauderon and B. Courcelle. Graph expres- 
sions and graph rewritings. Math. Syst. Theory, 
20:83-127, 1987. 
\[3\] J. Engelfriet and L. Heyker. The string generat- 
ing power of context-free hypergraph grammars. 
J. Comput. Syst. Sci., 43:328-360, 1991. 
142 
\[4\] J. Engelfriet, G. Rozenburg, and G. Slutzki. Tree 
transducers, I systems, and two-way machines. J. 
Comput. Syst. Sci., 20:150-202, 1980. 
\[5\] A. Habel and H. Kreowski. Some structural as- 
pects of hypergraph languages generated by hy- 
peredge replacement. In STACS, 1987. 
\[6\] A. K. Joshi, L. S. Levy, and M. Takahashi. Tree 
adjunct grammars. J. Comput. Syst. Sci., 10(1), 
1975. 
\[7\] T. Kasami, H. Seki, and M. Fujii. General- 
ized context-free grammars, multiple context-free 
grammars and head grammars. Technical report, 
Department of Information and Computer Sci- 
ence, Osaka University, Osaka, Japan, 1988. 
\[8\] C. Pollard. Generalized Phrase Structure Gram- 
mars, Head Grammars and Natural Language. 
PhD thesis, Stanford University, 1984. 
\[9\] K. Vijay-Shanker, D. J. Weir, and A. K. Joshi. 
Characterizing structural descriptions produced 
by various grammatical formalisms. In 25 th meet- 
ing Assoc. Comput. Ling., 1987. 
\[10\] D. J. Weir. Characterizing Mildly Context- 
Sensitive Grammar Formalisms. PhD thesis, 
University of Pennsylvania, Philadelphia, PA, 
1988. 
