Decidability of EDT0L structural equivalence.
We show that a tree pushdown automaton can verify, for an arbitrary nondeterministically constructed structure tree t, that t does not correspond to any valid derivation of a given EDT0L grammar. In this way we reduce the structural equivalence problem for EDT0L grammars to deciding emptiness of the tree language recognized by a tree pushdown automaton, i.e., to the emptiness problem for context-free tree languages. Thus we establish that structural equivalence for EDT0L grammars can be decided effectively. The result contrasts the known undecidability result for ET0L structural equivalence.
Introduction
Context-free type grammars G 1 and G 2 are said to be structurally equivalent if, corresponding to
each syntax tree of G 1 producing a terminal word, the grammar G 2 has a syntax tree with the
same structure, and vice versa. The structure of a syntax tree t is the leaf-labeled tree obtained
from t by removing the nonterminals labeling the internal nodes. The importance of the notion of
structural equivalence for context-free grammars is due to the fact that it can be decided effectively
[12, 14, 18] whereas language equivalence is undecidable.
This work has been supported by the Natural Sciences and Engineering Research Council of Canada grants
OGP0041630, OGP0147224.
y Department of Computing and Information Science, Queen's University, Kingston, Ontario K7L 3N6, Canada.
Email: ksalomaa@cs.queensu.ca
z Department of Computer Science, University of Western Ontario, London, Ontario N6A 5B7, Canada. Email:
syu@csd.uwo.ca
Structural equivalence remains decidable also for parallel context-free (E0L) grammars [15, 16,
17, 25]. Surprisingly it was shown in [23] that when the parallel derivations are controlled by a
finite set of tables (in an ET0L grammar), structural equivalence is undecidable. We cannot even
decide whether an E0L grammar and an ET0L grammar having just two tables are structurally
equivalent.
Here we show that structural equivalence becomes decidable if the tables of the grammars are
restricted to be homomorphisms, that is, we have EDT0L grammars. Thus for the structural
equivalence problem we cross the borderline between undecidable and decidable when restricting
the tables of the grammar to be homomorphisms. Our proof uses automata theoretic methods
but differs considerably from the automata theoretic decidability proofs for E0L structural equivalence
[25] and ET0L strong structural equivalence [10]. The E0L structure trees, as well as ET0L
structure trees augmented with the information about the control-sequence used, can be recognized
deterministically bottom-up using a tree automaton model for which equivalence is decidable. This
appears not possible for EDT0L structure trees since the arbitrary choice of the sequence of tables
makes the derivation inherently nondeterministic.
We reduce EDT0L structural equivalence to the emptiness problem for the tree pushdown
automata of Guessarian [8]. These automata recognize exactly the context-free tree languages and
emptiness can be decided algorithmically. We show that, given EDT0L grammars G 1 and G 2 , a
tree pushdown automaton can verify that a nondeterministically guessed structure tree of G 1 does
not correspond to any valid derivation of G 2 .
The decidability proof relies strongly on nondeterminism and an actual algorithm following the
proof requires multiple exponential time. It is seen easily that EDT0L structural equivalence is
PSPACE-hard, so one cannot expect to find a very efficient algorithm. It has been shown in [24]
that E0L structural equivalence is hard for deterministic exponential time. For the EDT0L case
we have not obtained an exponential time lower bound.
Preliminaries
We assume that the reader is familiar with the basics of formal language theory [29]. We briefly
recall some definitions concerning parallel context-free type grammars and tree automata. For
more information regarding parallel grammars the interested reader is asked to consult [21], and
regarding tree automata we refer the reader to [5, 6].
The cardinality of a finite set A is denoted by #A and the power set of A is -(A). Sometimes
we identify a singleton set fag with a. The sets of positive and nonnegative integers are denoted,
respectively, by IN and IN 0 .
The set of (nonempty) finite words over A is A   denotes the empty word. The length
of w 2 A   is jwj. Let A i , be finite sets. We define the mappings \Pi A 1
by setting for
A tree domain D [6] is a nonempty finite subset of IN   that satisfies the following two conditions:
(i) If u 2 D, then every prefix of u is in D.
(ii) For every u 2 D there exists rank D (u) 2 IN 0 such that ui 2 D for
0, the node u has no successors.)
An A-labeled tree is a mapping t : dom(t) \Gamma! A, where dom(t) is a tree domain. A node u 2 dom(t)
is said to be labeled by t(u) 2 A. A node v is a successor (respectively, an immediate successor) of
We assume that notions such as the height,
the root, a leaf, an internal node, and a subtree of a tree t are known. The height of t is denoted
hg(t). We use the convention that the height of a one-node tree is zero. The subtree of t at node
u is t=u.
By the level of a node u 2 dom(t) we mean the distance of u from the root, i.e., juj. Clearly,
the maximal level of a node of t is hg(t). The tree t is said to be balanced if all leaf nodes of t have
the same level. The set of level k subtrees of t, sub k (t), 0 - k - hg(t), is defined as
Note that sub k (t) is a set of trees as opposed to a set of occurrences of subtrees. Thus sub k (t)
contains only one copy of each tree t 0 that occurs as a subtree defined by a level k node of t. Also
ftg.
In our decidability proof we use the top-down tree pushdown automaton model of Guessarian [8].
Below we give a brief informal description of this model which will be sufficient for our purposes.
An interested reader can find the formal algebraic definition in [6, 8]. A tree pushdown automaton
A is an extension of a finite tree automaton where each copy of the finite-state control has access to
an auxiliary pushdown store. The automaton begins the computation at the root of the input tree,
in a given initial state q 0 and with an initial symbol in the pushdown store. When being in a state q
at a node u labeled by b in the input tree and having Z as the topmost stack symbol, depending on
the tuple (q; b; Z), A can either (i) change the internal state and pop Z from the stack, (ii) change
the state and push some symbol to the stack, or (iii) go to the m immediate successor nodes of u
in some states q sending to each of the m nodes a copy of the pushdown stack. (The node
u is assumed to have rank m.) The automaton accepts an input tree t if (in some nondeterministic
it reaches all leaves of t in an accepting state. The tree language recognized by A is
denoted T (A).
In general, the automata of [8] can employ a tree structure in the stack. The automaton model
described above is the so called restricted tree pushdown automaton of [8]. Both the restricted
and general tree pushdown automata recognize exactly the family of context-free tree languages
[3, 4, 6, 20]. Given a context-free tree language T (in terms of a tree pushdown automaton or a
context-free tree grammar), we can effectively construct an indexed grammar that generates the
yield of T . Since emptiness is decidable for indexed grammars [1, 2], we have the following result.
Proposition 2.1 We can decide effectively whether the tree language recognized by a given tree
pushdown automaton is empty.
3 Structural equivalence
We recall and invent some notations concerning parallel context-free grammars [21] and the structure
trees of their derivations [23, 24].
An ET0L grammar G is a tuple
(1)
where V is a finite alphabet of nonterminals, \Sigma is a finite alphabet of terminals, s is the
initial nonterminal, and H is a finite set of tables. A table h 2 H is a finite set of rewrite rules
. (We do not allow rewriting of terminals.) The grammar G
is an EDT0L (deterministic ET0L) grammar if every table h 2 H contains exactly one rule with
left side a, for each nonterminal a 2 V . Thus, h is a morphism V   \Gamma! (V [ \Sigma)   and h(a) denotes
the right side of the rule of h having the nonterminal a as the left side. The grammar G is an E0L
contains only one table. The grammar is said to be propagating if the right side of
any production is not the empty word, i.e., for all h 2 H and a
In this paper we will be dealing mainly with the structure trees of EDT0L derivations. Below
we define structure trees for arbitrary ET0L grammars since the definition is not essentially simpler
in the deterministic case. In the remainder of this section, G is always an ET0L grammar as in (1).
Let FG denote the set of (V [ \Sigma [ -trees. Here - is a new symbol that will be used to label nodes
corresponding to the empty word. We define the parallel derivation relation of G, ! par
as the union of relations ! par
defined as follows. Let
is obtained from t 1 as follows. Assume that t 1 has m
leaves
m. (Note that if some leaf of t 1 is labeled by a
terminal, the derivation cannot be continued from t 1 .) For each
choose a rule
(2)
a i
2 the node u i has k i successors
labeled respectively by the symbols a i
. If t 1 2 the node u i has
one successor labeled by the symbol -. If t 1
-, then u i is a leaf of t 2 .
We denote by t 0 the singleton tree with the only node labeled by the initial nonterminal s 0 .
The set of syntax trees S(G) of G is defined by
A syntax tree t 2 S(G) is terminal if all leaves of t are labeled by elements of \Sigma [ -
-. The set of
terminal syntax trees of G is denoted TS(G).
In case G is an EDT0L grammar, the rule (2) is determined uniquely by the table h. We call
words over the alphabet H control-sequences. Given an EDT0L grammar G and a control-sequence
by G(!) the syntax tree obtained from the
initial nonterminal by applying the sequence of tables specified by !. Thus G(!) is the unique
tree t such that
if a tree t as in (3) exists, and otherwise G(!) is undefined.
If G is propagating, then in every syntax tree t of G all paths from the root to a leaf have
the same length, i.e., t is balanced. For non-propagating grammars all paths from the root to
a leaf labeled by an element of V [ \Sigma have the same length. Note that our definition does not
allow the rewriting of terminal symbols, i.e., we assume that the grammars are synchronized [21].
This is not a restriction since an arbitrary E(D)T0L grammar can be easily transformed into
a synchronized E(D)T0L grammar in such a way that the transformation preserves structural
equivalence of grammars. The transformation (for E0L grammars) is explained in [15].
For obtained by catenating, in the natural
left-to-right order of the leaves, the labels of the leaves of t. The yield of a syntax tree t is defined
as
is the morphism defined by setting e - (a) = a for a
and e -
-.
For a syntax tree t, yield(t) is the sentential form generated by G in the derivation corresponding
to t. The language L(G) generated by G consists of the terminal words generated by G, i.e.,
Clearly the above definition is equivalent to the standard definition of the language generated by
an E(D)T0L grammar [21].
The structure of a syntax tree t 2 S(G), str(t) is the tree obtained from t by relabeling each
internal node with oe, where oe is a new symbol not in V [ \Sigma. We denote
Elements of STS(G) are called (terminal) structure trees of G. When G is known, we sometimes
speak simply about (\Sigma-)structure trees since the leaves are labeled by elements of \Sigma. Note that the
rules of G determine the maximal number of immediate successors of any node of a structure tree
of G. Thus, of course, the alphabet \Sigma does not by itself determine the set of \Sigma-structure trees.
Grammars G 1 and G 2 are said to be language equivalent if L(G 1 It is well known
that language equivalence is undecidable already for context-free grammars. Here we shall consider
the following two more restricted notions of equivalence. Let G 1 and G 2 be ET0L grammars. The
grammars G 1 and G 2 are
ffl structurally equivalent if STS(G 1
ffl syntax equivalent if are equal modulo a renaming of the nonterminals.
Note that syntax equivalence implies structural equivalence, and structurally equivalent grammars
in turn are always language equivalent. Syntax equivalence is incomparable with the notion of
strong structural equivalence [10] for ET0L grammars. Both syntax and structural equivalence
are decidable for context-free and E0L grammars [7, 12, 14, 15, 18, 25]. (We have not formally
defined these notions for sequential context-free grammars here, but the definitions are analogous
to the parallel case.) Syntax equivalence and strong structural equivalence are decidable also for
ET0L grammars but ET0L structural equivalence is undecidable [10, 23]. Here we will consider the
structural equivalence problem for the deterministic ET0L grammars.
4 The main result
We show that EDT0L structural equivalence can be decided effectively. First we introduce some
notations concerning the width of trees. Intuitively, a structure tree is said to have width M if it
has at most M distinct subtrees at any level.
Definition 4.1 A set of \Sigma-structure trees is said to have subtree-width M (2 IN) if,
for all have at most M distinct subtrees at level k,
i.e.,
In the above definition, note that sub k (t j ) is a set of (\Sigma [ foeg)-labeled trees, i.e., its elements
do not consist of occurrences of subtrees in t j . Note also that the subtree-width M does not need
to be the minimal number of distinct subtrees at any given level, i.e., if
then it has width M 0 for all M 0 - M .
We code the structure of an arbitrary derivation of an EDT0L grammar G 1 as a string. Then
using the string encoding in its stack, a tree pushdown automaton can verify in one computation that
no control-sequence of another grammar G 2 generates the same structure tree. The construction
relies essentially on the fact that the failure of an EDT0L derivation with respect to a given control-
sequence can be checked by following only one (nondeterministically chosen) path of the tree.
Lemma 4.1 Let be an EDT0L grammar. Then there exists M 2 IN such that,
for every control-sequence ! 2 H   , the structure tree str(G(!)) has width M .
Proof. Since the tables of H are homomorphisms, it follows that always when nodes
dom(G(!)) have the same length and are labeled by the same nonterminal, then G(!)=u
choosing that str(G(!)) has width M . 2
Structure trees having constant subtree-width can be coded as strings where the ith symbol
from the left codes the information which of the level i subtrees are direct descendants of which of
the level nodes. The ith symbol also codes the order of occurrences of level i subtrees. The
number of distinct level i subtrees is bounded by a constant and, furthermore, we need to consider
only a constant number of level nodes that correspond to pairwise different subtrees.
Below we define the above described coding of structure trees having subtree-width M and
prove a regularity property of such codings (in Lemma 4.3) for propagating EDT0L grammars
only. The restriction to propagating grammars is done just to avoid unnecessarily complicated
notations. Afterwards we explain how the result can be straightforwardly extended for grammars
allowing erasing productions.
Definition 4.2 Let propagating EDT0L grammar and let
For each M 2 IN we define the
set\Omega\Gamma M) to consist of tuples
and - is a mapping of
j such that
every element of occurs in some tuple -(j);
The set of final
f (M) is defined to consist of tuples
and - is a mapping of into
. Note that here \Sigma j is the set
of ordered j-tuples of elements of \Sigma (and not the set of strings of length j).
A sequence W in \Omega\Gamma M)
is said to be well-formed if m
Consider an s-tuple of structure trees denotes the structure
tree where the level one subtrees, from left to right, are t . (This is just the standard algebraic
notation for trees where we allow the symbol oe to have variable arity.)
Corresponding to a well-formed sequence W as in (7) we define inductively an m 1;1 -tuple of
\Sigma-structure trees \Xi(W ). We say that the well-formed sequence W represents \Xi(W ). First a final
represents the m 1 -tuple of structure trees
For the inductive definition, denote by W 0 the suffix of W obtained by deleting the first symbol
assume that
Note that m since W is well-formed. Denote - 1
Example 4.1 Let is the tree given in Figure 1. Choose
A
A
A
A A
#c
c
c
c
c
c
c c
A
A
A
A A
a b b b a b
oe oe oe oe
oe oe
oe

Figure

1.
The following lemma can be proved using induction on the maximal height of the trees t
Lemma 4.2 Let M 2 IN be fixed. Let be a set of \Sigma-structure trees having subtree-width
M such that max 1-i-m there exists a well-formed sequence W 2 \Omega\Gamma M)
as in (7) such that
Furthermore, m i;1 is the cardinality of the set of level
A word W 2 \Omega\Gamma M)
\Omega f (M) is said to be simple if the first symbol of W is of the form (1; m;-),
. If W is simple and well-formed, then \Xi(W ) is a one-tuple (t) where t is a \Sigma-structure tree
and, in practice, we identify \Xi(W ) with t.
As an immediate consequence of Lemma 4.2 we have:
Corollary 4.1 For every \Sigma-structure tree t having subtree-width M there exists a simple well-formed
sequence W 2 \Omega\Gamma M)
\Omega f (M) such that \Xi(W t.
The following lemma states that given a simple well-formed sequence W 2 \Omega\Gamma M)
\Omega f (M) and
a control-sequence ! of an EDT0L grammar G, a finite automaton can determine whether or not
Lemma 4.3 Let propagating EDT0L grammar and M 2 IN. Let the
alphabets
and\Omega f (M) be as in Definition 4.2. We denote by L the set of words - 2
such that
\Omega f (M) is simple and well-formed,
Here we denote the mappings \Pi
simply by \Pi i , 2.
We claim that L is a regular language.
Proof. Condition (i) can be easily verified by a finite automaton. Hence it is sufficient to show
that given - 2
satisfying (i), a finite automaton A can verify whether
or not (ii) holds. (Note that if (i) does not hold, then \Xi(\Pi 1 (-)) is not necessarily defined or may
denote an ordered tuple of trees.)
The set of states of A is
and the initial state is fs 0 g. Assume that A is in a state (U
and reading an input symbol
goes to the rejecting state rej. From our construction it follows that this is
possible only when condition (i) does not hold. Assume then that
then A goes to the accepting state acc. Also, A goes to the accepting state acc if for some x 2 U i ,
After this A reads the rest of the input verifying only that (i) holds.
The remaining possibility is that for all x 2 U is of the form (s
. In this case after reading the symbol
goes to the state (Z where the sets Z are
constructed as follows. For each and each x 2 U i do the following. If
then add the element a to the set Z s j , that each of the sets Z
will be nonempty because - satisfies the condition (5).
Intuitively, U i consists of all elements of V that the derivation of G (following the morphisms
read so far in the second components of the input) reaches at nodes corresponding to the
ith subtree representative at this, say the kth, level of \Xi(\Pi 1 (-)). Thus if condition (8) holds, the
derivation reaches some level k node u of \Xi(\Pi 1 (-)) with a symbol a 2 V such that the number
of immediate successors of u is not equal to jh(a)j. If condition contains a
terminal symbol. Thus a derivation using next the table h cannot have the structure \Xi(\Pi 1 (-))
and condition (ii) holds. The case where conditions (8) and (9) do not hold corresponds to the
situation where the parallel derivation step determined by h at level k does not immediately violate
the structure of the tree. Then the sets Z are constructed to consist, respectively, of all
nonterminals that will appear in the m 2 subtree representatives at the following level.
It remains to define the operation of A when it reaches a final symbol [(m
H] in a state (U Following the above idea this is done so that A accepts exactly then
when the derivation step h produces for some leaf representative b 2 \Sigma a wrong terminal symbol
(or a nonterminal).
The possibility corresponds again to a situation where (i) does not hold. We need to
consider only the possibility
then the derivation step h produces correct terminal symbols at all leaves. This means that (ii)
does not hold and A rejects. On the other hand, A enters the accepting state if for some x 2 U i ,
The above Lemma 4.3 was formulated and proved for propagating grammars only. However,
exactly the same proof works also for general EDT0L grammars: the possibility of having erasing
productions just adds at most one more subtree representative to each level of the structure tree.
We can modify Definition 4.2 so that in the symbols (m (as in (4)) - is a partial function
where -(i) is undefined if i represents a node having - as the immediate successor (or in such cases
-(i) is defined to be a new symbol not belonging to g.) The proof of Lemma 4.3 is then
simply modified by dividing the conditions (8) and (9) into cases depending on whether -(i) is
defined or not. Thus we can prove the following:
Lemma 4.4 The statement of Lemma 4.3 holds without the assumption that G is propagating.
Now we can show that a tree pushdown automaton can in a single computation verify whether
all possible derivations of a given EDT0L grammar violate a given structure tree of constant width.
Lemma 4.5 Let G be EDT0L grammars. Let M be a constant guaranteed
for G 1 by Lemma 4.1. Then we can effectively construct a tree pushdown automaton A such
that only if there exists
such that t has width M .
Proof. Denote k. The tree pushdown automaton A receives as inputs trees where each
internal node has exactly k immediate successors. The internal nodes are labeled by a symbol a 0 .
The set of stack symbols is (\Omega\Gamma M)
Assume that
Then the automaton A accepts the balanced k-ary input tree of
At the beginning of the computation, A nondeterministically pushes into
the stack a word (ff
(The top of the stack is to the left.)
Intuitively, the stack contents is guessed so that
\Omega f (M)) is simple
and well-formed and it satisfies the following property. If we denote
is as in (11). By Corollary 4.1, there exists W satisfying (12).
When reading an input symbol, A always pops the topmost stack symbol and the remaining
stack contents is forwarded to the k successor nodes. After the initial nondeterministic guesses A
does not push any more symbols into the stack.
The states of A consist of two components that operate in parallel. The first component verifies
that the condition (12) holds. As in the proof of Lemma 4.4 we see that this can be done using
only a finite-state memory. The first component operates identically on all paths of the input tree,
that is, it ignores the input symbols and treats the initial stack contents as input.
On the path to a leaf of the input, 1 the second component
of A verifies that
Again from the proof of Lemma 4.4 it follows that this is possible using the finite-state control of
A. The second component of A ignores the second components h of the stack symbols.
Hence, on different paths of the input A verifies that \Xi(W ) is not the structure of a syntax tree
control-sequence ! 0 of length verifies that \Xi(W ) 62 STS(G 2 ). On the
other hand, each branch of the computation has to consume the entire stack so an accepted input
tree is necessarily balanced. Thus A accepts some input tree if and only if there exists a tree t such
that (10) holds and t has subtree-width M . 2
Note that in the proof of Lemma 4.5 it is essential that the guessed instance of t 2 STS(G 1 ) in
the pushdown stack has a string encoding, although the general tree pushdown automaton model of
[8] allows, in fact, trees also in the stack. It can be shown that a tree pushdown automaton cannot
nondeterministically push a balanced tree of arbitrary height into the stack [22], so one could not
directly store an arbitrary t 2 STS(G 1 ) in the tree stack at the beginning of the computation.
Furthermore, simulating the derivations of G 2 given by different control-sequences directly on the
tree t would have the following problem. The paths leading to "failure of the derivation of G 2 in
t" may branch out earlier than the corresponding control-sequences branch out in the input tree.
More specifically, the tree pushdown automaton A has to find, for each control-sequence ! of G 2 ,
at least one path - ! in t that leads to failure. The control-sequences correspond to different paths
in the input and it is, in general, possible that two control-sequences have a very long
common prefix whereas the corresponding paths
in t branch out already at the root
of t. Situations like this do not cause problems when A has a string encoding \Xi(W ) of t in the
pushdown stack. Then A can simulate on all paths of the input all distinct subderivations of G 2
within the structure of t.
Combining Lemmas 4.1 and 4.5 and Proposition 2.1 we have proved the following result. Note
that the constant M in Lemma 4.1 is independent of the control-sequence chosen.
Theorem 4.1 For given EDT0L grammars G 1 and G 2 we can decide effectively whether or not
Exactly as in the proof of Lemma 4.5, for given EDT0L grammars G 1 and G 2 the nonemptiness
of can be reduced to deciding whether a tree pushdown automaton recognizes a
nonempty tree language. Since the number of nonterminals of G 1 and G 2 is finite, we have a new
proof for the decidability of the syntax equivalence. The result follows also from [23].
Theorem 4.2 Syntax equivalence is decidable for EDT0L grammars. 2
5 Discussion and open problems
The decidability results for syntax equivalence, structural equivalence and strong structural equivalence
of E(D)(T)0L grammars are summarized in Table 1. In the table D stands for "decidable"
and U for "undecidable". The decidability of strong structural equivalence for ET0L grammars is
proved in [10]. For E0L grammars, this notion coincides with structural equivalence. Language
equivalence is naturally undecidable for all the cases. Note that the E0L and EDT0L language
families are incomparable.
Syntax equiv. Structural equiv. Strong struct. equiv.
E0L D D D
EDT0L D D D
ET0L D U D

Table

1: Decidability of syntax and [strong] structural equivalence.
The proof of Theorem 4.1 gives only a multiple exponential time algorithm for EDT0L structural
equivalence. We do not know what is the exact complexity of the problem. The deterministic
exponential time hardness result obtained in [24] for E0L structural equivalence cannot be used, at
least not directly, to prove a similar lower bound for the complexity of EDT0L structural equiva-
lence. On the other hand, we cannot expect to obtain an efficient algorithm for the EDT0L case
since it is known that already the structural equivalence problem for linear grammars is PSPACE-complete
[9], and structural equivalence for linear grammars is easily logspace reducible to EDT0L
structural equivalence. Note that when the sentential forms have only one nonterminal (or any
constant number of occurrences of nonterminals), an EDT0L grammar can simulate a context-free
derivation simply by having a different table for each rule.
Intuitively, the decidability proof of the previous section relies on the following two properties
of EDT0L derivations:
(i) the current nonterminal and the remaining control-sequence determine uniquely a subderivation

(ii) all control-sequences generate the structure tree one level at a time.
These properties enabled us to produce a string encoding W of a structure tree such that the failure
of all possible control-sequences to produce this structure can be verified by a finite automaton that
reads W and the control-sequence in parallel.
The necessity of both conditions (i) and (ii) can be illustrated by considering the Indian parallel
grammars. An IP grammar is a context-free grammar with the derivation relation defined so
that at each derivation step one rewrites all occurrences of one (nondeterministically chosen) non-terminal
b in the given sentential form using the same rule with left side b. The other nonterminals
are not rewritten. For the formal definition the reader may consult [2, 19, 26, 27]. It is well known
that languages generated by IP grammars are strictly included in the EDT0L languages.
When the sequence of rules used in a derivation of an IP grammar is viewed as a control-
sequence, the IP grammars clearly have the above property (i). However, different sequences of rules
can generate distinct parts of a given structure tree in completely different order, and no analogy
of condition (ii) seems to hold for IP grammars. Thus in spite of the fact that EDT0L grammars
are strictly more powerful than IP grammars in terms of the family of generated languages, it
does not appear possible to use the proof method of the previous section to decide the structural
equivalence problem for IP grammars. We conjecture that IP structural equivalence is decidable.
For the E0LIP grammars of [11] structural equivalence can be shown to be decidable exactly as
in the proof of Theorem 4.1. (E0LIP grammars combine the Indian parallel and E0L rewriting
mechanisms: at each derivation step all occurrences of every nonterminal are rewritten using the
same rule.)
Russian parallel (RP) grammars [2, 13, 28] extend IP grammars by allowing also (sequential)
context-free derivation steps. The decidability of the RP structural equivalence problem remains
open.



--R

An extension of the context-free case
Regulated rewriting in formal language theory.
IO and OI
Grammars with macro-like productions
Tree automata (Akad'emiai Kiad'o
in: Handbook of Formal Languages
System Sci.
Pushdown tree automata

The strong equivalence of ET0L grammars
A study in parallel rewriting systems
A characterization of parenthesis languages
On some grammars with global productions (in Russian)

A normal form for structurally equivalent E0L grammars
Defining families of trees with E0L grammars
Simplifications of E0L grammars

Some classifications of Indian parallel languages
Mappings and grammars on trees
The Mathematical Theory of L Systems (Academic Press
Deterministic tree pushdown automata and monadic tree rewriting systems

Complexity of E0L structural equivalence
Decidability of structural equivalence of E0L grammars
Parallel context-free languages
Parallel context-free languages
Decomposition theorems for various kinds of languages parallel in nature
Theory of Computation (John Wiley
--TR
Deterministic tree pushdown automata and monadic tree rewriting systems
Some classifications of Indian parallel languages
Decidability of structural equivalence of EOL grammars
Defining families of trees with E0L grammars
Tree languages
Parenthesis Grammars
Theory of Computation
Regulated Rewriting in Formal Language Theory
Mathematical Theory of L Systems
Structural Equivalences and ET0L Grammars (Extended Abstract)
formal languages;tree pushdown automata;parallel grammars