Gecseg Tree Automata
Gecseg Tree Automata
i
and some relevant references are given to help an interested reader get started on them.
I thank Heiko Vogler and Zoltán Fülöp for some important additions to the bibliography.
ii
Hungarian Academy of Sciences, the János Bolyai Mathematical Society, the University
of Szeged, and the University of Turku. Our work was also furthered by a possibility for
the first-named author to spend a term at the Tampere University of Technology. For
this thanks are due Professor Timo Lepistö.
iii
Contents
Prefaces i
1 PRELIMINARIES 5
1.1 Sets, relations and mappings . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Universal algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Terms, polynomial functions and free algebras . . . . . . . . . . . . . . . . 16
1.4 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.5 Finite recognizers and regular languages . . . . . . . . . . . . . . . . . . . 27
1.6 Grammars and context-free languages . . . . . . . . . . . . . . . . . . . . 35
1.7 Sequential machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
1.8 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
1
Contents
Bibliography 207
Index 225
5 APPENDIX 233
2
NOTES TO THE READER
Within each section, there is one counter which is incremented by each of the environ-
ments definition, lemma, theorem, corollary, and example. The end of a proof or an
example is indicated by the mark ✷. It appears immediately after a theorem, lemma or
corollary if this is not followed by a proof. The references to the literature are by the
author(s) and the number with which the publication occurs in the Bibliography. In a
few cases we refer to a book mentioned at the end of Chapter 1.
3
1 PRELIMINARIES
In this chapter we shall review some basic concepts and results from the theories of
automata, formal languages, and universal algebras. It is reasonable to assume that
a potential reader of this book already knows something about automata and formal
languages. On the other hand, we do not presuppose any knowledge of universal algebra.
These two assumptions suggested the styles and extents of the following seven sections.
Section 1.1 (Sets, relations and mappings) may be skimmed through for terminology
and notation.
Sections 1.2 and 1.3 present the required universal algebraic concepts and results.
These are not many, but they should be mastered well as the very basic concepts of the
theory of tree automata are defined in terms of universal algebra. We have tried to make
the book self-contained in this respect, but a reader who wants to pursue further the
algebraic aspects of the theory should certainly consult one of the references on universal
algebra.
The lattice theory presented in Section 1.4 is less important here, and the reading of
this section may be postponed until needed.
Sections 1.5, 1.6 and 1.7 survey some of the most essential facts about finite recognizers,
regular languages, context-free grammars, and (generalized) sequential machines. A
reader less familiar with these matters would do wisely to look up these subjects in some
of the references given at the end of the chapter.
(i) A ⊆ B means that the set A is a subset of the set B. Proper inclusion is denoted
by A ⊂ B.
(iv) The power set of a set A, i.e., the set of all subsets of A, is denoted by pA.
(vi) The set {x ∈ A | P1 (x), . . . , Pk (x)} of all elements x in A with the properties P1 ,
. . . , Pk may also be written as {x | P1 (x), . . . , Pk (x)} when A is understood from
5
1 PRELIMINARIES
the context. We shall use this notation in the following more general form, too.
Suppose f (x1 , . . . , xm ) is an object defined in some way in terms of the objects x1 ,
. . . , xm . Then
{f (x1 , . . . , xm ) | P (x1 , . . . , xm )}
is the set of all such objects constructed from objects x1 , . . . , xm satisfying the
condition P (x1 , . . . , xm ). Furthermore, we use
(vii) If there is no danger of confusion, we may write simply a for the one-element set
{a}. Of course, we should not write ∅ for {∅}.
(ii) “(∃x ∈ A) P (x)” states that there exists an x in A such that P (x) holds.
(iv) “P ⇐⇒ Q” states that the conditions P and Q are equivalent, i.e., both of them
hold or then neither one holds.
(v) “P ∧ Q” is the statement that both P and Q hold. Similarly, “P ∨ Q” states that
at least one of P and Q holds.
The numbers dealt with here are always integers and mostly even non-negative integers.
When we write “. . . for all n ≥ 1” we mean, in fact, “. . . for all integers n ≥ 1”. The
set of all integers is denoted by Z, the set of the natural numbers 1, 2, . . . by N, and
the set of all non-negative integers by N0 .
Let A and B be sets and ̺ ⊆ A × B a (binary) relation from A to B. The fact that
(a, b) ∈ ̺ (a ∈ A, b ∈ B) is also expressed by writing a̺b or a ≡ b (̺). The opposite case
may be expressed by a6 ̺ b or by a 6≡ b (̺). For any a ∈ A, we put
a̺ = {b ∈ B | a̺b}.
6
1.1 Sets, relations and mappings
Obviously,
b̺−1 = {a ∈ A | a̺b}
and
B1 ̺−1 = {a ∈ A | (∃b ∈ B1 )a̺b}
for all b ∈ B and B1 ⊆ B. The domain of ̺ is the subset dom(̺) = B̺−1 of A, and its
range is the subset range(̺) = A̺ of B.
The product or composition of two relations ̺ ⊆ A × B and τ ⊆ B × C is the relation
In this definition we used the short form a̺bτ c to express the fact that a̺b and bτ c.
Often we write ̺τ for ̺ ◦ τ . The product of relations is associative. We note also the
equality (̺ ◦ τ )−1 = τ −1 ◦ ̺−1 .
Consider now (binary) relations on a set A, i.e. subsets of A × A. These include the
diagonal relation δA = {(a, a) | a ∈ A} and the total relation ιA = A × A. For any
relation ̺ on A we define the powers ̺n (n ≥ 0) with respect to the product of relations:
1◦ ̺0 = δA and
◦ n+1 n
2 ̺ =̺ ◦̺ for n ≥ 0.
(a) reflexive if δA ⊆ ̺,
(d) transitive if ̺2 ⊆ ̺.
The intersection of any reflexive relations (on a given A) is reflexive, and the intersec-
tion of transitive relations is transitive. Thus there exists for every ̺ ⊆ A × A a unique
minimal reflexive, transitive relation ̺∗ containing ̺. It is called the reflexive, transitive
closure of ̺. One verifies easily that
̺∗ = δA ∪ ̺ ∪ ̺2 ∪ ̺3 ∪ . . . ,
a = a1 ̺ a2 ̺ a3 . . . an−1 ̺ an = b
7
1 PRELIMINARIES
a̺ = b̺. We shall also write a/̺ for a̺ and extend this notation to subsets A1 ⊆ A
and n-tuples a = (a1 , . . . , an ) of elements of A (n ≥ 1): A1 /̺ = {a/̺ | a ∈ A1 } and
a/̺ = (a1 /̺, . . . , an /̺). The quotient set of A modulo ̺ is A/̺. Obviously, A/̺ is
a partition on A, that is, every element of A belongs to exactly one ̺-class. On the
other hand, every partition on A can be obtained this way as the quotient set from a
unique equivalence relation and there is a natural one-to-one correspondence between
the partitions on A and E(A). The cardinality of A/̺ is called the index of ̺ ∈ E(A).
If |A/̺| is finite, we say that ̺ is of finite index. We say that ̺ ∈ E(A) saturates the
subset H ⊆ A if H̺ = H, i.e., if H is the union of some ̺-classes.
A mapping or a function from a set A to a set B is a triple (A, B, ϕ), where ϕ ⊆ A × B
is a relation such that for every a ∈ A there exists exactly one b ∈ B satisfying aϕb. As
usual we write ϕ : A → B and say that ϕ is a mapping from A to B. If aϕb (a ∈ A,
b ∈ B), b is called the image of a and a an inverse image of b. This is expressed by
writing b = aϕ, b = ϕ(a) or ϕ : a 7→ b. For a subset A1 of A we also use the two notations
A1 ϕ and ϕ(A1 ) for the set {aϕ | a ∈ A1 }. The converse ϕ−1 of ϕ is always defined as
a relation (⊆ B × A), but it is usually not a mapping from B to A. Again, ϕ−1 (B1 )
will sometimes be used instead of B1 ϕ−1 when B1 ⊆ B. Note that dom(ϕ) = A and
range(ϕ) ⊆ B. The set of all mappings from A to B is denoted by B A .
The composition or product of two mappings ϕ : A → B and ψ : B → C is the mapping
ϕψ : A → C
where ϕψ is the product of ϕ and ψ as relations. Clearly, aϕψ = (aϕ)ψ for all a ∈ A.
The restriction of a mapping ϕ : A → B to a subset C of A is the mapping
ϕ|C : C → B
θ ♮ : A → A/θ, a 7→ aθ, (a ∈ A)
such that the kernel of θ ♮ is θ. This θ ♮ is called the natural mapping associated with θ.
A mapping ϕ : A → B is called
8
1.1 Sets, relations and mappings
We shall also meet partial mappings, that is, mappings for which the image of some
elements may be undefined. A partial mapping from A to B is defined by a relation
ϕ ⊆ A × B such that |aϕ| ≤ 1 for all a ∈ A. Again, we write ϕ : A → B. If aϕ = ∅, then
we say that ϕ is undefined for a (a ∈ A). The notations and terminology introduced
above for mappings apply to partial mappings, too, although dom(ϕ) may be a proper
subset of A when ϕ : A → B is a partial mapping.
It is convenient to think of the elements of a cartesian product A1 ×· · ·×An as n-tuples
(a1 , . . . , an ) with a1 ∈ A1 , . . . , an ∈ An . We adopt the definition of an ordinal number n
as the set of all ordinals smaller that n: 0 = ∅, 1 = {0}, 2 = {0, 1} etc. and, in general,
n = {0, 1, . . . , n − 1}. Then A1 × · · · × An can also be defined as the set of all mappings
ϕ : n → A1 ∪ · · · ∪ An
such that iϕ ∈ Ai+1 for i = 0, 1, . . . , n − 1. Of course, we may identify such a ϕ with
the n-tuple (0ϕ, 1ϕ, . . . , (n − 1)ϕ). Now the cartesian power An = A × · · · × A (n times)
is the set of all mappings ϕ : n → A. In particular, A0 = {∅} since ∅ is the only mapping
from ∅ to A. Note that the notation An is consistent with our earlier notation B A for
the set of all mappings from A to B.
We shall also need countably infinite sequences of elements. Let ω = {0, 1, 2, . . . } be
the smallest infinite ordinal and A any set. The elements of Aω are called ω-sequences.
Thus an ω-sequence of elements of A is a mapping
ϕ: ω → A
which we may also write as
(0ϕ, 1ϕ, . . . , nϕ, . . . )n<ω .
We conclude the section by considering operations. These are special mappings and
are among the most fundamental concepts of algebra. Let m ≥ 0. An m-ary operation
on a set A is a mapping from Am to A. If ϕ : Am → A is an m-ary operation on A, then
ϕ assigns to every m-tuple (a1 , . . . , am ) of elements of A a unique element of A which
we write as ϕ(a1 , . . . , am ). The number m is called the arity or the rank of ϕ. Most
operations encountered in the usual algebraic systems (groups, rings, lattices etc.) have
rank 0, 1 or 2. A few comments on these special cases:
(i) A 0-ary operation ϕ : {∅} → A is completely determined by its only image ϕ(∅),
and often ϕ is given simply by naming this element. Note that here ∅ may also be
seen as the empty sequence of elements, and often one writes ϕ( ), or just ϕ, for
ϕ(∅).
(ii) When m = 1, we have a mapping from A to itself. Such operations are called
unary.
(iii) An operation of rank 2 is called a binary operation. For example, the addition and
the multiplication in a ring are binary operations. In most such concrete examples
one uses the infix notation for binary operations. Thus it is customary to write the
ring operations in the form a + b and a · b instead of +(a, b) and ·(a, b), respectively.
9
1 PRELIMINARIES
ϕ|B : B m → B,
(pU, ∪, ∩, c , ∅, U )
10
1.2 Universal algebras
with two binary, one unary and two 0-ary operations. Note that we get such an algebra
for each set U . In fact, all of these algebras can be viewed as special instances of a
general class of algebras known as Boolean algebras.
The example brings forth an important point. In algebra, and this will be the case
here, too, one is generally not interested just in individual algebras, but rather in whole
classes of algebras. Algebras in such a class are all “similar” in the sense that there
is a natural correspondence between the operations of any two algebras of the class.
Such a correspondence of operations is needed when one defines any concept, such as
homomorphisms or direct products, involving more than one algebra. For example, the
multiplications of any two groups correspond to each other, and a homomorphism of
groups should preserve the multiplication. We shall now introduce a convenient vehicle
to define such a class of similar algebras.
r : Σ → N0
Σm = {σ ∈ Σ | r(σ) = m}
From now on Σ is an operator domain. The mapping r is usually not mentioned, but
we denote by r(Σ) the set of all m ≥ 0 such that Σm 6= ∅. One can write Σ as the
disjoint union Σ0 ∪ Σ1 ∪ Σ2 ∪ . . . from which the empty sets will be omitted.
σ A : Am → A,
11
1 PRELIMINARIES
Note that the possibility m = 0 is not excluded when we consider generally an m-ary
operation. For σ ∈ Σ0 one often writes σ A instead of σ A ( ) or σ A (∅) (this involves the
harmless confusion of a 0-ary operation and its value). When Σ = {σ1 , . . . , σk } is finite,
one usually writes A = (A, σ1 , . . . , σk ) instead of A = (A, Σ).
We introduce now several concepts related to algebras.
12
1.2 Universal algebras
a1 ≡ b1 , . . . , am ≡ bm (̺).
Every algebra A has at least the trivial congruences δA and ιA . For ̺ ∈ C(A), the
̺-class a̺ of an element a ∈ A is also called a congruence class (modulo ̺). The partition
A/̺ of A defined by the congruence classes is compatible in the sense that for all m ≥ 0,
σ ∈ Σm and a1 ̺, . . . , am ̺ ∈ A/̺ there is a class a̺ such that
σ A (a1 ̺, . . . , am ̺) ⊆ a̺.
13
1 PRELIMINARIES
ψ : aθ 7→ aϕ (a ∈ A).
14
1.2 Universal algebras
For any a1 , a2 ∈ A,
a1 θψ = a2 θψ iff a1 ϕ = a2 ϕ
iff a1 ≡ a2 (θ).
This shows that ψ is well-defined (i.e., aθψ is independent of the choice of the represen-
tative a ∈ A of the θ-class aθ) and injective. Since ϕ is surjective, it is clear that ψ is
surjective, too. It remains to be shown that ψ is a homomorphism. Let m ≥ 0, σ ∈ Σm
and a1 , . . . , am ∈ A. Then
σ A/θ (a1 θ, . . . , am θ)ψ = σ A (a1 , . . . , am )θψ
= σ A (a1 , . . . , am )ϕ
= σ B (a1 ϕ, . . . , am ϕ)
= σ B (a1 θψ, . . . , am θψ). ✷
Taken together, Theorems 1.2.9 and 1.2.11 say that the epimorphic images of an algebra
are exactly its quotient algebras (when one does not distinguish between isomorphic
algebras).
Next, direct products of algebras are introduced. We may restrict ourselves to the case
of a finite number of factors.
Definition 1.2.12 The direct product of two Σ-algebras A and B is the Σ-algebra
A × B = (A × B, Σ),
where the operations are defined so that
σ A×B ((a1 , b1 ), . . . , (am , bm )) = (σ A (a1 , . . . , am ), σ B (b1 , . . . , bm ))
for all m ≥ 0, σ ∈ Σm and (a1 , b1 ), . . . , (am , bm ) ∈ A × B. The kth (k ≥ 0) direct power
Ak of the Σ-algebra A is defined inductively:
(i) A0 = ({∅}, Σ) is the trivial Σ-algebra.
(ii) Ak+1 = Ak × A for all k ≥ 0.
It is easy to see that direct products are associative in the sense that (A × B) × C ∼ =
A × (B × C) for all A, B and C. Both of these products can be written simply as
A × B × C and their elements may be identified with the triples (a, b, c) with a ∈ A,
b ∈ B and c ∈ C. More generally, one can define the direct product A1 × · · · × Ak of k
(k ≥ 0) Σ-algebras as an algebra with A1 × · · · × Ak as its set of elements and operations
performed componentwise. It is easy to see that the projections
πi : A1 × · · · × Ak → Ai , (a1 , . . . , ak ) 7→ ai
(i = 1, . . . , k) are epimorphisms from A1 × · · · × Ak to the respective factor algebras Ai .
Hence, every factor in a direct product is an epimorphic image of the direct product.
We shall also need the following, perhaps, less usual, way to construct a new algebra
from a given one.
15
1 PRELIMINARIES
Definition 1.2.13 The subset algebra (or power algebra) pA = (pA, Σ) of a Σ-algebra
A is defined as follows. If m ≥ 0, σ ∈ Σm and H1 , . . . , Hm ∈ pA, then put
σ pA (H1 , . . . , Hm ) = σ A (H1 , . . . , Hm ).
Example 1.2.14 Suppose Σ consists of one binary operator σ and a nullary operator
γ. Let A = ({a, b}, Σ) be a Σ-algebra such that γ A = a and σ A (a, a) = σ A (a, b) =
σ A (b, a) = a, σ A (b, b) = b. Consider first the direct power A2 = A × A. If we write aa
for (a, a) etc., then γ A×A = aa and σ A×A is given by the following multiplication table:
σ A×A aa ab ba bb
aa aa aa aa aa
ab aa ab aa ab
ba aa aa ba ba
bb aa ab ba bb
Let us now construct the subset algebra. The value of the 0-ary operation is γ pA = {a}
and the operation σ pA is given by the table below.
16
1.3 Terms, polynomial functions and free algebras
the operations of the algebra in question are known. In fact, algebras can be viewed as
devices that evaluate terms. When we interpret (in Chapter 2) terms as trees, the step
from algebras to tree automata is not long.
From now on, X will be a set disjoint from the operator domain Σ. The elements of
X are called variables. Other symbols used for sets of variables are Y and Z.
Definition 1.3.1 The set FΣ (X) of Σ-terms in X, or ΣX-terms for short, is defined as
follows:
(i) X ⊆ FΣ (X),
(iii) every ΣX-term can be obtained by applying the rules (i) and (ii) a finite number
of times.
(i) X ∪ Σ0 ⊆ FΣ (X),
(iii) every ΣX-term can be obtained by applying the rules (i) and (ii) a finite number
of times.
When Σ and X are unspecified or unemphasized, we shall speak simply about terms.
The inductive definition of FΣ (X) suggests a useful method to deal with terms. It could
be called term induction. If we want to define a property or quantity c(t) for every
ΣX-term t, it suffices
Sometimes the variation suggested by Definition 1.3.1’ is more convenient: in (i) one
defines c(t) for t ∈ Σ0 , too, but in (ii) one can then restrict oneself to values m > 0.
Proofs by term induction can be modelled according to the same pattern.
Note that FΣ (X) is empty iff Σ0 = X = ∅. Since we do not want to consider this
uninteresting case separately every time, we shall tacitly assume that always Σ0 ∪X 6= ∅.
17
1 PRELIMINARIES
Of course, the result depends on the choice of α, too. This evaluation process can be
formalized as follows.
tA : AX → A
It may seem strange that the polynomial functions tA ∈ PX (A) are evaluated on
mappings from X to A, but this is, in fact, just a modification of the usual way to
express polynomial functions. When one writes the value of a polynomial function in
the form p(a1 , . . . , an ), a given order of the variables is assumed, say X = {x1 , . . . , xn },
and the n-tuple (a1 , . . . , an ) is just a convenient way to give the mapping α : X → A
such that xi α = ai (i = 1, . . . , n).
In a sense, the polynomial functions of an algebra A are the operations one can derive
by composition from the basic operations σ A (σ ∈ Σ) of A, and they share many
properties with these. This is exemplified by the following four lemmas.
The lemma states, in other words, that subalgebras are closed with respect to polyno-
mial functions. The proof is a simple exercise in term induction quite similar to that of
the next lemma which expresses formally the fact that congruences are invariant with
respect to polynomial functions.
18
1.3 Terms, polynomial functions and free algebras
tA A
i (α) ≡ ti (β) (θ) for all i = 1, . . . , m.
Then also
tA (α) = σ A (tA A A A A A
1 (α), . . . , tm (α)) ≡ σ (t1 (β), . . . , tm (β)) = t (β) (θ)
tA (α)ϕ = tB (αϕ)
then
tA×B (γ) = (tA (α), tB (β)) for all t ∈ FΣ (X). ✷
Lemma 1.3.8 For any subset X of a Σ-algebra A we have [X] = {tA (αX ) | t ∈ FΣ (X)},
where αX = 1A |X, i.e., αX is the mapping from X to A such that xαX = x for all x ∈ X.
σ A (tA A A
1 (αX ), . . . , tm (αX )) = σ(t1 , . . . , tm ) (αX ) ∈ C
19
1 PRELIMINARIES
(i) F ∈ K.
(ii) X generates F.
If these conditions are satisfied for some subset X of F , then F is called a free algebra
over K (with |X| generators), and X is called a free generating set.
b : X+ → S
α
is obtained by putting
Theorem 1.3.11 The ΣX-term algebra FΣ (X) is freely generated by X over the class
of all Σ-algebras.
Proof. That X generates FΣ (X) is quite obvious when we compare the definitions of
FΣ (X) and FΣ (X), but it follows also from the useful observation that
20
1.3 Terms, polynomial functions and free algebras
(where αX = 1FΣ (X) |X). The proof of (*) goes again by term induction. Let A be any
Σ-algebra and α : X → A any mapping. We claim that the mapping
b : FΣ (X) → A,
α t 7→ tA (α) (t ∈ FΣ (X))
σ FΣ (X) (t1 , . . . , tm )b
α = σ(t1 , . . . , tm )A (α)
= σ A (tA A
1 (α), . . . , tm (α))
= σ A (t1 α
b , . . . , tm α
b)
We add a few general comments on free algebras. First of all, one should note that
the homomorphic extension α b : F → A of a mapping α : X → A (A ∈ K) is unique.
This follows from Lemma 1.2.6. Free algebras over a given class do not always exist,
but when they do, they are determined up to isomorphism by the cardinality of the free
generating set. This is stated formally in the following lemma.
Lemma 1.3.12 Any two algebras freely generated over the same class of algebras by
sets of the same cardinality are isomorphic.
Proof. Suppose A and B both are free over the same class K and that they have free
generating sets X and Y , respectively, such that |X| = |Y |. Then there is a bijection
α : X → Y . The converse of it, β = α−1 , defines a bijection from Y to X. Now there
exist morphisms
b : A → B and βb : B → A
α
b = β. But then
b|X = α and β|Y
such that α
Lemma 1.3.12 allows us to speak about the algebra freely generated over a class K by
a set X.
b used above for the rest of the book: for anyA and α : X → A,
We shall fix the notation α
b : FΣ (X) → A is the homomorphism such that α
α b|X = α. To evaluate a ΣX-term t in a
Σ-algebra A for a given assignment α : X → A of values to the variables amounts to the
computation of tb α. Indeed, we showed in the proof of Theorem 1.3.11 that tA (α) = tb α
for all A, α and t.
The polynomial functions in variables X of an algebra A are the mappings one can get
from the “projections” xA (x ∈ X) by iterated compositions with the basic operations
21
1 PRELIMINARIES
σ A (σ ∈ Σ). If the generating set of functions is enlarged by the set of all constant
mappings (c ∈ A)
γc : AX → A, α 7→ c (α ∈ AX ),
then we get, in general, a larger class of functions. These are called algebraic functions.
We shall need just the unary (i.e., 1-place) algebraic functions and these only are defined
below. In this special case X is a singleton {x} and we may identify any mapping
α : X → A with the element xα ∈ A. Then the unary algebraic functions can be defined
simply as certain mappings from A to A.
Definition 1.3.13 The set of unary algebraic functions Alg1 (A) of a Σ-algebra A is
defined as follows:
(i) 1A ∈ Alg1 (A).
(ii) For every c ∈ A, Alg1 (A) contains the constant mapping γc : A → A, a 7→ c
(a ∈ A).
(iii) The composition σ A (f1 , . . . , fm ) is in Alg1 (A) whenever m ≥ 0, σ ∈ Σm and f1 ,
. . . , fm ∈ Alg1 (A).
(iv) All members of Alg1 (A) are obtained by the rules (i)–(iii).
Lemma 1.3.14 For every f ∈ Alg1 (A) there exists a term tf ∈ FΣ (A ∪ x) such that,
for all a ∈ A,
f (a) = tA
f (αa )
22
1.4 Lattices
Proof. Suppose a ≡ b (θ) implies f (a) ≡ f (b) (θ) for all a, b ∈ A and f ∈ ET(A).
Consider any m > 0, σ ∈ Σm and elements a1 , . . . , am , b1 , . . . , bm ∈ A such that
a1 ≡ b1 , . . . , am ≡ bm (θ). Define the following m elementary translations:
Then
Hence σ A (a1 , . . . , am )θσ A (b1 , . . . , bm ) and we have verified that θ ∈ C(A). The converse
is obvious. ✷
1.4 LATTICES
We shall need a few facts from lattice theory, and these are quickly surveyed here.
(1) δA ⊆ ̺ (̺ is reflexive),
(3) ̺̺ ⊆ ̺ (̺ is transitive).
23
1 PRELIMINARIES
The usual symbol for a partial ordering is ≤. Often a set A is called a poset when a
certain partial ordering of A is understood.
An example of a poset is (pS, ⊆), where S is a set and ⊆ the usual subset relation
in the power set pS. Another simple example is (N, ≤) where ≤ is the “less than or
equal” -relation of natural numbers. This ≤ is a total ordering, which means that any
two elements of the poset are comparable, i.e., either a ≤ b or b ≤ a holds for any two
elements a and b. A poset (A, ≤) in which ≤ is a total ordering is called a chain.
Let (A, ≤) be a poset and a, b ∈ A. We may write a ≥ b when b ≤ a, a < b when
a ≤ b and a 6= b, and a > b when a ≥ b and a 6= b. Clearly ≥ is a partial ordering and
the poset (A, ≥) is said to be dual to (A, ≤). Each one of the relations ≥, < and >
determines ≤ completely.
An element a ∈ A is an upper bound of a subset H ⊆ A if b ≤ a for all b ∈ H. An
upper bound a of H ⊆ A is the least upper bound, or the supremum, of H, if a ≤ c
for all upper bounds c of H. Lower bounds and greatest lower bounds (infimums) are
defined similarly. The least upper
W bound
V and the greatest lower bound of a subset H
are denoted, respectively,W by H and H. In case of an indexed family (ai | i ∈ I) of
V
elements the notations (ai | i ∈ I) and (ai | i ∈ I) may be used.
An element c ∈ A is a zero element of the poset A if c ≤ a for every a ∈ A. If a
poset has a zero element, it is unique and usually it is denoted by 0. Similarly,
V the unit
element 1, is defined by the condition V that a ≤ 1 for all a ∈WA. Clearly, A exists iff the
poset has a zero element 0, and then A = 0. Similarly, A exists, and then equals 1,
iff A has a unit element 1.
W V
Definition 1.4.2 A posetW(A, ≤) isVa lattice, if {a, b} and {a, b} exist for all a, b ∈ A.
It is a complete lattice, if H and H exist for all subsets H of A.
W V
In a lattice one usually writes a ∨ b and a ∧ b for {a, b} and {a, b}, respectively. The
element a ∨Wb is also called
V the join of a and b, and a ∧ b is the meet of a and b. It is easy
to
W see that H and H exist for every finite, nonempty subset H W of a lattice. However,
V
∅ exists only in case the lattice has a zero element
V 0. Then ∅ = 0. Similarly, ∅
exists iff the lattice has a unit element 1; then ∅ = 1.
The following lemma follows directly from the definitions of the join and the meet.
Lemma 1.4.3 If (A, ≤) is a lattice then ∧ and ∨ satisfy the following identities:
(L1) x ∧ x = x, x ∨ x = x (idempotence).
(L2) x ∧ y = y ∧ x, x ∨ y = y ∨ x (commutativity).
(L3) x ∧ (y ∧ z) = (x ∧ y) ∧ z, x ∨ (y ∨ z) = (x ∨ y) ∨ z (associativity).
(L4) x ∧ (x ∨ y) = x, x ∨ (x ∧ y) = x (absorption). ✷
The identities (L1)–(L4) are characteristic of lattices in the following sense. If (A, ∧, ∨)
is an algebra with two binary operations that satisfy these identities, then (A, ≤) is a
lattice when ≤ is defined so that
a≤b iff a∧b=a (a, b ∈ A).
24
1.4 Lattices
W V
In this lattice {a, b} = a ∨ b and {a, b} = a ∧ b for all a, b ∈ A. In lattice theory
lattices are usually defined and considered in parallel both as posets and as algebras.
The two aspects of the theory complement each other.
The following lemma is often useful when one wants to show that a certain poset is a
complete lattice.
V
Lemma 1.4.4 A poset (A, ≤) is a complete lattice, if H exists for each subset H ⊆ A.
✷
V
Note that the existence of ∅ = 1 should also be ascertained when Lemma 1.4.4 is
used. We shall now apply the lemmaT to an important example. Let A be a set. It is
easy to see that the intersection (εi | i ∈ I) of any equivalence relations εi (i ∈ I) of A
is again in E(A). This means that
^ \
(εi | i ∈ I) = (εi | i ∈ I)
V
always exists in the poset (E(A), ⊆). (In particular, ∅ = ιA .) Hence, we get
a ε1 a1 ε2 a2 . . . an−1 εn b. ✷
Theorem 1.4.7 For any Walgebra A = (A,VΣ), C(A) forms a complete sublattice of
(E(A), ⊆), that is to say, H ∈ C(A) and H ∈ C(A) whenever H ⊆ C(A). ✷
The direct product (L1 × · · · × Ln , ≤) of posets (L1 , ≤), . . . , (Ln , ≤) is a poset when
we define ≤ in L1 × · · · × Ln so that
If the (Li , ≤)’s are lattices, then the direct product is also a lattice in which
and
25
1 PRELIMINARIES
26
1.5 Finite recognizers and regular languages
w = x1 x2 . . . xn (n ≥ 0, x1 , . . . , xn ∈ X).
x1 x2 . . . xm = y 1 y 2 . . . y n
holds just in case m = n and xi = yi for all i = 1, ..., m. Letters are considered words of
length 1. Hence, we may write X ⊂ X + ⊂ X ∗ and X ∗ = X + ∪ e.
In Section 3 we noted that X + is the free semigroup generated by X, when the product
of two words is defined to be their catenation. Similarly, X ∗ is the free monoid generated
by X. The identity element is the empty word: ew = we = w for each w ∈ X ∗ .
A language over X, or an X-language, is simply a subset of X ∗ . An X-language is
e-free if it does not include the empty word. Of course, formal language theory concerns
itself with such languages only that can be specified in some effective manner.
A family of languages L is defined by indicating for each alphabet the set L(X) of
X-languages belonging to the family. For example, L(X) could consist of all languages
recognized by automata of a given type with input alphabet X. If L ∈ L(X), one may
write just L ∈ L. Two families of languages K and L are equal, which we write K = L,
if K(X) = L(X) for every alphabet X. Similarly, the inclusion K ⊆ L means that
K(X) ⊆ L(X) for every X.
One way to specify a language L ⊆ X ∗ is to give an automaton that can examine any
given X-word and then tell whether the word is in L or not. Such automata are called
recognizers. The most basic type of recognizers is the following:
27
1 PRELIMINARIES
δ̂ : A × X ∗ → A
as follows:
1◦ δ̂(a, e) = a for each a ∈ A, and
L(A) = {w ∈ X ∗ | δ(a0 , w) ∈ A′ }.
U V = {uv | u ∈ U, v ∈ V }.
U (V W ) = (U V )W for all U, V, W ⊆ X ∗ .
Furthermore,
U ∅ = ∅U = ∅ and U {e} = {e}U = U
for every X-language U .
The powers U n (n ≥ 0) of an X-language U are defined inductively:
1◦ U 0 = {e} and
2◦ U n = U n−1 U for n > 0.
28
1.5 Finite recognizers and regular languages
Definition 1.5.2 The set Reg X of regular X-languages is the smallest set R such that
1◦ ∅ ∈ R and {x} ∈ R for each x ∈ X, and
2◦ U, V ∈ R implies U ∪ V, U V, U ∗ ∈ R.
Regular languages are also called rational languages. All finite languages are regular.
Hence Reg X is the smallest set of X-languages containing the finite X-languages which
is closed under the three regular operations.
The form of Definition 1.5.2 implies that every regular X-language can be represented
by a regular expression which shows how the language is obtained from ∅ and the lan-
guages {x} by forming unions, products and iterations.
Example 1.5.3 Let X = {x, y}. Some members of Reg X are ∅, {x}, {y}, {xy} =
{x}{y}, {xy, yy} = {x}{y} ∪ {y}{y} = ({x} ∪ {y}){y} and
A possible regular expression for the language U would be η = (x(x)∗ (y)∗ ) + (y(xx)∗ )
(usually ‘+’ is used for union). If we agree on the usual hierarchy of regular operations
(first iterations, then products, and unions last), then some parentheses can be omitted
and η becomes xx∗ y ∗ +y(xx)∗ . The language U is recognized by the X-recognizer defined
by the state graph of Fig 1.1 (the initial state is a0 and the final states are a, b and c).
✷
The following theorem is one of the cornerstones of finite automaton theory.
The theorem is effective in the following sense. There are algorithms to construct a
recognizer for any regular language given by a regular expression. Conversely, a regular
expression representing L(A) can be found for any given recognizer A.
Kleene’s theorem implies also that the family Rec is closed under the regular opera-
tions. We shall present some more closure properties of the family Rec.
29
1 PRELIMINARIES
x y
a
y
b
x x xy
a0 q
y y
y
c x d
x
Figure 1.1
(c) If U and V are recognizable X-languages, then so are the quotient languages
U −1 V = {w ∈ X ∗ | uw = v for some u ∈ U, v ∈ V }
and
U V −1 = {w ∈ X ∗ | wv = u for some u ∈ U, v ∈ V }.
30
1.5 Finite recognizers and regular languages
(i) a0 ∈ A0 ,
(iii) an ∈ A′ .
δ̂ : pA × X ∗ → pA
as follows:
Obviously, δ̂(H, w) is the set of states A may reach under the input word w from at
least one state in H. The language recognized by A can now be defined formally as
where A′′ = {H ∈ pA | H ∩A′ 6= ∅}; this is the well-known “subset construction”. Hence,
a language can be recognized by a nondeterministic recognizer iff it is recognizable in
our original sense of the word.
Now we recall some algebraic characterizations of Rec.
An equivalence relation ̺ on a semigroup S is a right congruence, if a̺b implies ac̺bc
for all a, b, c ∈ S. Every X-recognizer A = (A, X, δ, a0 , A′ ) defines a right congruence
̺A of the free monoid X ∗ as follows:
31
1 PRELIMINARIES
for all u, v ∈ X ∗ . From these observations it is easy to construct a proof for the following
theorem.
Theorem 1.5.6 (A. Nerode 1957). For any X-language L the following three conditions
are equivalent:
(1) L ∈ Rec X.
for all u, v ∈ X ∗ .
Theorem 1.5.7 (J. R. Myhill 1957). For every X-language L the following three con-
ditions are equivalent:
(1) L ∈ Rec X.
32
1.5 Finite recognizers and regular languages
−1
Let θ be a congruence of X ∗ saturating an X-language L. Then L = (Lθ ♮ )θ ♮ , where
θ ♮ : X ∗ → X ∗ /θ
is the canonical homomorphism, and X ∗ /θ is finite iff θ is of finite index. This applies,
in particular, to the syntactic congruence θL . The monoid X ∗ /θL is called the syntactic
monoid of L. On the other hand, if we have a finite monoid M , a homomorphism
ϕ : X∗ → M
Theorem 1.5.8 For any X-language L the following three conditions are equivalent:
(1) L ∈ Rec X.
L − {e} = (HX ∗ ∩ X ∗ K) − X ∗ IX ∗ .
33
1 PRELIMINARIES
(2) θ saturates A′ .
Let C(A) be the set of all congruences of A. It is not hard to prove that ∼ is a congruence
of A. In fact, it is the greatest congruence of A.
If θ ∈ C(A), then one can define a quotient recognizer
by putting
δ′ (aθ, x) = δ(a, x)θ for all a ∈ A and x ∈ X.
The congruence property (1) guarantees that δ′ is well-defined. An easy induction on
|w| shows that
δ′ (aθ, w) = δ(a, w)θ for all a ∈ A and w ∈ X ∗ .
This implies L(A/θ) = L(A). In particular, L(A/∼) = L(A). It is now obvious that a
minimal recognizer should be reduced and, of course, connected.
Let A = (A, X, δ, a0 , A′ ) and B = (B, X, η, b0 , B ′ ) be two X-recognizers. A homomor-
phism ϕ : A → B is a mapping ϕ : A → B such that
(1) δ(a, x)ϕ = η(aϕ, x) for all a ∈ A and x ∈ X,
(2) a0 ϕ = b0 , and
(3) B ′ ϕ−1 = A′ .
Epimorphisms and isomorphisms of X-recognizers are, respectively, surjective and bi-
jective homomorphisms.
Homomorphisms, congruences and quotients of X-recognizers are related to each other
the same way as the corresponding concepts in algebra. Hence, for any θ ∈ C(A), the
natural mapping θ ♮ is an epimorphism A → A/θ. If ϕ : A → B is an epimorphism, then
ϕϕ−1 is a congruence of A and A/ϕϕ−1 is isomorphic to B. Moreover,
Ac = (Ac , X, δc , a0 , A′ ∩ Ac )
where δc = δ|Ac × X.
The following theorem summarizes the main facts concerning minimal and reduced
recognizers.
34
1.6 Grammars and context-free languages
(c) For any recognizer A, the quotient A/∼ is reduced and its connected part (A/∼)c
is minimal. The recognizer Ac /∼ is isomorphic to (A/∼)c .
(d) If A is minimal, B is connected and L(A) = L(B), then there exists a unique
epimorphism ϕ : B → A. ✷
Theorem 1.5.10 implies that one can find a minimal recognizer for a regular language
L by starting with any recognizer A of L; first one finds the connected part Ac and
then one has to determine the equivalent pairs of states in Ac . For both tasks there are
simple algorithms. The order may also be reversed; first form A/∼ and then find the
connected part of this reduced recognizer.
The decidability of the emptiness, finiteness and equality questions for regular lan-
guages follows from the following simple observation.
(a) If L(A) contains a word w of length ≥ n, then one may write w = uvz so that
0 < |v| ≤ n and uv k z ∈ L(A) for all k ≥ 0.
(c) L(A) is infinite iff it contains a word w such that n ≤ |w| < 2n. ✷
Statement (a) is often referred to as the “pumping lemma” for finite recognizers.
To test whether L(A) is nonempty it suffices to try all input words of length < |A|.
Similarly, the finiteness of L(A) can be checked by applying all input words w such
that |A| ≤ |w| < 2|A|. From any two X-recognizers A and B one can construct a
recognizer for (L(A) − L(B)) ∪ (L(B) − L(A)). But this language is empty exactly in
case L(A) = L(B). Hence, the equivalence of A and B can also be decided.
35
1 PRELIMINARIES
u0 ⇒G u1 ⇒G u2 ⇒G . . . ⇒G un (n ≥ 0)
such that u0 = u and un = v, then we write u ⇒∗G v (or just u ⇒∗ v). The language
generated by G is the X-language
(iii) δ(c, x) = ∅.
36
1.6 Grammars and context-free languages
P = {a → xb | δ(a, x) = b} ∪ {a → e | a ∈ A′ }.
Theorem 1.6.3 The type 3 languages are exactly the regular languages. ✷
Definition 1.6.4 A grammar (N, X, P, a0 ) is context-free (CF, for short) if each pro-
duction is of the form
a→γ
The CF languages are the type 2 languages in Chomsky’s hierarchy. Every right linear
grammar is CF. Hence Rec ⊆ CF. If |X| = 1, then Rec X = CF(X), but in all other
cases the inclusion is proper.
Example 1.6.5 Suppose X contains two distinct letters x and y. Every derivation in
the CF grammar
G = ({a}, X, {a → xay, a → xy}, a)
is of the form
The main fact to connect CF languages with tree automata is that context-free deriva-
tions can be represented by derivation trees. A derivation tree is a description of the
syntax of a word of the CF language. (Here it would be more natural to speak about
“sentences” of a language.) Derivation trees have proved very useful tools in the theory
of CF languages. Later we shall define “trees” in a way suitable for our purposes, but
here there is no need to define the concept too formally.
Let G = (N, X, P, a0 ) be a CF grammar. The derivation tree representing a derivation
of a word u ∈ (X ∪ N )∗ from a symbol a ∈ (X ∪ N ) in G is defined by induction on the
number k of steps in the derivation:
37
1 PRELIMINARIES
2◦ Consider a derivation
a ⇒ u1 ⇒ u2 ⇒ . . . ⇒ uk−1 ⇒ u (*)
where k ≥ 1. Suppose u1 = d1 . . . dm , where m ≥ 0 and d1 , . . . , dm ∈ N ∪ X.
At this point the context-freeness of G becomes essential. Every application of a
production in (*) rewrites exactly one di or a nonterminal derived from exactly one
di . This means that (*) may be decomposed into a number of “subderivations”
di ⇒ . . . ⇒ vi (i = 1, . . . , m)
each of which yields a segment vi of u and u = v1 v2 . . . vm . If the derivation trees
of the subderivations are t1 , . . . , tm , respectively, then the derivation tree of (*) is
that shown in Fig. 1.2.
The possibility m = 0 was not excluded. Then k = 1, u = e and the derivation
tree reduces to a single node labelled by a.
t1 tm
d1 ... dm
Figure 1.2
x y
x y
a
x y
a
Figure 1.3
tree is also called a derivation tree of w, and w can be read from the “leaves” of the tree.
The grammar G of Example 1.6.5 has the rather special property that every word in
L(G) has just one derivation in G.
38
1.6 Grammars and context-free languages
Obviously, L(G) = {xm y m+n xn | m, n ≥ 1}. The word xyyx ∈ L(G) has the two
derivations
a0 ⇒ ab ⇒ xyb ⇒ xyyx
and
a0 ⇒ ab ⇒ ayx ⇒ xyyx
both of which are represented
by the derivation tree shown in Fig. 1.4. In general, the
word xm y m+n xn has m+n
n different derivations all of which are represented by the same
derivation tree. ✷
x y y x
a b
a0
Figure 1.4
In Example 1.6.6 the different derivations of the same word do not represent different
syntactic descriptions of the word. In fact, they can all be obtained from each other by
changing the order in which the individual steps are carried out. If we agree on some
fixed order in which the subderivations are to be carried out, then there would be just
one derivation for each derivation tree of a word in the language.
u0 ⇒ u1 ⇒ u2 ⇒ . . . ⇒ uk
39
1 PRELIMINARIES
a0 ⇒∗ uav ⇒∗ w
If m ≤ k for all productions of type (i), then G is said to be in Greibach k-form (k ≥ 0).
Proofs for the following facts can be found in the references given at the end of the
section.
Theorem 1.6.9 (a) Every CF grammar (N, X, P, a0 ) can be converted into an equiv-
alent reduced CF grammar (N ′ , X, P ′ , a0 ), where N ′ ⊆ N and P ′ ⊆ P .
(b) Every CF grammar can be converted into an equivalent CF grammar in any one
of the following normal forms: Chomsky normal form, Greibach normal form, and
Greibach 2-form. In all cases the grammar can be made reduced. ✷
Theorem 1.6.10 If the languages U and V are CF, then so are U ∪ V , U V and U ∗ . ✷
40
1.6 Grammars and context-free languages
The following theorem implies, as a special case, that CF is closed under morphisms.
The following useful lemma is obtained most naturally by considering derivation trees.
Lemma 1.6.13 (Bar-Hillel’s pumping lemma). For each CF grammar G one can find
two natural numbers p and q such that the following holds for every word w ∈ L(G): if
|w| > p, then we may write w = u1 v1 w′ v2 u2 so that
(i) |v1 w′ v2 | ≤ q,
(ii) v1 v2 6= e, and
Theorem 1.6.14 There are algorithms for deciding the following questions:
The decidability of the finiteness problem follows from Bar-Hillel’s lemma. The other
two statements can be justified quite directly.
(b) Is the intersection of two given CF languages empty? | finite? | regular? | context-
free?
41
1 PRELIMINARIES
42
1.7 Sequential machines
2◦ δ̂(a, wx) = δ(δ̂(a, w), x) and λ̂(a, wx) = λ̂(a, w)λ(δ̂(a, w), x) for all a ∈ A, w ∈ X ∗ ,
x ∈ X.
If A receives in state a the input word w, it emits the word λ̂(a, w) (∈ Y ∗ ) and ends
up in state δ̂(a, w). The translation induced by A is defined as the relation
Two Mealy-machines are said to be equivalent if they define the same translation.
In the case of a Mealy-machine A every input word w has exactly one translation
λ̂(a0 , w) and this has the same length as w. Mealy-machines enjoy a number of desirable
properties and they have a well-developed theory. For example, the following facts are
known:
(c) For any Mealy-machine one can find an equivalent minimal Mealy-machine and this
is unique up to isomorphism.
43
1 PRELIMINARIES
(d) Let A be the Mealy-machine defined above. If L ∈ Rec X, then LτA ∈ Rec Y . If
−1
L ∈ Rec Y , then LτA ∈ Rec X.
There are several ways to generalize Mealy-machines. First of all, both the next-state
and the output behaviour may be nondeterministic. Another generalization allows the
sequential machine to emit a word in response to each input letter. Moreover, one may
add a set of final states. Then a translation of a word is accepted just in case it leaves
the machine in a final state. We shall now define a generalized sequential machine which
includes all these features. It is now convenient to use a set of productions which will
account both for the next-state behaviour and for the outputs. We arrive at the following
concept.
Definition 1.7.1 A (nondeterministic) generalized sequential machine (gsm) is a sys-
tem A = (X, A, Y, a0 , P, A′ ) where
(1) X is the input alphabet,
(2) A is a finite, nonempty set of states,
(3) Y is the output alphabet,
(4) a0 (∈A) is the initial state,
(5) P is a set of productions of the form ax → wb with a, b ∈ A, x ∈ X and w ∈ Y ∗ ,
and
(6) A′ ⊆ A is the set of final states.
It is assumed that A ∩ (X ∪ Y ) = ∅. The gsm A is said to be deterministic if there exists
for each pair (a, x) ∈ A × X exactly one production of the form ax → wb.
Let A be the above gsm. A production ax → wb is interpreted as follows. If A
is in state a and receives the input x, A may enter state b and simultaneously emit
the word w. We shall now define the translation performed by A. For any two words
p, q ∈ (A ∪ X ∪ Y )∗ , we write p ⇒A q if there exist a production ax → wb in P and
words p′ and p′′ such that p = p′ axp′′ and q = p′ wbp′′ . The reflexive, transitive closure
of ⇒A is denoted by ⇒∗A . Thus p ⇒∗A q (p, q ∈ (A ∪ X ∪ Y )∗ ) holds iff there exists a
derivation of the form
p = p 0 ⇒A p 1 ⇒A . . . ⇒A p k = q (k ≥ 0).
Now, the translation induced by A is defined as the relation
τA = {(u, v) | u ∈ X ∗ , v ∈ Y ∗ , a0 u ⇒∗A vb for some b ∈ A′ }.
If (u, v) ∈ τA , then v is a translation of u. If A is deterministic, then each X-word w has
at most one translation. Two gsm’s are equivalent if they induce the same translation.
The tree transducers, which form the subject matter of Chapter 4, may be viewed as
further generalizations of gsm’s in which trees replace words as inputs and as outputs.
The following two theorems may be compared with some of the results to be presented
in Chapter 4.
44
1.8 References
Theorem 1.7.3 The equivalence problem of deterministic gsm’s is decidable, but the
equivalence problem of nondeterministic gsm’s is undecidable. ✷
Lemma 1.7.4 Let A be a gsm as defined above. For any two states a, b ∈ A, the
language
L(a, b) = {u ∈ X ∗ | au ⇒∗A bv for some v ∈ Y ∗ }
is regular. ✷
1.8 REFERENCES
Extensive treatments of universal algebra can be found in the following two standard
references:
• P. M. Cohn, Universal algebra, D. Reidel, Dordrecht (2. ed. 1981).
• G. Grätzer, Universal algebra, Springer-Verlag, New York (2. ed. 1979).
An extensive algebraic treatment of the theory of finite automata can be found in the
following two volumes:
• S. Eilenberg, Automata, languages, and machines, Academic Press, New York
(Vol. A 1974, Vol. B 1976).
The general area of formal language theory is covered, for example, by the following
books:
• A. V. Aho and J. D. Ullman, The theory of parsing, translation, and compiling,
Prentice-Hall, Englewood Cliffs, N. J. (1972).
45
1 PRELIMINARIES
46
2 TREE RECOGNIZERS AND
RECOGNIZABLE FORESTS
This chapter is devoted to finite-state tree recognizers and the family of forests recog-
nizable by them. Here trees are defined as terms over a finite operator domain, and a
forest (or tree language) is just a set of trees. As in the case of formal languages, there
are two particularly natural ways to effectively define a forest; a forest can be recognized
by an automaton, or it can be generated by a grammar. In Section 2.2 we introduce
the tree recognizers which correspond to Rabin–Scott recognizers. It does not make any
difference whether Rabin–Scott recognizers are defined to read words from left to right or
from right to left, but here we should consider both recognizers that read trees from the
leaves down towards the root (frontier-to-root recognizers) and recognizers which work
in the opposite direction (root-to-frontier tree recognizers). In both cases the recognizer
may be either deterministic or nondeterministic. This gives us four types of finite-state
tree recognizers. Three of these define the same family of forests, the family Rec of rec-
ognizable forests. Deterministic root-to-frontier recognizers are essentially weaker and
they define a proper subfamily of Rec. In Section 2.3 we define regular tree grammars.
After having shown that these can be reduced to a very simple normal form, we prove
that regular tree grammars generate exactly the recognizable forests. Often it will be
convenient to use regular tree grammars in the study of recognizable forests. In Section
2.4 several operations on forests are considered. Many of these arise as a generalization
of some basic language operation. Usually Rec can be shown to be closed under such
operations. However, one should note that there are often many ways to generalize from
languages to forests, and a right choice among the alternatives is essential if one wants to
generalize the corresponding results, too. For example, there is a natural generalization
of the product of languages with respect to which Rec is not even closed. A related point
is demonstrated by the case of tree homomorphisms. Here the greater generality of trees
compared with words admits of some entirely new phenomena, such as the copying of
subtrees.
In Section 2.5 regular expressions to denote forests are defined, and the appropriate
generalized Kleene theorem can then be proved. Section 2.6 contains the minimization
theory of deterministic frontier-to-root tree recognizers. In Sections 2.7 to 2.9 the family
Rec is characterized in some further ways. Recognizable forests are described by means
of congruences of the term algebra, as solutions of fixed-point equations, and in terms of
local forests. Moreover, a Medvedev-type characterization in terms of certain elementary
forests and elementary operations is given. In Section 2.10 we show that the emptiness,
the finiteness, and the equivalence problems of recognizable forests are decidable. Section
2.11 is devoted to deterministic root-to-frontier recognizers. The forests recognizable by
47
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
48
2.1 Trees and forests
γ x
y σ
Figure 2.1.
Term induction will now be called tree induction. Below some important concepts are
defined by tree induction.
Definition 2.1.2 The height hg(t), the root root(t) and the set of subtrees sub(t) of a
ΣX-tree t are defined as follows:
1◦ If t ∈ X ∪ Σ0 , then hg(t) = 0, root(t) = t and sub(t) = {t}.
For the tree of Example 2.1.1 we get hg(t) = 3, root(t) = ω and sub(t) = {t, σ (y, σ(γ, x)) ,
y, σ(γ, x), γ, x}.
Subtrees of height 0 are referred to as the leaves of the tree. A leaf is labelled by a
letter from the frontier alphabet or by a nullary operator. The length |t| of a tree t is
simply its length as a word. The leaves of tree t of our example are y, γ and x. Its length
is 15 (when parentheses and commas are counted, too). Of course, one can define and
prove things about trees by induction on the length; but in practice this mostly reduces
to tree induction. Induction on the height hg(t) is equivalent to tree induction.
We shall use the term frontier in a rather informal way to designate the part of a tree
consisting of the leaves. The frontier of the tree of Example 2.1.1 consists of the nodes
labelled by y, γ and x. The same letter or nullary operator could appear several times as
a leaf in the frontier. The visual picture of a tree also suggests the notions of a branch
and that of a path. In our t there are two main branches leaving the lower σ. They
correspond to the subtrees y and σ(γ, x). There are three paths from the root to the
frontier. They spell out the words ωσy, ωσσγ and ωσσx, respectively. These terms are
used in a descriptive manner to aid the intuition and no precise definitions are needed.
Note. In the literature the root is often called the “top” of the tree, while its frontier
is referred to as the “bottom”. Then “top-down” indicates the direction from the root
towards the frontier, and “bottom-up” means the opposite direction. This terminology
is connected with the common practice of drawing trees upside-down.
49
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
The same tree may occur several times as a subtree of a given tree and one should
distinguish between a subtree and an occurrence of a subtree. It is possible to assign
coordinates to the nodes of a tree and then indicate a certain occurrence of a subtree by
the coordinates of its root. However, the following simple device to specify an occurrence
of a subtree will suffice. For any occurrence of a subtree s of a tree t, there is a unique
way to write t = usv. Here u and v are just words and the occurrence of s is uniquely
determined by u.
We shall now consider some ways to construct new trees from given ones. The very
definition of FΣ (X) suggests such a construction. If m ≥ 0, σ ∈ Σm and t1 , . . . , tm ∈
FΣ (X), then σ(t1 , . . . , tm ) is a new ΣX-tree which could be called the σ-catenation of
t1 , . . . , tm . It is obtained by connecting the roots of the trees t1 , . . . , tm to a new root
labelled by σ. The construction is illustrated by Fig. 2.2.
γ x x x x z
t1 tm
d1 ... dm x σ σ
σ
σ
Figure 2.2. Figure 2.3.
Note that the σ-catenation is the σ-operation of the ΣX-term algebra FΣ (X):
Let t be a ΣX-tree and suppose we are given a tree sx for every x ∈ X. The tree
denoted by
t(x ← sx | x ∈ X), or just t(x ← sx ),
is obtained by substituting in t, simultaneously for every x ∈ X, sx for each occurrence
of x. The formal definition by tree induction reads as follows:
1◦ If t = z ∈ X, then t(x ← sx ) = sz .
2◦ If t = σ ∈ Σ0 , then t(x ← sx ) = σ.
3◦ If t = σ(t1 , . . . , tm ), then
If the trees sx are ΣX-trees, then t(x ← sx ) is also a ΣX-tree. However, the construc-
tion works also in the more general case where the trees sx are ΩY -trees for some Ω and
Y such that Σm ∩ Ωn = ∅ whenever m 6= n. Then t(x ← sx ) ∈ FΣ∪Ω (Y ).
Suppose X = {x1 , . . . , xn }. One may then write t(x ← sx ) in the more explicit form
50
2.1 Trees and forests
t(s1 , . . . , sn )A : AX → A
51
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
Of course, those forests only are of interest that can be defined in some natural way.
This chapter is devoted to a family of such forests, the forests recognizable by finite tree
automata. In the theory of these forests many concepts and results familiar from the
theory of recognizable languages can be perceived. The generalization from words and
languages to trees and forests will be considered in the next section.
52
2.2 Tree recognizers
If not otherwise specified, A will be the ΣX-recognizer (A, α, A′ ). Also B and C will
usually be the ΣX-recognizers (B, β, B ′ ) and (C, γ, C ′ ), respectively. Here B = (B, Σ)
and C = (C, Σ) are Σ-algebras, β : X → B and γ : X → C are the initial assignments,
and B ′ ⊆ B and C ′ ⊆ C.
In algebraic terms the operation of the ΣX-recognizer A can be explained as follows.
Given an input tree t ∈ FΣ (X) the polynomial function tA is evaluated on the initial
assignment α. The tree is accepted exactly in case the result tA (α) is a final state. If
α̂ : FΣ (X) → A
is the extension of α to a homomorphism, then
tA (α) = tα̂ for every t ∈ FΣ (X),
and we may write
T (A) = {t ∈ FΣ (X) | tα̂ ∈ A′ } = A′ α̂−1 .
A more pictorial description of the operation of A in automata theoretic terms is also
possible. Given an input tree t, A starts reading it from the leaves in states that depend
on the labels of the leaves. If a certain leaf is labelled by a frontier letter x, then A is
in state xα at that leaf. If the label is a nullary operator σ, then A starts from that
leaf in state σ A . Now A moves down all the branches towards the root step by step as
follows. If a given node v is labelled by the m-ary operator σ (m > 0), then A enters v
in state σ A (a1 , . . . , am ), where a1 , . . . , am are the states of A at the nodes immediately
above v, listed in order from left to right. The tree is accepted if A enters the root in a
final state.
Example 2.2.2 Let Σ = Σ1 ∪ Σ2 , Σ1 = {∼}, Σ2 = {∧, ∨} and X = {x, y}. Define the
operations of the Σ-algebra A = ({0, 1}, Σ) by the tables below:
53
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
∼ (1) ∨ (1)
∧ (1)
Figure 2.4.
Example 2.2.3 Let Σ = Σ2 = {+, ·} and X = {x1 , . . . , xn } for some n ≥ 1. The ΣX-
trees may now be interpreted as arithmetic expressions in variables x1 , . . . , xn . Using
the customary infix notation one could write, for example x1 + x1 · x2 rather than
+(x1 , ·(x1 , x2 )). Let m > 0 and define the Σ-algebra A = ({0, 1, . . . , m − 1}, Σ) so that
a +A b = a + b (mod m)
and
a ·A b = a · b (mod m)
for all a, b = 0, 1, . . . , m − 1. If t is a ΣX-tree and α : X → A is any mapping, then tA (α)
is the value of the expression t (mod m) when the variables are assigned values according
to α. Thus any ΣX-recognizer A = (A, α, A′ ) based on the algebra A recognizes a set of
arithmetic expressions which get a value (mod m) in A′ when each variable xi is given
a certain value xi α (i = 1, . . . , n). ✷
The examples suggest some useful general observations on tree recognizers. A tree
recognizer is a device that evaluates an expression (a tree) for given values of the variables
(given by the initial assignment) and decides then on the basis of this value whether the
expression belongs to given set or not. Since the state set is finite such an evaluation
is always “modulo something”. For example, we could not construct a tree recognizer
which would find out whether the value of an arithmetic expression is a prime or not.
Similarly, there is no tree recognizer that recognizes the set of all trees in which two given
operators appear the same number of times. The following example discusses another
manifestation of the same phenomenon.
Example 2.2.4 Let Σ = Σ2 = {σ} and let X be an arbitrary nonempty frontier alpha-
bet. Then the forest
T = {σ(t, t) | t ∈ FΣ (X)}
is not recognizable. For suppose T = T (A) for some ΣX-recognizer A. Since A is finite,
there must exist two different ΣX-trees s and t such that sα̂ = tα̂. But then we would
have that
σ(s, t)α̂ = σ A (sα̂, tα̂) = σ A (sα̂, sα̂) = σ(s, s)α̂ ∈ A′ ,
which implies the contradiction σ(s, t) ∈ T . ✷
54
2.2 Tree recognizers
Let us now look how tree recognizers arise as generalizations of the Rabin–Scott recog-
nizers through a universal algebraic interpretation. First, let A = (A, I, δ, a0 , A′ ) be an
I-recognizer as defined in Sect. 1.5 (to avoid confusion we use I as the input alphabet).
Define a ranked alphabet Σ such that Σ1 = I and Σm = ∅ for all m 6= 1. The next-state
mapping of A is completely determined by the Σ-algebra A = (A, Σ) which is defined
so that
σ A (a) = δ(a, σ) for all a ∈ A and σ ∈ I.
If we put X = {x}, then I-words and ΣX-trees can be identified as follows. The empty
word e corresponds to the tree x, and a nonempty word σ1 . . . σk (k ≥ 1, σi ∈ I) may
be interpreted as the tree σk (. . . σ1 (x) . . .) (the reverse Polish notation for trees would
make the identification even more natural). Define α : X → A so that xα = a0 . Then
This implies that the forest recognized by the ΣX-recognizer (A, α, A′ ) is, interpreted
as an I-language, the language recognized by A. Hence a Rabin–Scott recognizer may
be viewed as a tree recognizer over a unary ranked alphabet and a one-element frontier
alphabet. The general ΣX-recognizers result when one does not require Σ to be unary
and allows also an arbitrary frontier alphabet X.
The nondeterministic frontier-to-root tree recognizers that we soon shall define may
be viewed as generalized F -tree recognizers in which nondeterminism is allowed both in
the assignment of states to the leaves and in the next-state behaviour. First we have to
introduce nondeterministic operations and nondeterministic algebras.
An m-ary nondeterministic (ND) operation on a set A is a mapping from Am to pA
(m ≥ 0). Thus an m-ary ND operation
f : Am → pA
f : {∅} → pA
fixes a subset of A, and f may be identified with this subset f (∅). A nondeterministic
(ND) Σ-algebra A = (A, Σ) consists of a nonempty set A and a family {σ A | σ ∈ Σ} of
ND operations on A such that for each σ ∈ Σ, σ A is m-ary if σ ∈ Σm . The ND Σ-algebra
is finite if A is finite. A Σ-algebra may be viewed as an ND Σ-algebra when elements
a ∈ A are identified with the corresponding singletons {a}.
On the other hand, we associate with every ND Σ-algebra A = (A, Σ) an ordinary
Σ-algebra, namely the subset algebra
pA = (pA, Σ)
where [
σ pA (A1 , . . . , Am ) = σ A (a1 , . . . , am ) | a1 ∈ A1 , . . . , am ∈ Am
55
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
α : X → pA
α̂ : FΣ (X) → pA.
Consider a ΣX-tree t. The computation of the set tα̂ may be described in automata
theoretic terms as follows. If a leaf is labelled by a letter x, then the “automaton” A
may start at that leaf in any one of the states in xα. If a leaf is labelled by a nullary
operator, then σ A is the set of the possible starting states. Let v be any node in the
tree labelled by an m-ary symbol σ (m > 0). Let σ(t1 , . . . , tm ) be the subtree of t
which has v as its root. Then t1 α̂, . . . , tm α̂ are the respective sets of possible states of
A at the nodes immediately above v. Now A may enter v in any one of the states from
σ pA (t1 α̂, . . . , tm α̂). Clearly, tα̂ is the set of all states in which A may be at the root of t.
pA = (pA, α, A′′ ),
where
A′′ = {A1 ∈ pA | A1 ∩ A′ 6= ∅},
recognizes the same forest as A. Indeed, for any t ∈ FΣ (X),
56
2.2 Tree recognizers
σ A : A → p(Am ).
α̃ : FΣ (X) → pA
is defined as follows:
57
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
2◦ If σ ∈ Σ0 , then σ α̃ = σ A .
Example 2.2.9 Let us consider again the arithmetic expressions, defined in Example
2.2.3. We shall construct an NDR Σ{x1 , x2 }-recognizer which accepts an expression in
variables x1 and x2 iff the value of the expression is divisible by 4 when x1 = 0 or 2 (mod
4) and x2 = 3 (mod 4). An obvious choice for a state set is A = {0, 1, 2, 3}. The set of
initial states is {0}, and the final assignment is defined by x1 α = {0, 2} and x2 α = {3}.
The next-state behaviour is determined by inferring the possible summands or factors
from the sum or product, respectively. We get
(1) A = B, A′ = B ′ and α = β,
It easy to see that α̂ = β̃ if A and B are associated. Since every NDF tree recognizer
has an associated NDR tree recognizer, and conversely, we get
Theorem 2.2.10 The forests recognizable by NDR tree recognizers are exactly the rec-
ognizable forests. ✷
58
2.3 Regular tree grammars
The inability of these recognizers to cope with situations such as that in Example
2.2.11 is due to the fact that they have to read disjoint subtrees separately without any
possibility to combine the information gathered from the individual subtrees. In an NDR
tree recognizer this handicap is compensated for by their ability to make several guesses
about the subtrees jointly before reading them separately.
When Σ and X are not specified, we speak about regular tree grammars or just gram-
mars, if there is no danger of confusion.
Let G be a regular tree grammar as in the definition above. The right-hand side of a
production is a tree in which nonterminal symbols may appear at the leaves only. For
p, q ∈ FΣ (X ∪ N ), we write
p ⇒G q (or just p ⇒ q)
59
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
p ⇒G p1 ⇒G . . . ⇒G pn−1 ⇒G q (n ≥ 1)
x b x σ
x σ x σ
ω a ω σ ω σ
a ⇒ ⇒ σ ⇒ σ
σ
Figure 2.5.
60
2.3 Regular tree grammars
61
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
We say that a regular tree grammar is in normal form if each of its productions is of
type (i), (ii) or (iii). The previous discussion amounts to the following lemma.
Lemma 2.3.4 Every regular tree grammar can be transformed into an equivalent regular
tree grammar in normal form. ✷
Example 2.3.5 None of the productions of the grammar considered in Example 2.3.3
is in normal form. The production a → σ(x, σ(x, b)) can be replaced by the following
set:
a → σ(a1 , a2 ), a1 → x, a2 → σ(a1 , b).
Notice that we could use the new nonterminal symbol a1 twice since in both functions
it should be rewritten as x. Similarly, the production a → σ(ω, a) is replaced by the two
productions
a → σ(a3 , a) and a3 → ω,
and the production b → σ(x, x) is replaced by b → σ(a1 , a1 ) (we already have a1 → x).
We have got a grammar in normal form with five nonterminal symbols a, b, a1 , a2 and
a3 , and the productions
G = (N, Σ, X, P, A′ )
It is immediately clear that every language generated by an extended regular tree gram-
mar can be generated by an ordinary regular tree grammar, too.
Theorem 2.3.6 The forests generated by regular tree grammars are exactly the recog-
nizable forests.
62
2.3 Regular tree grammars
where
P = {a → x | x ∈ X, a ∈ xα} ∪ {a → σ | σ ∈ Σ0 , a ∈ σ A }∪
{a → σ(a1 , . . . , am ) | m ≥ 1, σ ∈ Σm , a, a1 , . . . , am ∈ A, a ∈ σ A (a1 , . . . , am )}.
The grammar G is in normal form (i.e., the productions are of type (i)–(iii)). It is clear
that every extended regular ΣX-grammar in normal form arises this way from a NDF
ΣX-recognizer. To prove the theorem it suffices now to show that T (A) = T (G) for
such an associated pair A and G. To do this we show by tree induction that
a ⇒ σ(a1 , . . . , am ) ⇒∗ σ(t1 , . . . , tm ),
where a1 , . . . , am ∈ N and
ai ⇒ ∗ t i for i = 1, . . . , m.
a ∈ σ A (a1 , . . . , am )
a ⇒ σ(a1 , . . . , am ) ⇒∗ σ(t1 , . . . , tm ) = t.
This completes the proof of (*), and we have for every ΣX-tree t,
63
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
Of course, the lemma presupposes the point of view that every ΣX-forest is also an
ΩY -forest. Now let Σ and Ω be any ranked alphabets such that Σm ∩ Ωn = ∅ whenever
m 6= n. Also, let X and Y be arbitrary frontier alphabets. The lemma implies that if
S ∈ Rec(Σ, X) and T ∈ Rec(Ω, Y ), then S and T can be regarded as recognizable forests
over a common ranked alphabet Σ ∪ Ω and a common frontier alphabet X ∪ Y .
Then
tγ̂ = (tα̂, tβ̂) for all t ∈ FΣ (X).
This implies that we get from C and γ ΣX-recognizers for S ∩ T , S ∪ T and S − T by
choosing, respectively, as the set of final states A′ ×B ′ , A′ ×B ∪A×B ′, and A′ ×(B −B ′ ).
For example, let
C = (C, γ, A′ × B ′ ).
For any t ∈ FΣ (X),
64
2.4 Operations on forests
1◦ If t = z ∈ X, then t(x ← Tx ) = Tz .
2◦ If t = σ ∈ Σ0 , then t(x ← Tx ) = σ.
The forest product of the family (Tx | x ∈ X) with the ΣX-forest T is defined as the
ΣX-forest [
T (x ← Tx | x ∈ X) = (t(x ← Tx | x ∈ X) | t ∈ T ).
T (x ← Tx ) = t(x ← Tx ).
The trees t(x ← Tx ) are obtained from t by replacing every occurrence of each letter x
by a tree from the corresponding forest Tx . Different occurrences of the same letter x
may be rewritten as different trees from Tx .
If x1 , . . . , xn ∈ X, then we use the notation
T (x1 ← T1 , . . . , xn ← Tn )
If the letters x1 , . . . , xn and their order are understood, then this notation may be further
simplified to T (T1 , . . . , Tn ).
The comments presented at the beginning of the section show that the definition of
forest products also includes the cases, where T ⊆ FΣ (X) and Tx ⊆ FΩ (Y ) (x ∈ X) for
any such alphabets that Σm ∩ Ωn = ∅ whenever m 6= n. If T is a ΣX-forest and the
forests Tx are ΩY -forests, then T (x ← Tx ) is a (Σ ∪ Ω)Y -forest.
65
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
The trees in S ·z T are obtained by taking a tree t from T and substituting a tree from
S for every occurrence of z in t. Different occurrences of z may be replaced by different
trees from S.
Proof. Here it is convenient to use regular tree grammars. Suppose T and the forests
Tx (x ∈ X) are generated by the regular ΣX-grammars G = (N, Σ, X, P, a0 ) and Gx =
(Nx , Σ, X, Px , ax ) (x ∈ X), respectively. We may assume that the grammars are in
normal form and that their sets of nonterminal symbols are pairwise disjoint. Construct
a regular ΣX-grammar
G′ = (N ′ , Σ, X, P ′ , a0 )
S
with N ′ = N ∪ (Nx | x ∈ X) and
[
P ′ = P ′′ ∪ {a → ax | x ∈ X, a → x ∈ P } ∪ (Px | x ∈ X),
a ⇒G′ az ⇒G′ y.
On the other hand, all derivations of y from a in G′ are of this form. Hence, if
a ⇒∗G′ y, then a → az , az → y ∈ P ′ for some z ∈ X. This means that a → z ∈ P
and az → y ∈ Pz , and thus z is the required tree q.
2◦ Let p = σ ∈ Σ0 .
(2a) If there is a q such that a ⇒∗G q and σ ∈ q(x ← Tx ), then there are two
possibilities. The first one is that q = σ. Then P and P ′ both contain a → σ
and we get the required derivation a ⇒∗G′ σ in one step. The other possibility
66
2.4 Operations on forests
a ⇒G′ ax ⇒G′ σ.
a ⇒G′ az ⇒∗G′ p.
q = σ(q1 , . . . , qm )
pi ∈ qi (x ← Tx ) (i = 1, . . . , m)
a ⇒G σ(a1 , . . . , am )
such that
ai ⇒∗G qi for i = 1, . . . , m.
Our silent inductive assumption yields
ai ⇒∗G′ pi for i = 1, . . . , m.
ai ⇒∗G qi , pi ∈ qi (x ← Tx ) (i = 1, . . . , m).
67
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
Next we generalize the iteration operation taking the x-products as the starting point.
Definition 2.4.7 Let T be any ΣX-forest and let x ∈ X. Put T 0,x = {x} and
(1) N ′ = N ∪ {d} (d 6∈ N ),
(2) P ′ = P ∪ {d → x} ∪ {a → r | a → x ∈ P, a0 → r ∈ P }, and
A tree p is in S −x T iff one can convert it into a tree in T by substituting for every
occurrence of x a tree from S. If Σ is unary and X = {x}, and if we identify the tree
σk (. . . σ1 (x) . . .) with the word σ1 . . . σk , then
S −x T = S −1 T = {u ∈ Σ∗ | Su ∩ T 6= ∅}
68
2.4 Operations on forests
Next we introduce the forest operation corresponding to the σ-catenation of trees which
was defined in Section 2.1.
Definition 2.4.11 Let σ ∈ Σ be an m-ary operator and let T1 , . . . , Tm be m ΣX-forests
for some m ≥ 0. The σ-product of the forests T1 , . . . , Tm is the forest
σ(T1 , . . . , Tm ) = {σ(t1 , . . . , tm ) | t1 ∈ T1 , . . . , tm ∈ Tm }.
If m = 0, then the σ-product is always {σ}. In general,
σ(T1 , . . . , Tm ) = {σ(x1 , . . . , xm )}(x1 ← T1 , . . . , xm ← Tm ).
From Theorem 2.4.6 we get the following result which could easily be proved directly,
too.
Corollary 2.4.12 If σ ∈ Σm and T1 , . . . , Tm ∈ Rec(Σ, X) (m ≥ 0), then σ(T1 , . . . , Tm ) ∈
Rec(Σ, X). ✷
We shall now consider some operations in which forests are generally transformed into
forests over another ranked alphabet. The ranked alphabets will be Σ and Ω. Moreover,
we introduce for every m ≥ 0, a new alphabet
Ξm = {ξ1 , . . . , ξm }
which is assumed to be disjoint from all other alphabets.
69
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
hX : X → FΩ (Y )
hm : Σm → FΩ (Y ∪ Ξm ).
h : FΣ (X) → FΩ (Y )
defined as follows:
The tree homomorphism h is said to be linear if no letter ξi appears more than once in
hm (σ) for any m ≥ 0 and σ ∈ Σm .
To define such an h it obviously suffices to give hX and the mappings hm for which
Σm 6= ∅.
If we interpret | as the Sheffer stroke (i.e., the 2-place NAND), ∨ as the symbol of
disjunction and ′ as the symbol of negation, then the tree homomorphism h defined
by hX and h2 transforms |-expressions in variables x and y into equivalent expressions
which use ∨ and ′ only. If the more customary way to write Boolean expressions is used,
we get, for example,
Tree homomorphisms are not really homomorphisms in the sense of algebra. The
concept is the result of the dual nature of words. When one generalizes from languages
to forests, words are usually treated as unary terms. On the other hand, many concepts in
language theory arise from the interpretation of words as elements of a free monoid. Here
the initial concept was that of a homomorphism from the free monoid generated by an
alphabet Σ to the free monoid generated by another alphabet Ω. Such a homomorphism
rewrites every letter in a word over Σ as a word over Ω. When Σ and Ω are now viewed
70
2.4 Operations on forests
as unary ranked alphabets, this means that every operator from Σ is rewritten as a piece
of Ω-tree to be combined with other such pieces to form the image of a given Σ-word.
The generalization of such mappings to the case of arbitrary ranked alphabets gives tree
homomorphisms.
The following example shows that tree homomorphisms do not always preserve recog-
nizability.
would imply ω(si , sj ) ∈ h(FΣ (X)). Thus h(FΣ (X)) cannot be recognizable. ✷
h′0 : Σ0 ∪ N → FΩ′ (Y )
71
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
G′ = (N, Ω, Y, P ′ , a0 )
P ′ = {a → h′ (p) | a → p ∈ P },
holds for all a ∈ N and t ∈ FΩ (Y ). We prove the two directions of (*) separately.
Suppose a ⇒∗G′ t for some a ∈ N and ΩY -tree t. We prove the existence of the required
s by induction on the length of the shortest derivation of t from a.
a ⇒G r ⇒∗G s,
2◦ Suppose now that the derivation consists of k steps (k > 1) and that (*) holds
whenever a shorter derivation exists. The first step must be the application of a
production a → h′ (p), where a → p ∈ P . Since G is in normal form,
p = σ(a1 , . . . , am )
ai ⇒G′ . . . ⇒G′ ti (∈ FΩ (Y ))
of length less than k. The linearity of h implies that such a ξi appears in hm (σ)
exactly once, and hence ti is unique. For every ti there is an si ∈ FΣ (X) such that
h(si ) = ti and ai ⇒∗G si . If a certain ξi does not appear in hm (σ), then we choose
72
2.4 Operations on forests
any si ∈ FΣ (X) such that ai ⇒∗G si and put ti = h(si ). With these choices we get
a tree
s = σ(s1 , . . . , sm ) ∈ FΣ (X)
such that
a ⇒G σ(a1 , . . . , am ) ⇒∗G σ(s1 , . . . , sm ) = s
and
h(s) = hm (σ)(ξ1 ← h(s1 ), . . . , ξm ← h(sm )) = t.
Now we shall prove the converse part of (*). Suppose a ⇒∗G s and h(s) = t for some
a ∈ N , s ∈ FΣ (X) and t ∈ FΩ (Y ). To show that this implies a ⇒∗G′ t we proceed by
induction on the length of the shortest derivation a ⇒G . . . ⇒G s.
a ⇒G σ(a1 , . . . , am ) ⇒G . . . ⇒G σ(s1 , . . . , sm ) = s,
a → hm (σ)(ξ1 ← a1 , . . . , ξm ← am )
73
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
sβ̂ = h(s)α̂
for all s ∈ FΣ (X). Hence, s ∈ T (B) iff h(s) ∈ T (A). This means that h−1 (T ) = T (B)
is recognizable. ✷
As a conclusion we consider a simple, but very important special type of tree homo-
morphisms.
74
2.5 Regular expressions. Kleene’s theorem
Definition 2.5.1 The set of regular ΣZ-expressions RE(Σ, Z) is defined as the smallest
set RE such that the following conditions are satisfied:
1◦ ∅ ∈ RE.
2◦ Σ0 ∪ Z ⊆ RE.
Thus regular ΣZ-expressions are strings of symbols from Σ ∪ Z, of commas etc. Parts
2◦ and 6◦ of the definition imply that every ΣZ-tree is a regular ΣZ-expression. Regular
expressions are intended as representations of forests.
5◦ |(ζ ∗z )| = |ζ|∗z .
75
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
Note that the operations in the right-hand sides of 3◦ − 6◦ are forest operations which
have been defined in Section 2.4. It is easy to see that every tree t ∈ FΣ (Z) represents,
as a regular expression, the one-element forest {t}.
With this interpretation in mind we may simplify regular expressions by omitting
parentheses that are not needed in order to specify the intended order of the opera-
tions. First of all, the outermost parentheses in (ζ + η), (ζ ·z η) and (ζ ∗z ) are obviously
superfluous if the expressions do not appear as parts of other expressions. We may
also agree that iterations precede products and that products precede unions. Then the
parentheses around ζ ∗z can always be omitted and, for example,
ζ + η ·x θ ∗y
(ζ + (η ·x (θ ∗y ))).
Example 2.5.3 Let Σ = Σ0 ∪ Σ2 , Σ0 = {ω} and Σ2 = {σ} and Z = {x, y}. The forest
represented by
η = ω ·y σ(x, y)∗y
contains the trees ω, σ(x, ω), σ(x, σ(x, ω)) etc. Note that y has a purely auxiliary
function; it does not appear in any tree of the forest |η|. ✷
In the following definition we make the formal distinction between letters that may
appear in trees of the forest represented by a regular expression and those letters that
are used just to mark leaves to be rewritten when products of forests are formed.
ζ = u(η ·z θ)v
2◦ For each z ∈ Z, Zz = {z} and |z| = {z} ∈ Rec(Σ, {z}). For σ ∈ Σ0 , Zσ = ∅, but
still |σ| = {σ} ∈ Rec(Σ, ∅).
76
2.5 Regular expressions. Kleene’s theorem
4◦ If η = ζ ·z θ, then (if we omit the trivial case z 6∈ Zθ , |η| = |θ|) Zη = Zζ ∪ (Zθ − z).
There are two cases to consider. If z 6∈ Zζ , then Zη = (Zζ ∪ Zθ )− z. From Theorem
2.4.6 we know that |η| ∈ Rec(Σ, Zζ ∪ Zθ ). Thus it suffices to show that no tree
t ∈ |η| contains any occurrence of z. But this is obvious since every such t is
obtained from some s ∈ |θ| by replacing every occurrence of z by a tree from |ζ|,
and no tree in |ζ| contains z. If z ∈ Zζ , then Zη = Zζ ∪ Zθ and |η| ∈ Rec(Σ, Zη )
follows directly from Theorem 2.4.6.
The operations (finite) union, z-product and z-iteration are called the regular opera-
tions. A forest is regular if it can be constructed from finite forests by applying a finite
number of regular operations. In view of the preceding discussion regularity can also be
defined as follows:
Lemma 2.5.7 For any ΣX-recognizer A one can construct a regular expression η ∈
RE(Σ, X ∪ A) (we assume X ∩ A = ∅) such that |η| = T (A).
Proof. The proof is modelled after the almost standard proof for the corresponding fact
in the language case (due to R. McNaughton and H. Yamada (1960)). The notation can
be simplified by assuming that
(1) tα = i and
77
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
1◦ When h = 0, no intermediate states between the frontier and the root are allowed.
Every tree t in T (K, 0, i) must hence be of one of the following types:
(i) t = x ∈ X and xα = i.
(ii) t = i ∈ K.
(iii) t = σ ∈ Σ0 with σ A = i.
(iv) t = σ(d1 , . . . , dm ) with m > 0, dj ∈ X ∪ Σ0 ∪ K (j = 1, . . . , m) and tα = i.
In each case a regular expression for {t} can be written. The number of such trees
t is finite and we get a regular expression for T (K, 0, i).
2◦ Suppose we already have a regular expression for each T (K, j, i) such that j ≤ h
for some h < k. We show that
T (K, h + 1, i) = (*)
T (K, h, i) ∪ T (K, h, h + 1) ·h+1 T (K ∪ h + 1, h, h + 1)∗h+1 ·h+1 T (K ∪ h + 1, h, i)
holds for all K ⊆ A and i ∈ A. This will complete the induction because the
right-hand side of (*) is obtained by regular operations from forests for which we
already have regular expressions.
Let T be the right-hand side of (*). From the construction of T it is obvious that
T ⊆ T (K, h + 1, i). If t ∈ T (K, h + 1, i), then either t ∈ T (K, h, i) or t has a proper
subtree s 6∈ X ∪ Σ0 such that sα = h + 1. In the former case we get t ∈ T directly.
In the second case we have
t ∈ {p1 , . . . , pd } ·h+1 {q11 , . . . , q1e1 } ·h+1 . . . ·h+1 {qj1 , . . . , qjej } ·h+1 {r},
for some
p1 , . . . , pd ∈ T (K, h, h + 1), q11 , . . . , q1e1 , . . . , qj1 , . . . , qjej ∈ T (K ∪ h + 1, h, h + 1)
and r ∈ T (K ∪ h + 1, h, i). This means that t belongs to the second part of T . ✷
Combining Lemma 2.5.5 and Lemma 2.5.7 we get the following generalized form of
Kleene’s theorem.
78
2.6 Minimal tree recognizers
(2) αϕ = β, and
(3) B ′ ϕ−1 = A′ .
Part (3) of Definition 2.6.1 means that the final states, and these only, map to final
states in a homomorphism. If ϕ is an epimorphism, then (3) implies A′ ϕ = B ′ .
Proof. The clauses (1) and (2) of Definition 2.6.1 imply together with Lemma 1.3.6 that
79
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
Lemma 2.6.4 C(A) is a principal ideal of the complete lattice C(A), and thus (C(A),
⊆) is a complete lattice itself, too.
In Theorem 2.6.10 we shall get a more useful description of the greatest element of
C(A).
The usual relations between homomorphisms, congruences and quotients hold for tree
recognizers, too. Some of them are listed in the following theorem. We omit the proofs
since they can be constructed exactly as the corresponding proofs in algebra.
̺♮ : A → A/̺, a 7→ a̺ (a ∈ A),
80
2.6 Minimal tree recognizers
To get a better intuitive grasp of this definition we recall the fact that for each algebraic
function f ∈ Alg1 (A) there exists a tree t ∈ FΣ (A ∪ ξ) such that for all a ∈ A,
f (a) = tα̂a ,
(a) reduced if ∼A = δA ,
(b) connected if every state of A is reachable, i.e., there exists for every a ∈ A a tree
t ∈ FΣ (X) such that tα̂ = a, and A is
81
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
That a recognizer is reduced means that no two distinct states are equivalent. To
be connected means that every state is possible in some computation performed by
the recognizer on some tree. By Lemma 1.3.8, a tree recognizer A is connected iff
Xα generates A. In the case of a finite recognizer minimality really means a minimal
number of states among equivalent recognizers. If a recognizer is not connected, then
the nonreachable states can be discarded without changing the forest recognized. If A is
finite and ∼A > δA , then A/∼A is a properly smaller recognizer equivalent to A. Hence,
a finite tree recognizer can be minimal with respect to the number of states only if it is
minimal in the sense of Definition 2.6.9. The converse will be established later.
f ◦ g : ξ 7→ g(f (ξ)) (ξ ∈ A)
The quotient recognizer A/∼A is often called the reduced form of A. It is clear
from Theorem 2.6.10 that two tree recognizers having isomorphic reduced forms are
equivalent. We show that the converse holds for connected recognizers. In other words,
equivalent minimal recognizers are shown to be isomorphic.
Theorem 2.6.11 Let A and B be two minimal tree recognizers. If A and B are equiv-
alent, then they are also isomorphic.
82
2.6 Minimal tree recognizers
We show that ϕ gives the required isomorphism from A to B. This involves the following
seven points:
(ii) To show that ϕ is well-defined we consider the possibility that sα̂ = tα̂ for two
ΣX-trees s and t. If sβ̂ 6= tβ̂, then sβ̂ and tβ̂ are nonequivalent and there exists
an algebraic function f ∈ Alg1 (B) such that f (sβ̂) ∈ B ′ and f (tβ̂) 6∈ B ′ (or
conversely). By Lemma 1.3.14 there exists a tree p ∈ FΣ (B ∪ ξ) (ξ 6∈ B ∪ X) such
that for all b ∈ B,
f (b) = pB (βb ),
where βb : B ∪ ξ → B is defined so that βb |B = 1B and ξβb = b. Since B is
connected there exists for each b ∈ B a ΣX-tree pb such that pb β̂ = b. Let
qs β̂ = pB (βsβ̂ ) = f (sβ̂) ∈ B ′
and
qt β̂ = pB (βtβ̂ ) = f (tβ̂) 6∈ B ′ .
If we assign in q to every letter x ∈ X the value xα, we get a function g ∈ Alg1 (A)
such that for each a ∈ A,
g(a) = q A (αa )
where αa : X ∪ ξ → A is defined so that αa |X = α and ξαa = a. Applying Lemma
1.3.6 we get now
g(sα̂)ϕ = q A (αsα̂ )ϕ = qs α̂ϕ = qs β̂ ∈ B ′
and
g(tα̂)ϕ = q A (αtα̂ )ϕ = qt α̂ϕ = qt β̂ 6∈ B ′ .
This is in contradiction with our original assumption that sα̂ = tα̂. Hence qs ∈
T (B), but qt 6∈ T (B). On the other hand, sα̂ = tα̂ implies qs α̂ = qt α̂, and a
contradiction with our assumption that T (A) = T (B) results.
(iii) Reversing the roles of A and B in Part (ii) one sees that sβ̂ = tβ̂ implies sα̂ = tα̂
for all ΣX-trees s and t. This means that ϕ is injective.
83
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
(vii) If tα̂ ∈ A′ (t ∈ FΣ (X)), then tα̂ϕ = tβ̂ ∈ B ′ since t ∈ T (A) = T (B). Similarly,
tα̂ϕ ∈ B ′ implies tα̂ ∈ A′ . Hence, B ′ ϕ−1 = A′ . ✷
Corollary 2.6.12 If A and B are connected ΣX-recognizers such that T (A) = T (B),
then A/∼A ∼
= B/∼B . ✷
FT = (FΣ (X), 1X , T )
where FΣ (X) = (FΣ (X), Σ) is the ΣX-term algebra. Indeed, for each t ∈ FΣ (X) we
have
tFΣ (X) (1X ) = t ∈ T (FT ) iff t ∈ T.
Obviously FT is connected. Hence, FT /∼ is a minimal recognizer for T (the relation ∼
will be examined more closely in the next section). To show it we shall verify that every
quotient recognizer of a connected tree recognizer is connected.
Let ϕ : A → B be an epimorphism of ΣX-recognizers. If A is connected, then so is
B. Indeed, let b be any state of B. There exists an a ∈ A such that aϕ = b. Since A is
connected there is a tree t ∈ FΣ (X) so that a = tA (α). Using Lemma 1.3.6 we get
Theorem 2.6.13 For every forest T there exists a minimal tree recognizer, and it is
unique up to isomorphism. If A is any connected recognizer of T , then the minimal
recognizer is an epimorphic image of A. In fact, A/∼A is minimal. ✷
The theorem is valid for every forest. It suggests the following two-step procedure for
finding the minimal recognizer for T once any recognizer A of T is given:
84
2.7 Algebraic characterizations of recognizability
85
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
Theorem 2.7.1 For every ΣX-forest T the following three conditions are equivalent:
(ii) The term algebra FΣ (X) has a congruence of finite index which saturates T .
The corollary gives, in fact, just an obvious reformulation of the definition of recog-
nizability. Without going into the subject any further here, we note that in this form
recognizability may be defined for subsets of arbitrary algebras (and not just term al-
gebras): a subset T of a Σ-algebra A is said to be recognizable, if there exist a finite
Σ-algebra B, a homomorphism ϕ : A → B and a subset H ⊆ B such that Hϕ−1 = T .
If here A = FΣ (X), then we get the recognizable ΣX-forests, and if A is the free
monoid X ∗ , then we get the recognizable X-languages.
As an introduction to the theory of fixed-point equations we first look at an example
of Arden equations.
Example 2.7.3 Consider the two-state Rabin-Scott recognizer A defined by the state
graph shown in Fig. 2.6. The input alphabet is Σ = {σ, τ }.
Let L1 and L2 be the languages of all words taking A from the initial state 1 to state
1 and 2, respectively. Then the following equations hold:
L1 = L1 σ ∪ L2 σ ∪ e
(1)
L2 = L1 τ ∪ L2 τ .
86
2.7 Algebraic characterizations of recognizability
σ σ τ
1 2
τ
Figure 2.6.
If we define a mapping
Π̂ : (pΣ∗ )2 → (pΣ∗ )2
so that for all U, V ⊆ Σ∗ ,
Π̂(U, V ) = (U σ ∪ V σ ∪ e, U τ ∪ V τ ) ,
then (1) means that (L1 , L2 ) is a solution of the fixed-point equation
(v1 , v2 ) = Π̂(v1 , v2 ) . (2)
Moreover, (L1 , L2 ) is the least solution of (2) when (pΣ∗ )2 is partially ordered in the
natural way:
(U1 , V1 ) ≤ (U2 , V2 ) iff U1 ⊆ U2 and V1 ⊆ V2 .
If we view Σ as a unary ranked alphabet and identify Σ{x}-trees and Σ-words as shown
in Section 2.2 (x = e, σk (· · · σ1 (x) · · · ) = σ1 · · · σk ), then the term algebra FΣ ({x}) may
be taken to be
F = (Σ∗ , Σ) ,
where
σ F (u) = uσ (σ ∈ Σ, u ∈ Σ∗ ) .
In the corresponding subset algebra
pF = (pΣ∗ , Σ)
we have the operations
σ pF (L) = Lσ (σ ∈ Σ, L ⊆ Σ∗ ) .
The mapping Π̂ can be defined in terms of these operations, the empty word and unions:
Π̂(U, V ) = σ pF (U ) ∪ σ pF (V ) ∪ x, τ pF (U ) ∪ τ pF (V ) .
Using forest products we may write this as follows:
Π̂(U, V ) = {σ(v1 ), σ(v2 ), x}(v1 ← U, v2 ← V ) ,
(3)
{τ (v1 ), τ (v2 )}(v1 ← U, v2 ← V ) .
Finally, we write (2) in the more readable form
v1 = σ(v1 ) + σ(v2 ) + x
(4)
v2 = τ (v1 ) + τ (v2 )
as a system of equations to be solved in the forest algebra pF which is augmented by
union as an operation. Union is denoted here by +. ✷
87
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
It is obvious that Example 2.7.3 could be repeated for any regular language and that
the language itself is always the union of those components of the minimal fixed-point
which correspond to final states. The interpretation of the equations in terms of forest
operations serves as the starting point for a generalization to equations for regular forests.
Fix again a ranked alphabet Σ and a frontier alphabet X. For any k ≥ 1, let
Fk = (pFΣ (X))k
Then Fk becomes a complete lattice in which least upper bounds and greatest lower
bounds are obtained, respectively, by forming componentwise unions and intersections,
thus
_ [ [
(Si1 , . . . , Sik ) | i ∈ I = (Si1 | i ∈ I), . . . , (Sik | i ∈ I)
and
^ \ \
(Si1 , . . . , Sik ) | i ∈ I = (Si1 | i ∈ I), . . . , (Sik | i ∈ I) .
The least element is 0 = (∅, . . . , ∅). (We refer the reader to Section 1.4 for the lattice
theory needed here.)
Let Vk = {v1 , . . . , vk } be a set of variables disjoint from Σ and X. With every Σ(X ∪
Vk )-forest P we associate the mapping
P̂ : Fk → pFΣ (X)
defined so that
P̂ (T1 , . . . , Tk ) = P (v1 ← T1 , . . . , vk ← Tk )
for all (T1 , . . . , Tk ) ∈ Fk . A k-tuple Π = (P1 , . . . , Pk ) of finite Σ(X ∪ Vk )-forests is called
a (Σ, X, k)-polynomial and we associate with it the mapping
Π̂ : Fk → Fk
defined so that
Π̂(T) = P̂1 (T), . . . , P̂k (T) (T ∈ Fk ) .
P (v1 ← S1 , . . . , vk ← Sk ) ⊆ P (v1 ← T1 , . . . , vk ← Tk )
88
2.7 Algebraic characterizations of recognizability
Ti = (Ti1 , . . . , Tik ) ∈ Fk (i ≥ 0)
or equivalently, that
[
P̂j (T) = P̂j (Ti ) | i ≥ 0 (j = 1, . . . , k) . (5)
S
Every tree t ∈ P̂j (T) is obtained from some p ∈ Pj by substituting a tree from (Tim |
i ≥ 0) for every occurrence of each variable vm and each m = 1, . . . , k. The number of
occurrences of variables in p is finite. Hence there exists an i ≥ 0 such that all trees used
in this substitution appear in a component of Ti . Then t ∈ P̂j (Ti ). This shows that the
left side of (5) is included in the right side of (5) for each j = 1, . . . , k. The converse
inclusions are obvious since Π̂ is isotone and Ti ≤ T for all i ≥ 0. ✷
Corollary 2.7.5 For any (Σ, X, k)-polynomial Π, the mapping Π̂ : Fk → Fk has the
least fixed-point
_
[Π̂] = (00Π̂i | i ≥ 0) . ✷
The corollary means that [Π̂] is the least solution of the fixed-point equation
where the vi ’s are “unknowns” that assume ΣX-forests as their values. The equation (6)
can also be written as a system of equations
v1 = P1
..
. (7)
v = P ,
k k
89
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
where the P ’s are usually expressed as formal sums of their elements (as we did in
Example 2.7.3).
The finiteness of the components Pi was not used in the proof of Lemma 2.7.4. How-
ever, it will be essential for obtaining the main result of this section. In fact, it will
be convenient, although not necessary, to work with an even more restricted class of
fixed-point equations, which we shall soon introduce. Example 2.7.3 provides us with a
guideline here, too.
Let us extend the height function of FΣ (X) to FΣ (X ∪ Vk ) so that
hg(vi ) = −1 (i = 1, . . . , k) .
(iii) the trees of the form σ(vi1 , . . . , vim ), where m > 0, σ ∈ Σm and vi1 , . . . , vim ∈ Vk .
The fixed-point equation in Example 2.7.3 is regular. It is easy to see that the same
procedure applied to any Rabin-Scott recognizer will yield a regular fixed-point equation.
Hence, every regular language is equational when viewed as a unary forest. It is also
well-known, and easy to prove, that the components of the least solution of a system of
Arden equations are regular.
and
T2 = y, σ(x, x), σ(γ, γ), σ(y, y), . . . . ✷
90
2.7 Algebraic characterizations of recognizability
Let [Π̂] = (T1 , . . . , Tk ) be the least fixed-point for a given (Σ, X, k)-polynomial Π. We
define a binary relation ̺(Π) in FΣ (X):
Ti = Pi (v1 ← T1 , . . . , vk ← Tk ) (i = 1, . . . , k) (8)
2o Consider a tree t = σ(t1 , . . . , tm ) (m > 0) and assume that all trees of lesser height
belong to exactly one Ti . Then there exists for each j = 1, . . . , m exactly one ij
(1 ≤ ij ≤ k) such that tj ∈ Tij . Also, there is exactly one i (1 ≤ i ≤ k) such that
p = σ(vi1 , . . . , vim ) ∈ Pi . Clearly,
t ∈ p(v1 ← T1 , . . . , vk ← Tk ) ⊆ Ti .
The uniqueness of the indices ij implies that p is the only tree of height 0 in FΣ (X ∪
Vk ) from which t can be obtained by the substitutions v1 ← T1 , . . . , vk ← Tk . Hence
t belongs to Ti only.
Now we know that ̺(Π) ∈ E FΣ (X) . It is obvious that it has at most k equivalence
classes. (There may be less than k classes as some T ’s could be empty.) To prove that it is
a congruence relation we consider any m ≥ 1, σ ∈ Σm and s1 , . . . , sm , t1 , . . . , tm ∈ FΣ (X)
such that
s1 ≡ t1 , . . . , sm ≡ tm ̺(Π) .
There are indices i1 , . . . , im such that
sj , tj ∈ Tij for j = 1, . . . , m .
σ(s1 , . . . , sm ), σ(t1 , . . . , tm ) ∈ Ti
91
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
by (8). Hence
σ FΣ (X) (s1 , . . . , sm ) ≡ σ FΣ (X) (t1 , . . . , tm ) ̺(Π)
as required.
Now, suppose ̺ ∈ C FΣ (X) and let S1 , . . . , Sk be the equivalence classes of ̺. We
define a (Σ, X, k)-polynomial Π = (P1 , . . . , Pk ) so that
Pi = {p ∈ FΣ (X ∪ Vk ) | hg(p) = 0, p(v1 ← S1 , . . . , vk ← Sk ) ⊆ Si }
for all i = 1, . . . , k. The fact that ̺ is a congruence means that for each p of height 0
there is exactly one i (1 ≤ i ≤ k) such that
p(v1 ← S1 , . . . , vk ← Sk ) ⊆ Si .
Hence Π is regular. We claim that ̺(Π) = ̺. Let [Π̂] = (T1 , . . . , Tk ). In order to
prove the second statement of the lemma we show by induction on hg(t) that for all
i = 1, . . . , k,
∀t ∈ FΣ (X) t ∈ Si ⇐⇒ t ∈ Ti .
1o If hg(t) = 0, then there is exactly one i such that t ∈ Pi . This means t ∈ Si .
From (8) it follows that t ∈ Ti for the same i.
2o Let t = σ(t1 , . . . , tm ) (m > 0) and suppose the claim holds for all trees of height <
hg(t). Then there are unique indices i1 , . . . , im such that
tj ∈ Sij ∩ Tij (j = 1, . . . , m) .
Also, there is a unique i such that
p = σ(vi1 , . . . , vim ) ∈ Pi .
Then
t ∈ σ(Si1 , . . . , Sim ) = p(v1 ← S1 , . . . , vk ← Sk ) ⊆ Si
by the definition of Pi . On the other hand, (8) implies t ∈ Ti . ✷
From the first part of this section it is clear that a ΣX-forest T can be recognized by a
k-state tree recognizer iff T is saturated by a congruence of FΣ (X) of index ≤ k. From
Lemma 2.7.8 we get a similar connection between the number of states and the number
of variables in a regular fixed-point equation which defines the forest.
There is also a very close connection between regular tree grammars and the fixed-point
equations considered here. For example, the equations of Example 2.7.7 can be converted
into the following set of productions in which v1 and v2 are nonterminal symbols:
v1 → x, v1 → γ, v1 → σ(v1 , v2 ), v1 → σ(v2 , v1 ),
v2 → y, v2 → σ(v1 , v1 ), v2 → σ(v2 , v2 ) .
92
2.8 A Medvedev-type characterization
The resulting regular tree grammar generates T1 if v1 is the initial symbol, and it gen-
erates T2 if v2 is the initial symbol.
On the other hand, every regular ΣX-grammar with k nonterminal symbols can be
converted into a fixed-point system with k equations. This system is not necessarily
regular, but the components of the least solution are nevertheless the regular forests
generated by the grammar from the different nonterminal symbols. For example, if
Σ and X are as in Example 2.7.7 and the productions are
a = x + γ + σ(a, b) and
b = y + σ(b, b) ,
where a and b now are the unknowns. The least solution is T (Ga ), T (Gb ) , where
Ga and Gb are the grammars which we obtain by choosing a and b, respectively, as the
initial symbol.
Definition 2.8.1 For every pair (Σ, X) we define the “next-to-root function”
[
nroot : FΣ (X) − (Σ0 ∪ X) → (Σ ∪ X)m | m ∈ r(Σ)
so that
nroot σ(t1 , . . . , tm ) = root(t1 ), . . . , root(tm )
for all m > 0, σ ∈ Σm and t1 , . . . , tm ∈ FΣ (X).
93
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
Note that the definitions of the U (d)- and V (d1 , . . . , dm )-forests presume a Σ and an X
although the notations do not show this. Clearly, U (d) is the set of all ΣX-trees with
the root labelled by d, and V (d1 , . . . , dm ) consists of all ΣX-trees of height ≥ 1 in which
the nodes immediately above the root are labelled, from left to right, by d1 , . . . , dm ,
respectively. Note also that U (d) = {d} when d ∈ Σ0 ∪ X. We need three more
definitions.
rest(T ) = {t ∈ T | sub(t) ⊆ T } .
Proof. To prove that the representable forests are recognizable it suffices to note that
the elementary forests are recognizable and that the elementary operations preserve
recognizability. Consider any Σ and X. If d ∈ Σ0 ∪ X, then U (d) = {d} ∈ Rec(Σ, X). If
d ∈ Σm (m > 0), then
U (d) = d(y1 , . . . , ym ) y1 ← FΣ (X), . . . , ym ← FΣ (X)
94
2.8 A Medvedev-type characterization
R = {x ∈ X | xα ∈ A′ } ∪
[
U ((σ, c1 , . . . , cm )) | (σ, c1 , . . . , cm ) ∈ Ω, σ A (c1 , . . . , cm ) ∈ A′ .
h : FΩ (X) → FΣ (X)
so that
hm (σ, b1 , . . . , bm ) = σ , m ≥ 0, (σ, b1 , . . . , bm ) ∈ Ωm
and hX = 1X . Clearly, h is alphabetic. We claim that
T = h(P )
95
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
P = R ∩ rest(S ∪ Ω0 ∪ X) .
p = (σ, b1 , . . . , bm )(u1 , . . . , um )
2o Now let
p = (σ, b1 , . . . , bm )(p1 , . . . , pm )
and assume that (1) holds for the trees p1 , . . . , pm . As p is in S and
h(p)α̂ = σ A h(p1 )α̂, . . . , h(pm )α̂ ,
p = (σ, b1 , . . . , bm )(p1 , . . . , pm ) ∈ P .
h(p)α̂ = σ A (b1 , . . . , bm ) ∈ A′ .
96
2.9 Local forests
p = (σ, b1 , . . . , bm )(p1 , . . . , pm ) ,
3o Let t = σ(t1 , . . . , tm ) (m > 0). If we use (1) and its notation, we get
97
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
τ σ γ x τ y
, , and
σ τ σ τ
Figure 2.7.
Hence the membership of a ΣX-tree t in the local forest Loc(R, F ) can be decided by
testing for the local properties root(t) ∈ R and fork(t) ⊆ F .
A ΣX-recognizer for Loc(R, F ) can be constructed as follows. First we define a Σ-
algebra A = (A, Σ). Let A = Σ ∪ X ∪ 0 (0 ∈ / Σ ∪ X). For every σ ∈ Σ0 , put σ A = σ.
For m > 0, σ ∈ Σm and a1 , . . . , am ∈ A let
(
σ if σ(a1 , . . . , am ) ∈ F ,
σ A (a1 , . . . , am ) =
0 otherwise.
The converse of Theorem 2.9.4 does not hold. For example, the forest consisting of
the single tree of Example 2.9.2 is not local as there are many other trees with the same
root and the same forks. However, the following fact can be proved.
Theorem 2.9.5 For every recognizable ΣX-forest T there exist a ranked alphabet Ω, a
frontier alphabet Y , a local ΩY -forest S and an alphabetic tree homomorphism
h : FΩ (Y ) → FΣ (X)
98
2.10 Some basic decision problems
Y = {[a → x] | a → x ∈ P, x ∈ X} .
R = {[a0 → p] | a0 → p ∈ P }
and
F = [a → σ(a1 , . . . , am )]([a1 → p1 ], . . . , [am → pm ]) | m > 0,
a → σ(a1 , . . . , am ), a1 → p1 , . . . , am → pm ∈ P .
h : FΩ (Y ) → FΣ (X)
by the mappings
hY : Y → FΣ (X), [a → x] 7→ x,
and
hm : Ωm → FΣ (X ∪ Ξm ), [a → σ(a1 , . . . , am )] 7→ σ(ξ1 , . . . , ξm ) .
Now h(S) = T , and thereby the theorem, follows from (1) and (2):
(1) If a ⇒∗G t, for some a ∈ N and t ∈ FΣ (X), then there is a tree s ∈ FΩ (Y ) such that
h(s) = t, fork(s) ⊆ F and root(s) is of the form [a → p].
Part (1) can be proved by induction on the length of the derivation of t and (2) by
tree induction on s. ✷
Note that h(S) is always recognizable when S is a local forest and h an alphabetic tree
homomorphism (Theorem 2.9.4 and Corollary 2.4.20).
99
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
the important equivalence problem: Do two given tree recognizers recognize the same
forest? In fact, the more general inclusion problem: “T (A) ⊆ T (B)?” is shown to
be decidable. The problems are quite easy and the proofs follow the strategy familiar
from finite automata theory with a “pumping lemma” as the key result. We have seen in
Section 2.2 that any nondeterministic frontier-to-root, or root-to-frontier, tree recognizer
can be converted into an equivalent deterministic F-recognizer. Hence we may again
restrict ourselves to our basic type of tree recognizers.
We need the following special notation. Let Σ and X be given. Introduce a new letter ξ
and let Tξ be the set of all Σ(X ∪ ξ)-trees in which ξ appears exactly once. For any
q ∈ Tξ and p ∈ FΣ (X) ∪ Tξ we denote q(ξ ← p) by p · q. Also, we define the powers q k
as follows:
1o q 0 = ξ,
2o q n+1 = q · q n (n ≥ 0).
Using these notations we may formulate the pumping lemma of tree recognizers as
follows.
(a) t = p · q · r,
Proof. Suppose t ∈ T (A) and hg(t) ≥ k(= |A|). Then we can write t = σ(t1 , . . . , tm )
(m > 0, σ ∈ Σm ). Choose some j (1 ≤ j ≤ m) such that hg(tj ) = hg(t) − 1. Then
t = tj · s 1 ,
where
s1 = σ(t1 , . . . , tj−1 , ξ, tj+1 , . . . , tm ) ∈ Tξ .
If hg(tj ) > 0, we may decompose tj the same way. Since hg(t) ≥ k the process can be
repeated k times and finally we obtain a representation
t = t′ · s k · . . . · s 2 · s 1 ,
uk+1 = t′ , uk = t′ · sk , . . . , u1 = t ′ · s k · . . . · s 1 = t .
uh α̂ = uj α̂ .
100
2.10 Some basic decision problems
α : FΣ (X ∪ A) → A
Suppose two ΣX-recognizers A and B are given. Clearly, T (A) ⊆ T (B) iff T (A) −
T (B) = ∅. But T (A) − T (B) is recognized by
C = A × B, γ, A′ × (B − B ′ ) ,
where xγ = (xα, xβ) for x ∈ X. Thus the question “T (A) ⊆ T (B)?” can be answered
by deciding whether T (C) is empty or not. The equivalence problem can similarly be
reduced to the emptiness problem. Of course, its decidability follows also from the
decidability of the inclusion problem. We have justified
101
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
Theorem 2.10.3 The inclusion problem and the equivalence problem of tree recognizers
are decidable. ✷
Finally we consider the finiteness problem.
Theorem 2.10.4 It is decidable whether the forest recognized by a given tree recognizer
is finite or infinite.
Proof. Let A be a k-state ΣX-recognizer and write
T = T (A) − {t ∈ FΣ (X) | hg(t) < k} .
We claim that T (A) is finite iff T = ∅. Obviously the condition is sufficient since the
set of ΣX-trees of height < k is finite. If T 6= ∅ and t ∈ T , then hg(t) ≥ k and we may
apply the pumping lemma and write t = p · q · r so that
p · q i · r ∈ T (A) for all i ≥ 0 .
These trees are pairwise distinct since hg(q) ≥ 1. Hence T (A) is infinite. The forest T
is recognizable and one can easily construct a recognizer for it. This means that the
condition T = ∅ is effectively testable. ✷
The decidability of the finiteness problem may also be deduced from the following
corollary of the pumping lemma. The proof is an exercise.
Lemma 2.10.5 Let A be a k-state tree recognizer. Then T (A) is infinite iff it contains
a tree t such that
k ≤ hg(t) < 2k . ✷
102
2.11 Deterministic R-recognizers
Definition 2.11.1 Let X be any frontier alphabet. For each x ∈ X the set gx (t) of
x-paths of a ΣX-tree t is defined as follows:
2◦ If t = σ(t1 , . . . , tm ) (σ ∈ Σm , m > 0), then gx (t) = σ1 (gx (t1 )) ∪ · · · ∪ σm (gx (tm )).
We extend gx to a mapping from pFΣ (X) to pFΓ (X) in the natural way. Moreover, we
put [
g(T ) = (gx (T ) | x ∈ X)
for each T ⊆ FΣ (X).
Label the edges of the graph representing a tree t ∈ FΣ (X) so that the ith edge (counted
from the left) leaving a node labelled by a symbol σ always gets the label σi . Then the
elements of gx (t) (x ∈ X) are spelled out by the paths leading from the root to a leaf
labelled by x when we interpret a word σ1i1 . . . σkik x (k ≥ 0, σ1i1 , . . . , σkik ∈ Γ) as the
ΓX-tree σ1i1 (. . . σkik (x) . . . ). Moreover, every such path gives an element of gx (t).
We claim that T (G′ ) = g(T ). This follows when we show that, for every tree
and every a ∈ N ,
p ∈ T (G′a ) iff p ∈ g(T (Ga )), (*)
where G′a = (N, Γ, X, P ′ , a).
We proceed by induction on hg(p).
2◦ Suppose hg(p) > 0 and that (*) holds for all trees of lesser height.
103
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
If p ∈ T (G′a ), then a ⇒∗G′ σ1i1 (ai1 ) and ai1 ⇒∗G′ σ2i2 (. . . σkik (x) . . . ) for some ai1 ∈ N ,
and P contains a production a → σ1 (a1 , . . . , am ) such that i1 ≤ m. By the inductive
assumption there exists a tree ti1 ∈ T (Gai1 ) such that σ2i2 (. . . σkik (x) . . . ) ∈ gx (ti1 ).
Moreover, we may choose for every i 6= i1 , 1 ≤ i ≤ m, a tree ti ∈ T (Gai ). Then
t = σ1 (t1 , . . . , tm ) ∈ T (Ga ) and p ∈ gx (t) ⊆ g(T (Ga )).
Conversely, let p ∈ g(T (Ga )). Then p ∈ gx (t) for some t ∈ T (Ga ). Obviously, t is of
the form σ1 (t1 , . . . , tm ), where i1 ≤ m, and it has a derivation
a ⇒G σ1 (a1 , . . . , am ) ⇒∗G t.
This means that P ′ contains the production a → σ1i1 (ai1 ). Moreover, ti1 ∈ T (Gai1 ) and
σ2i2 (. . . σkik (x) . . . ) ∈ gx (ti1 ). Hence, we get a derivation
Let g be the mapping of Definition 2.11.1 associated with a given frontier alphabet X.
Then we write τX = gg−1 . It is clear that τX is a closure operation in FΣ (X), i.e., for
all S, T ⊆ FΣ (X),
(i) S ⊆ SτX ,
104
2.11 Deterministic R-recognizers
Proof. In order to prove the inclusion T (pA) ⊆ T (A)τX , we consider an arbitrary tree
s ∈ T (pA) and an x-path p ∈ gx (s) (x ∈ X). We should show that p ∈ g(T (A)). Let
p = σ1i1 (. . . (σkik (x)) . . . ). By the definition of pA there are states a0 , a1 , . . . , ak ∈ A
such that
Since A is normalized, this implies that there is a tree t ∈ T (A) such that p ∈ gx (t).
Hence p ∈ g(T (A)). Now, let s ∈ T (A)τX and consider any x-path
Then p ∈ gx (t) for some t ∈ T (A) and there are states a0 , a1 , . . . , ak ∈ A such that the
above conditions (i) and (ii) hold. But the definition of pA implies that the state of pA
at the leaf corresponding to p includes ak for any tree in which p is an x-path. Hence
pA arrives at the leaf of s corresponding to p in a state belonging to xα. This holds for
every leaf of s and therefore s ∈ T (pA). ✷
Lemmas 2.11.3 and 2.11.4 also imply that every closed recognizable forest is recognized
by a DR recognizer. But it is easy to see that T (pA) = T (A) if A is deterministic. Hence
we may state the following result.
105
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
The rest of this section deals with the minimization of DR-recognizers. First two
general remarks. When A = (A, a0 , α) is a DR ΣX-recognizer, then the NDR algebra
A = (A, Σ) is deterministic and we may view each σ A (σ ∈ Σm , m > 0) as a mapping
σ A : A → Am .
Hence we write σ A (a) = (a1 , . . . , am ) rather than σ A (a) = {(a1 , . . . , am )}. The second
remark concerns normalized DR recognizers. If the DR ΣX-recognizer A is normalized,
one of the following conditions holds for each pair (a, σ) ∈ A × Σ:
(1) Every component of σ A (a) is a 0-state.
(ii) If A has a 0-state, choose one of them, say d, and define then for all m > 0,
σ ∈ Σm , and a ∈ A,
∗ (d, . . . , d) (∈ Am ) if σ A (a) contains a 0-state,
σ A (a) =
σ A (a) otherwise.
It is easy to prove that A∗ is normalized and deterministic, and that T (A∗ ) = T (A).
Normalized DR recognizers have also the following useful property.
Proof. If one of the states ai (1 ≤ i ≤ m) is a 0-state, then all of them are. Moreover,
T (A, a) = T (B, b) does not contain any tree of the form σ(t1 , . . . , tm ). Hence, one of
the forests T (B, bi ) (1 ≤ i ≤ m), and therefore every one of them, is empty. Thus
T (A, ai ) = T (B, bi ) = ∅ for all i = 1, . . . , m.
Suppose now that T (A, ai ) 6= ∅ and T (B, bi ) 6= ∅ for all i = 1, . . . , m. Consider any i
(1 ≤ i ≤ m) and ti ∈ T (A, ai ). Choose any t1 ∈ T (A, a1 ), . . . , ti−1 ∈ T (A, ai−1 ), ti+1 ∈
T (A, ai+1 ), . . . , tm ∈ T (A, am ). Then σ(t1 , . . . , tm ) ∈ T (A, a) = T (B, b) implies ti ∈
T (B, bi ). By a symmetrical argument, T (B, bi ) ⊆ T (A, ai ) holds for every i = 1, . . . , m.
Hence, T (A, ai ) = T (B, bi ) for every i = 1, . . . , m, as required. ✷
We shall now define a few algebraic concepts for DR recognizers. Let A = (A, a0 , α)
and B = (B, b0 , β) be DR ΣX-recognizers.
A homomorphism from A to B is a mapping ϕ : A → B such that
(i) for all m > 0, σ ∈ Σm and a ∈ A, σ B (aϕ) = (a1 ϕ, . . . , am ϕ), where (a1 , . . . , am ) =
σ A (a),
106
2.11 Deterministic R-recognizers
(ii) a0 ϕ = b0 , and
(i) for all m > 0, σ ∈ Σm and a, a′ ∈ A, a̺ = a′ ̺ implies σ A (a)/̺ = σ A (a′ )/̺ (recall
the notation from Section 1.1), and
and α̺ : X → A/̺ is defined by xα̺ = xα/̺ (x ∈ X). It is easy to see that A/̺ is
well-defined.
The following theorem is easily obtained by modifying the proofs of the corresponding
facts from algebra.
107
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
2◦ Let t = σ(t1 , . . . , tm ) and assume that (*) holds for t1 , . . . , tm . Suppose a ∈ tα̃.
If σ A (a) = (a1 , . . . , am ), this means that a1 ∈ t1 α̃, . . . , am ∈ tm α̃. Hence, a1 ϕ ∈
t1 β̃, . . . , am ϕ ∈ tm β̃. This implies
σ B (aϕ) = (a1 ϕ, . . . , am ϕ) ∈ t1 β̃ × · · · × tm β̃.
Hence, aϕ ∈ tβ̃. Suppose now that aϕ ∈ tβ̃, and let σ A (a) = (a1 , . . . , am ). Then
a1 ϕ ∈ t1 β̃, . . . , am ϕ ∈ tm β̃, which implies a1 ∈ t1 α̃, . . . , am ∈ tm α̃. Hence, a ∈ tα̃.
The equality tα̃ = tβ̃ϕ−1 implies tα̃ϕ = tβ̃ as ϕ is surjective.
Now, (*) implies that for every t ∈ FΣ (X),
t ∈ T (A) iff a0 ∈ tα̃
iff a0 ϕ(= b0 ) ∈ tα̃ϕ(= tβ̃)
iff t ∈ T (B). ✷
108
2.11 Deterministic R-recognizers
c
(i) Ac = (Ac , Σ), where Ac = {a ∈ A | a0 ⊢∗ a} and σ A (a) = σ A (a) for all σ ∈ Σ and
a ∈ Ac .
We are now ready to present the main theorem of the minimization theory of DR
recognizers.
ϕ : A/∼A → B/∼B
(i) (a∼A )ϕ is defined for all a∼A ∈ A/∼A . Since A is connected, there exist for every
a ∈ A a k ≥ 0 and states a1 , . . . , ak ∈ A such that
a0 ⊢ a1 ⊢ a2 ⊢ · · · ⊢ ak = a.
109
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
(iv) ϕ is surjective. If we exchange the roles of A and B in (i), we see that there exists
for every b ∈ B an a ∈ A such that T (A, a) = T (B, b).
(v) ϕ is a homomorphism. That ϕ preserves the operations follows from Lemma 2.11.7.
If a∼A ∈ xα/∼A (x ∈ X) and (a∼A )ϕ = b∼B , then x ∈ T (A, a) = T (B, b) implies
b∼B ∈ xβ/∼B . Likewise, (a∼A )ϕ = b∼B ∈ xβ/∼B implies a∼A ∈ xα/∼A . Thus
xβ∼B ϕ−1 = xα∼A for every x ∈ X. ✷
Step 1. Form A∗ .
Step 2. Form A∗ c .
2.12 EXERCISES
1. Let leaf(t) denote the set of symbols which label the leaves of a given ΣX-tree t.
Define leaf(t) by tree induction.
2. (a) Define the length |t| of a ΣX-tree t (as a word) by tree induction.
(b) For the sake of simplicity, let Σ = Σ2 . Derive an upper bound for |t| in terms
of hg(t). Give also a lower bound for |t| in terms of hg(t).
4. Let Σ and X be as in the previous exercise. Decide which ones of the ΣX-forests,
R, S, and T are recognizable, when these are defined as follows:
(i) t ∈ R iff the number of σ’s in t is odd.
(ii) t ∈ S iff all paths from the root to a leaf are of the same length.
110
2.12 Exercises
6. Use regular tree grammars to prove directly that Rec(Σ, X) is closed under σ-
products (Corollary 2.4.12).
7. Let us change the definition of the forest product T (x ← Tx ) (cf. Definition 2.4.3)
in such a way that every occurrence of each letter x ∈ X should be rewritten as
the same tree tx ∈ Tx . Then we get the new product
T [x ← Tx | x ∈ X] = {t(x ← tx | x ∈ X) | t ∈ T, tx ∈ Tx (x ∈ X)}.
10. Let us change Definition 2.4.7 so that T j+1,x = T ·x T j,x ∪ T j,x for all j ≥ 0.
Does the new x-iteration coincide with the original one? If not, does it preserve
recognizability?
11. Let x 6= y (x, y ∈ X). Is it possible that (T ∗x )∗y 6= (T ∗y )∗x for some ΣX-forest T ?
12. Show that the construction of the tree recognizer for the forest S −x T given in the
proof of Theorem 2.4.10 is effective when S is recognizable (and given by a tree
recognizer).
14. Prove Corollary 2.4.20 directly without using Theorems 2.4.16 and 2.4.18.
111
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
17. Let Σ = Σ2 = {σ} and X = {x}. Write a regular expression for the forest of all
ΣX-trees which contain an even number of σ’s.
18. Let Σ and X be as in Exercise 3. Construct a ΣX-recognizer for the forest repre-
sented by the regular expression σ(x, y) ·z σ(ω, σ(ω, z))∗z .
19. Prove Theorem 2.6.6.
20. If A is a ΣX-recognizer and T (A) = T , then α̂ is a homomorphism from FT to
A. Prove Lemma 2.6.2 using this observation.
21. Prove Lemma 2.6.14.
22. In Section 2.7 we noted that one may define recognizability for subsets of algebras.
We call T (⊆ A) a recognizable subset of the Σ-algebra A = (A, Σ), if there exists
a congruence θ of finite index which saturates T . Denote by Rec A the set of all
recognizable subsets of A. Prove the following facts:
(a) If S, T ∈ Rec A, then S ∪ T, S ∩ T, S − T ∈ Rec A.
(b) If ϕ : A → B is a homomorphism and T ∈ Rec B, then T ϕ−1 ∈ Rec A.
(Note. T ∈ Rec A does not imply T ϕ ∈ Rec B. A counterexample where A and
B are monoids can be found in Eilenberg’s book (Vol. A) mentioned among the
references of Chapter 1.)
23. Let Σ = Σ2 = {σ} and X = {x, y}, and let (U, V ) be the least fixed-point of the
system
u = x + σ(σ(u, v), y)
v = σ(y, u).
Find a regular (Σ, X, k)-polynomial Π (k ≥ 2) such that U and V can be rep-
resented as unions of some components of [Π̂]. (For a general treatment of such
questions see Mezei and Wright [182].)
24. Show that every local ΣX-forest Loc(R, F ) can be represented in terms of the ele-
mentary forests and the elementary operations intersection, union, and restriction.
Note the resulting connection between the Theorems 2.8.6 and 2.9.5.
25. Show that the decidability of the equivalence problem of tree recognizers follows
from the results of Section 2.6.
26. Prove Lemma 2.10.5.
27. Prove that it is decidable whether a recognizable forest can be recognized by a
DR-recognizer.
28. Are all local forests recognizable by DR-recognizers?
29. Present algorithms for carrying out Steps 2 and 3 of the minimization algorithm
for DR-recognizers which was outlined in Section 2.11.
112
2.13 Notes and references
113
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
morphic images of the recognizable subsets of term algebras. Applied to term algebras
this result gives our Theorem 2.7.9. Eilenberg and Wright [69] present these re-
sults in a category theoretic form. For various classes of subsets in general algebras we
refer also to Wagner [249], Lescanne [150], Marchand [175], Shepard [220], and
Steinby [227]. Dubinsky [67] discusses equational and recognizable subsets of nonde-
terministic algebras. Maibaum [170], and Engelfriet and Schmidt [85] extend the
subject into another direction by considering many-sorted algebras.
The material of Section 2.8 is from Costich [52]. Local forests, or similar concepts, and
results related to Theorems 2.9.4 and 2.9.5 can be found in Doner [66], Thatcher [237,
238], and Takahashi [234].
The characterization of the forests recognizable by DR recognizers is from Virágh [248],
although the basic idea is discernible already in Magidor and Moran [166] (cf. also
Thatcher [239]). The minimization theory of DR recognizers appears in Gécseg and
Steinby [104].
We should also mention an alternative approach, originating with Pair and Quere [196]
and popular among French writers, in which the basic objects are tuples of trees rather
than trees. The usual tree operations are then augmented by operations which catenate
tuples of trees or form a tree from an m-tuple by creating a new root labelled by an
m-ary operator. As an abstract framework for their study Pair and Quere introduced
“binoids”, the tuples of trees form such a binoid. Their results include the basic clo-
sure properties and a Kleene Theorem. This formalism has been developed further by
Arnold and Dauchet [21] to a theory of “magmoids” which also embodies many of the
ideas of Eilenberg and Wright [69]. Arnold [9, 10] discusses many topics relevant
to this chapter within the framework of magmoids.
We shall now discuss briefly some topics and applications of the theory not covered
by this book. The survey is by no means complete, and in many cases the choices
were dictated by personal preference. Some more remarks will be made at the end of
Chapters 3 and 4.
The category theoretic treatment of recognizable and equational subsets by Eilenberg
and Wright [69] was already mentioned. It is based on Lawvere’s “theories”. This
approach was developed further by Give’on and Arbib [111], and others. The theory
of magmoids has also evolved from the same ideas. We have avoided the use of category
theory altogether, but the bibliography contains a sample from the extensive and highly
diversified literature on the subject. The items of interest include Alagić [3, 4], Arbib
and Manes [6], Bobrow and Arbib [38], Goguen [113], Goguen et al [114, 115],
Horváth [122, 123], and Trnková and Adámek [244].
The structure theory of tree automata has received little attention although some initial
steps were taken already by Magidor and Moran [166]. Ricci [209] considered cascade
products of tree automata. Iterative realizations and general products of tree automata
are studied in Steinby [225]. Two sections of Gécseg and Steinby [105] are devoted
to the subject. It is evident that generalizations from the unary case will usually not be
easy in this area.
Transition monoids have proved very useful in finite automaton theory and some
equivalents of them for tree automata have been suggested. The “m-ary monoids” of
114
2.13 Notes and references
Give’on [110] and the “substitution algebras” of Yeh [253] are in fact special Menger
algebras. The same idea reappears in the “clone algebras” of Turner [246]. Sommer-
halder [223] develops the concept further and associates with an algebra a sequence
M1 , M2 , . . . of monoids. Here Mn consists of all n-tuples of n-ary polynomial functions of
the algebra. It would be easy to define syntactic monoids of forests along these lines, but
no such theory seems to have evolved yet. Another variant of the transition semigroup
concept has been studied by Helton [120].
We shall mention some other algebraic topics of potential interest. A ΣX-forest T is
said to be recognizable by a Σ-algebra A = (A, Σ) if one may choose α : X → A and A′ (⊆
A) in such a way that (A, Σ, A′ ) recognizes T . Families of forests recognizable by algebras
belonging to a given variety (equational class) were considered by Steinby [224] and by
Gécseg and Horváth [103]. For a further study in this direction it would probably
be advantageous to follow the example of Eilenberg’s theory of M -varieties and varieties
of recognizable languages and consider “ω-varieties” (usually called pseudovarieties) of
algebras and the families of forests corresponding to them; an ω-variety is a class of
finite algebras closed under the construction of subalgebras, homomorphic images and
finite direct products. In Steinby [226] it was shown that Eilenberg’s basic variety
theorem can be extended to ω-varieties and varieties of recognizable subsets of free
algebras (suitably defined). A specialization of this result to term algebras gives a
correspondence between ω-varieties and varieties of recognizable forests. A ΣX-forest T
is said to be rationally represented by an ΩX-recognizer A if there exists an embedding
ϕ : FΣ (X) → FΩ (X) of a certain kind such that T ϕ = T (A). A variety K of algebras is
said to be rationally complete if every recognizable forest can be rationally represented by
a recognizer based on a finite algebra belonging to K. Gécseg [101] studies the rational
completeness of varieties and the equivalence of tree recognizers with respect to rational
representation. Further results can be found in Maróti [176], and Marchand [173]
also contains some related ideas.
We shall now list a few references to some more topics. Probabilistic tree automata and
related topics have been discussed by Magidor and Moran [166, 167], Ellis [72] and
Karpiński [141, 142]. Forests of infinite trees appear in Rabin [204], Engelfriet [73],
Casteran [50] and Courcelle [54]. An alternative way to generate forests is provided
by the tree adjunct grammars studied by Joshi, Levy and Takahashi [135, 136],
Levy [155], and Levy and Joshi [157]. Also Lindenmayer systems (L-systems) for trees
have been considered; see Čulik [56], Čulik and Maibaum [57], Engelfriet [76, 79],
Karpiński [143], Steyart [230], and Szilard [231].
Although we present our subject as a part of pure automata and formal language
theory, it should be clear that it has many connections to the more applied aspects of
language specification, translation and semantics. As a conclusion we would like to point
out some less obvious areas of application.
When Doner [65, 66] and Thatcher and Wright [240, 241] introduced tree au-
tomata their goal was to prove the decidability of the weak second order theory of
multiple successors. Further applications to logic can be found in Rabin [204, 205].
In syntactic pattern recognition patterns are decomposed into simple basic elements
which are represented by letters of an alphabet. A pattern is then represented, for
115
2 TREE RECOGNIZERS AND RECOGNIZABLE FORESTS
example, as a word. However, essential information about the relations between the
basic elements may be lost if the corresponding letters are simply concatenated to form
a word. It is possible that these can be described adequately by representing the pattern
as a tree, and then tree automata theory may be used. For example, the considered class
of patterns may be generated by a tree grammar or recognized by a tree recognizer. One
specific problem prompted by syntactic pattern recognition is the inference of forests
from samples. The interested reader may consult the books by Fu [97] and Gonzalez
and Thomason [117]. Some papers from this area are Berger and Pair [33], Brayer
and Fu [42], Fu and Bhargava [98], Gonzalez, Edwards and Thomason [116], Lu
and Fu [165], Pair [194], Tai [232], and Williams [251].
116
3 CONTEXT-FREE LANGUAGES AND
TREE RECOGNIZERS
The words generated by a context-free grammar can be read from derivation trees. The
connection between forests and languages implied by this fact is the subject matter
of this chapter. In the first section we define the yield-function by means of which a
word is extracted from a tree. In Section 3.2 the basic relations between recognizable
forests and context-free grammars are established. The usual definition of derivation
trees must be modified slightly as to make them “trees” in our sense of the term, but
the difference is inessential. The forest of derivation trees of any CF grammar is shown
to be recognizable. On the other hand, we shall see that the yield of any recognizable
forest is a CF language. Hence tree recognizers may also be viewed as recognizers of CF
languages. The section is concluded by showing that every CF language is the yield of
a local forest recognizable by a deterministic R-recognizer.
The inverse image of a CF language under the yield-function is not always a recog-
nizable forest, but we show in the beginning of Section 3.3 that the inverse image of a
regular language is a recognizable forest. Also, a slightly restricted converse of this fact
is presented. Then we show that every CF language can be obtained from a recognizable
forest with a fixed and very simple ranked alphabet. Section 3.3 is concluded by some
examples which show how facts about context-free languages can be proved using the
theory of recognizable forests.
In Section 3.4 another, less well-known, way to obtain the context-free languages from
recognizable forests is presented.
To obtain the yield of a tree σ(t1 , . . . , tm ) one concatenates the yields of the subtrees
t1 , . . . , tm . In particular, yd(σ) = e for all σ ∈ Σ0 . More generally, yd(t) = e iff
117
3 CONTEXT-FREE LANGUAGES AND TREE RECOGNIZERS
Whether or not a given word w ∈ X ∗ is the yield of some ΣX-tree depends on the
length of w and the arities of the operators in Σ.
Lemma 3.1.3 Let r(Σ) = {m1 , . . . , mk }. For a word w ∈ X ∗ there exists a tree t ∈
FΣ (X) such that yd(t) = w iff the length of w can be expressed in the form
The proof of the lemma is an exercise. It is easy to see that yd(FΣ (X)) = X ∗ iff
Σ0 6= ∅ and Σ − (Σ1 ∪ Σ0 ) 6= ∅. When this is the case, there exists for every X-language
L a ΣX-forest T such that yd(T ) = L. The greatest among these is the forest
In general, we know just that yd(yd−1 (L)) ⊆ L. From Lemma 3.1.3 one easily gets
Corollary 3.1.4 For a given L ⊆ X ∗ , there exists a forest T ⊆ FΣ (X) such that
yd(T ) = L iff
118
3.2 Context-free languages and recognizable forests
ΣG
m = {(a, m) | (∃a → η ∈ P )|η| = m}.
Definition 3.2.1 Let G and ΣG be as above. For every d ∈ N ∪ X the set D(G, d) of
derivation trees with d as the root is defined by the following conditions:
1◦ D(G, x) = {x} for each x ∈ X.
4◦ Nothing is in any D(G, d) unless this follows from a finite number of applications
of the rules 1◦ , 2◦ and 3◦ .
The derivation forest of G is the ΣG X-forest D(G) = D(G, a0 ).
Theorem 3.2.2 The derivation forests of CF grammars are local and, therefore, recog-
nizable.
R = {(a0 , m) | m ≥ 0, (a0 , m) ∈ ΣG
m}
and the set F of the allowed forks is defined as follows. If m > 0 and a → d1 . . . dm ∈ P ,
then we include in F every fork (a, m)(c1 , . . . , cm ) such that for all i = 1, . . . , m,
di if di ∈ X,
ci =
(di , k) with k ≥ 0 and (di , k) ∈ ΣG k , if di ∈ N .
119
3 CONTEXT-FREE LANGUAGES AND TREE RECOGNIZERS
In this case ΣG = ΣG G G G G
0 ∪ Σ1 ∪ Σ3 , where Σ0 = {(a0 , 0)}, Σ1 = {(b, 1)} and Σ3 =
G
G
{(a0 , 3), (b, 3)}. The productions of the grammar GD = (N, Σ , X, PD , a0 ) generating
D(G) are a0 → (a0 , 3)(x, a0 , b), a0 → (a0 , 0), b → (b, 3)(x, y, b) and b → (b, 1)(y). The
allowed roots of the local forest D(G) are (a0 , 0) and (a0 , 3), and the possible forks are
(a0 , 3)(x, (a0 , 0), (b, 1)), (a0 , 3)(x, (a0 , 0), (b, 3)), (a0 , 3)(x, (a0 , 3), (b, 1)), (a0 , 3)(x, (a0 , 3),
(b, 3)), (b, 3)(x, y, (b, 1)), (b, 3)(x, y, (b, 3)) and (b, 1)(y). ✷
P1 = {a → yd′ (p) | a → p ∈ P }.
(2) for all w ∈ X ∗ and a ∈ N , a ⇒∗G1 w only in case there exists a tree t ∈ FΣ (X)
such that a ⇒∗G t and yd(t) = w.
These two facts imply that yd(T ) = L(G1 ) is CF. ✷
In view of Theorem 3.2.5 any tree recognizer may be seen as a device which recognizes
a CF language by checking the possible syntaxes of given words; a word is accepted iff
it is the yield of at least one tree accepted by the tree recognizer.
120
3.2 Context-free languages and recognizable forests
The equivalence expressed in Theorem 3.2.7 is effective both ways; for any CF language
given by a CF grammar we can construct a tree recognizer, and for any tree recognizer
A we can construct a CF grammar generating L(A).
By Theorem 3.2.2 every CF language is the yield of a local forest. We shall now show
that even a smaller class of forests will suffice. To this end we replace derivation trees
by trees in which the inner nodes are labelled by complete productions.
With every CF grammar G = (N, X, P, a0 ) we associate another ranked alphabet ΣP
defined as follows. For each m ≥ 0, let
i.e., the m-ary symbols correspond to the productions with right-hand sides of length
m.
Definition 3.2.8 Let G and ΣP be as above. For every d ∈ N ∪ X the set P (G, d) of
production trees with d at the root is defined by the following conditions:
1◦ P (G, x) = {x} for each x ∈ X.
2◦ For a ∈ N , (a → e) ∈ P (G, a) iff a → e ∈ P .
3◦ Suppose a → d1 . . . dm ∈ P (m > 0, a ∈ N and d1 , . . . , dm ∈ N ∪ X). If p1 ∈
P (G, d1 ), . . . , pm ∈ P (G, dm ), then (a → d1 . . . dm )(p1 , . . . , pm ) ∈ P (G, a).
4◦ Nothing is in any P (G, d) unless this follows from a finite number of applications
of 1◦ , 2◦ and 3◦ .
The production forest of G is the ΣP X-forest P (G) = P (G, a0 ).
Theorem 3.2.9 The production forest P (G) of any CF grammar G is local and it is
also recognizable by a deterministic R-recognizer.
121
3 CONTEXT-FREE LANGUAGES AND TREE RECOGNIZERS
Example 3.3.1 Let Σ = Σ2 = {σ} and X = {x, y}. Consider the (minimal linear) CF
language L = {xn y n | n ≥ 1}. If yd−1 (L) were recognized by a ΣX-recognizer A, then
A would accept all trees σ(si , ti ) (i ≥ 1), where (i) s1 = x, t1 = y and (ii) si+1 = σ(sk , x)
and tk+1 = σ(y, tk ) for all k ≥ 1. As A is finite, it would then also accept some tree
σ(si , tj ) with i 6= j. But this is a contradiction, because yd(σ(si , tj )) = xi y j 6∈ L. ✷
Theorem 3.3.2 If L is a regular X-language, then yd−1 (L) ∈ Rec(Σ, X) for any ranked
alphabet Σ.
σ A (a1 , . . . , am ) = a1 · a2 · . . . · am (product in M )
The full converse of Theorem 3.3.2 is not valid, but the following result will be proven
in Exercises 6 and 7.
122
3.3 Further results and applications
The ranked alphabets ΣG and ΣP depend on the given CF grammar. We shall now
show that every CF language is the yield of a recognizable forest over a fixed ranked
alphabet. In fact, a very simple alphabet will suffice.
Theorem 3.3.4 Let Σ be a ranked alphabet which contains a binary operator and a
nullary operator. Then every CF language is recognized by a Σ-recognizer. For e-free
CF languages the binary symbol alone is sufficient.
Proof. Let us consider the e-free case first. Every CF language L ⊆ X + is generated
by a CF grammar G = (N, X, P, a0 ) in Chomsky normal form, where each production
is of the form a → bc or a → x (a, b, c ∈ N , x ∈ X). By Lemma 2.4.1 we may assume
that Σ = Σ2 = {σ}. Let G1 = (N, Σ, X, P1 , a0 ) be the regular ΣX-grammar, where
P1 = {a → σ(b, c) | a → bc ∈ P } ∪ {a → x | a → x ∈ P }.
yd′ : FΣ (X ∪ N ) → (X ∪ N )∗
a ⇒G u1 ⇒G . . . ⇒G uk (a ∈ N, k ≥ 1)
there is a derivation
such that yd′ (pi ) = ui for i = 1, . . . , k. This implies L(G) ⊆ yd(T (G1 )) as yd′ |FΣ (X) =
yd. The converse inclusion follows from the fact that for every derivation (*) we have a
derivation
a ⇒G yd′ (p1 ) ⇒G . . . ⇒G yd′ (pk ).
If L ⊆ X ∗ and e ∈ L, then we find, as above, a recognizable ΣX-forest T such that
yd(T ) = L − {e}. Now add a nullary operator ω to Σ and let T ′ = T ∪ ω. Then T ′ is
recognizable and yd(T ′ ) = L. ✷
The connections established above suggest the possibility of developing, or just inter-
preting, the theory of context-free languages in terms of tree automata and recognizable
forests. We shall illustrate this by a few examples. The results themselves are well
known.
123
3 CONTEXT-FREE LANGUAGES AND TREE RECOGNIZERS
The next example shows how the regular forest operations relate to language opera-
tions.
w0 u1 w1 u2 . . . wk−1 uk wk ,
then
yd(p) = w0 yd(s1 )w1 yd(s2 ) . . . yd(sk )wk ∈ yd(S) ·x yd(T ).
Conversely, if w ∈ yd(S) ·x yd(T ), then we may write w in the form
w = w0 u1 w1 u2 . . . wk−1 uk wk
so that k ≥ 0, w0 xw1 x . . . xwk ∈ yd(T ) and u1 , . . . , uk ∈ yd(S). Then there are trees
t ∈ T and s1 , . . . , sk ∈ S such that yd(t) = w0 xw1 x . . . xwk and yd(s1 ) = u1 , . . . ,
yd(sk ) = uk . If we replace the occurrences of x in t by the trees s1 , . . . , sk , then we get
a tree p ∈ S ·x T such that yd(p) = w. An easy induction on i shows now that
Lemma 3.3.7 For any two ΣX-forests S and T , and any letter x ∈ X,
124
3.4 Another way to recognize CF languages
Now we can derive the following well-known description of the family of context-free
languages.
Theorem 3.3.8 The context-free languages form the smallest family of languages which
contains the finite languages and is closed under (finite) union, x-substitutions and x-
substitution closures.
125
3 CONTEXT-FREE LANGUAGES AND TREE RECOGNIZERS
1◦ xη = e for all x ∈ X.
Another way to get tη would be to erase the parentheses and x and then reverse the
resulting word. Both of these constructions can serve as a basis for the generalization
to the case of an arbitrary ranked alphabet. The reversing of the order of the word
is an inessential step due to our way of writing trees, and it will be omitted in the
generalization.
Let Σ be an arbitrary ranked alphabet and X any frontier alphabet. We shall treat Σ
as an ordinary alphabet, too. We assume that Σ and X are disjoint and that they do
not contain (, ) or the comma. Let
Y = Σ ∪ X ∪ {(, ), , }
and define
η : Y ∗ → Σ∗
Applied to a ΣX-tree t η erases all frontier letters x ∈ X, the parentheses and the
commas leaving the symbols σ ∈ Σ intact. It is easy to see that this can be carried out
as follows, too.
1◦ xη = e for all x ∈ X.
We have already noted that every regular ΣX-grammar may also be viewed as a
CF grammar generating a Y -language. Moreover, it is well-known that the family of
context-free languages is closed under homomorphisms. Hence we have
126
3.5 Exercises
In order to show that T (G1 ) is the required recognizable forest we extend η to a homo-
morphism
η1 |(Y ∪ N )∗ → (Σ ∪ N )∗
so that η1 |Y = η and η1 |N = 1N . It is easy to see that to every derivation
a ⇒G u1 ⇒G . . . ⇒G uk (a ∈ N, k ≥ 1)
a ⇒ G 1 v1 ⇒ G 1 . . . ⇒ G 1 vk (*)
3.5 EXERCISES
1. Is is possible that yd−1 (w) is infinite for some word w?
4. Show that for every CF grammar G, D(G) is the image of P (G) under an alphabetic
tree homomorphism.
127
3 CONTEXT-FREE LANGUAGES AND TREE RECOGNIZERS
5. Recall that a groupoid is an algebra with one binary operation (and no other
operations). For Σ = Σ2 = {σ}, FΣ (X) is the free groupoid generated by X.
Verify that yd : FΣ (X) → X + is a groupoid epimorphism. Then prove that a
language L ⊆ X + is context-free iff it is the homomorphic image of a recognizable
subset of the free groupoid generated by X (cf. Exercise 2.22, and Mezei and
Wright [182]).
6. The set Comb(Σ, X) of “comb-like” ΣX-trees is defined as the smallest set S
satisfying the conditions 1◦ and 2◦ :
1◦ X ∪ Σ0 ⊆ S.
2◦ If m > 0, σ ∈ Σm , x1 , . . . , xm−1 ∈ X and t ∈ S, then σ(x1 , . . . , xm−1 , t) ∈ S.
(a) Prove that Comb(Σ, X) ∈ Rec(Σ, X).
(b) Let T be a recognizable forest such that T ⊆ Comb(Σ, X).
Show that T is generated by a regular ΣX-grammar (N, Σ, X, P, a0 ) in
which each production has the form a → σ(x1 , . . . , xm−1 , b), a → ω or
a → x (a, b ∈ N , m > 0, σ ∈ Σm , x1 , . . . , xm−1 ∈ X, ω ∈ Σ0 , x ∈ X).
(c) Infer from (b) that yd(T ) ∈ RecX for every recognizable T ⊆ Comb(Σ, X).
(d) Prove that for every ΣX-tree t there exists a comb-like ΣX-tree s such
that yd(s) = yd(t). Deduce from this fact that if yd(yd−1 (L)) = L for
some L ⊆ X ∗ , then
yd(yd−1 (L) ∩ Comb(Σ, X)) = L.
128
3.6 Notes and references
129
4 TREE TRANSDUCERS AND TREE
TRANSFORMATIONS
In this chapter we shall deal with systems transforming trees into trees similarly as
generalized sequential machines transform strings into strings. There are two main
categories of such systems: frontier-to-root tree transducers which process a tree from
the leaves down towards the root, and root-to-frontier tree transducers which work in
the opposite direction. Special classes of tree transducers will play a basic part in
decomposing tree transformations into simpler ones.
Ξ = {ξ1 , ξ2 , . . .}
131
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
(5) P is a finite set of productions (or rewriting rules) of the following two types:
(i) x → a(q) (x ∈ X, a ∈ A, q ∈ FΩ (Y )),
(ii) σ(a1 (ξ1 ), . . . , am (ξm )) → a(q(ξ1 , . . . , ξm )) (σ ∈ Σm , m ≥ 0, a1 , . . . , am , a ∈ A,
q(ξ1 , . . . , ξm ) ∈ FΩ (Y ∪ Ξm )).
(In the sequel we shall write simply σ(a1 , . . . , am ) for σ(a1 (ξ1 ), . . . , am (ξm )).)
132
4.1 Basic concepts
For Definition 4.1.2 it would be enough to apply τA∗ to trees from FΣ (X). The above
more general case will be needed later.
Sometimes in our proofs we should know how an input tree is transformed step by step
into an output tree. Again, let A be the F-transducer of Definition 4.1.1, and consider
two trees p, q ∈ FΣ [X ∪ AFΩ (Y ∪ Ξ)]. It is said that p directly derives q in A if q can be
obtained from p by
Each application of rule (i) or rule (ii) is called a direct derivation in A. If q is obtained
from p by a direct derivation in A (i.e., p directly derives q in A), then we write p ⇒A q.
Therefore, ⇒A is a binary relation in FΣ [X ∪ AFΩ (Y ∪ Ξ)]. If there is no danger of
confusion, we generally omit A in ⇒A .
By finitely many consecutive applications of direct derivations we get derivations.
Accordingly, for any two trees p, q ∈ FΣ [X ∪ AFΩ (Y ∪ Ξ)] we say that
p = p0 ⇒ p1 ⇒ . . . ⇒ pi ⇒ . . . ⇒ pj ⇒ . . . ⇒ pk = q (1)
As A may have different productions with the same left side, there could be more
than one q ∈ FΩ (Y ) such that (p, q) ∈ τA for a given p ∈ FΣ (X), i.e., A is in general
nondeterministic. However, at each step of a transformation we have only finitely many
choices. Therefore, pτA is finite for every p ∈ FΣ (X).
A tree transformation is an F-transformation if it can be induced by an F-transducer.
The class of all F-transformations will be denoted by F.
Take an arbitrary set A. The ith component of a vector a ∈ An will be denote by ai ;
i.e., a = (a1 , . . . , an ). If a1 = . . . = an = a then for a we write an . If a ∈ An and b ∈ B m
are arbitrary two vectors, then (a, b) will stand for (a1 , . . . , an , b1 , . . . , bm ). Assume that
133
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
k = min(m, n). Then ab stands for (a1 b1 , . . . , ak bk ) or ((a1 , b1 ), . . . , (ak , bk )), depending
on the context.
Consider a p ∈ FΣ (X ∪ Ξn ), and let p = (p1 , . . . , pn ) be a vector of trees. Then we
shall write p(p) for p(p1 , . . . , pn ). Moreover, if p ∈ FΣ (X ∪ Ξn )m and q = (q1 , . . . , qn ) is
a vector of trees, then p(q) will stand for (p1 (q), . . . , pm (q)).
Consider the homomorphism ϕ : (X ∪ Ξ)∗ → Ξ∗ given by xϕ = e (x ∈ X) and ξϕ = ξ
(ξ ∈ Ξ). Set
and
ˆ
F̂Σ (X ∪ Ξn ) = {p ∈ FΣ (X ∪ Ξn ) | yd(p)ϕ = ξ1 . . . ξn }.
Moreover, if m > 0 then let
Let
r(p1 , p2 ) ⇒ r(p11 , p2 ) ⇒ . . . ⇒ r(p1k , p2 ) ⇒ r(p1k , p′2 ) (2)
(r ∈ F̂Σ [X ∪ AFΩ (Y ) ∪ Ξ2 ])
be a subderivation of α, where the first k direct derivation steps apply to the subtree p1 ,
and then the (k + 1)th step concerns the subtree p2 . Replacing the subderivation (2) in
α by
r(p1 , p2 ) ⇒ r(p1 , p′2 ) ⇒ r(p11 , p′2 ) ⇒ . . . ⇒ r(p1k , p′2 ) (3)
we obviously get a new derivation
β : p ⇒∗ q.
134
4.1 Basic concepts
y y y y
x x
⇒ a1 x ⇒ a1 a1 ⇒ ω
σ
σ σ a0
Figure 4.1
Thus (σ(x, x), ω(y)) is in τA . In fact, τA consists of this single pair (σ(x, x), ω(y)).
Indeed, the only ΣX-tree of height 0 is x, which obviously is not in dom(τA ). If p ∈
FΣ (X) is a tree with height greater than 1, then it should contain at least one of the
following trees as a subtree:
σ(σ(x, x), σ(x, x)), σ(σ(x, x), x) and σ(x, σ(x, x)).
One can easily see that none of these subtrees can be transformed by A. ✷
135
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
F-transducers transform a tree from the leaves of the tree towards the root of the tree.
Now we define a system which works in the opposite direction.
(1) Σ, X, A, Ω, Y and A′ are specified the same way as in Definition 4.1.1, but here
A′ is called the set of initial states,
(2) P is a finite set of productions (or rewriting rules) of the following two types:
(i) ax → q (a ∈ A, x ∈ X, q ∈ FΩ (Y )),
(ii) aσ(ξ1 , . . . , ξm ) → q (a ∈ A, σ ∈ Σm , m ≥ 0, q ∈ FΩ [Y ∪ AΞm ]).
In the sequel we shall write simply aσ for aσ(ξ1 , . . . , ξm ). Moreover, for a production
p → q we shall use the notation (p, q), too.
Obviously, a production of type (ii) in Definition 4.1.4 can be written in the form
aσ → q(a1 ξ1n1 , . . . , am ξm
nm
)
(ii) if p = σ(p1 , . . . , pm ) (σ ∈ Σm , m > 0), then for any (aσ, q(a1 ξ1n1 , . . . , am ξm
nm )) ∈ P
(iii) nothing is in any pτA,a unless this follows from (i) and (ii).
For R-transformations we also give another definition which shows how a transforma-
tion is carried out step by step.
Let p, q ∈ FΩ [Y ∪ AFΣ (X ∪ Ξ)] be trees, and consider the R-transducer of Defini-
tion 4.1.4. It is said that p directly derives q in A if q can be obtained from p by
136
4.1 Basic concepts
Each application of steps (i) and (ii) is called a direct derivation in A. The relation
expressing the direct derivation will be denoted by ⇒A , i.e., we write p ⇒A q if q is
obtained from p by a direct derivation in A. Frequently, A will be omitted in ⇒A . Any
finite sequence of consecutive direct derivations defines a derivation. More precisely,
p = p0 ⇒ p1 ⇒ . . . ⇒ pi ⇒ . . . ⇒ pj ⇒ . . . ⇒ pk = q (4)
Let
r(p1 , p2 ) ⇒ r(p11 , p2 ) ⇒ . . . ⇒ r(p1k , p2 ) ⇒ r(p1k , p′2 ) (5)
(r ∈ F̂Ω [Y ∪ AFΣ (X ∪ Ξ2 )])
be a subderivation of α, where the first k direct derivation steps are carried out in the
subtree p1 , and then in the (k + 1)th step we apply a production in the subtree p2 .
Replacing the subderivation (5) in α by
we get a derivation
β : p ⇒∗ q.
137
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
138
4.1 Basic concepts
x x x x x x x
σ σ σ σ σ a1 σ
σ ⇒ σ σ ⇒ a1 σ ⇒ ω1 σ ⇒
σ a1 a2 ω1 a2 ω1 a2
a0 ω2 ω2 ω2
x x x
y1 σ y1 σ y1 a2 y1 y2
ω1 σ ⇒ ω1 a2 ⇒ ω1 ω1 ⇒ ω1 ω1
ω1 a2 ω1 ω1 ω1 ω1 ω1 ω1
ω2 ω2 ω2 ω2
Figure 4.2
By induction on the heights of input trees one can easily prove that
139
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
(2) An R-transducer can first make copies of an input subtree and then process each
copy independently in a nondeterministic fashion.
(3) F-transducers should process even those subtrees which are deleted afterwards.
Before ending this section we state and prove some simple general results.
The concept of tree homomorphism was introduced in Section 2.4. It is easy to see
that the tree homomorphism h : FΣ (X) → FΩ (Y ), given by the mappings
hm : Σm → FΩ (Y ∪ Ξm ) (m ≥ 0)
and
hX : X → FΩ (Y ),
can be induced by the one-state F-transducer A = (Σ, X, {a}, Ω, Y, P, a) where
Next we prove that the class of all tree homomorphisms coincides with the class of all
transformations induced by HR-transducers.
and
140
4.1 Basic concepts
Example 2.4.15 shows also that the translation of a context-free language by a tree
transducer is not always context-free. In fact, in this example the finite language {x} is
n
translated into the non-CF language {x2 | n ≥ 0}.
141
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
Lemma 4.1.11 For each T ∈ Rec(Σ, X) there exists an F-transducer A such that
dom(τA ) = range(τA ) = T and τA is the identity mapping of T .
(1) A production of A is linear if each auxiliary variable occurs at most once in its
right-hand side. Moreover, A is a linear F-transducer (LF-transducer) if all of its
productions are linear.
(i) x → ay (x ∈ X, a ∈ A, y ∈ Y ) or
142
4.2 Some classes of tree transformations
143
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
The R-transducer of 4.1.6 is deterministic and nondeleting, but it is neither linear nor
totally defined.
Let us note that R-relabelings are linear and nondeleting R-transducers.
The abbreviations introduced above for classes of tree transducers can be combined to
indicate further subclasses. For instance, an LNF-transducer is a linear nondeleting F-
transducer. Moreover, a transformation is a K-transformation if it can be induced by a K-
transducer. The class of all K-transformations will be denoted by K. Thus, for example,
LN F is the class of all LNF-transformations, i.e., the class of all transformations induced
by linear nondeleting F-transducers. By Theorem 4.1.9, we shall write simply H instead
of HF and HR. Moreover, Frel, resp. Rrel, will denote the class of F-relabelings, resp.
R-relabelings.
We now prove
Proof. In order to prove Theorem 4.2.5, we give (i) an F-transformation which is not
in R and (ii) an R-transformation which cannot be induced by any F-transducer.
(i) Consider the LDF-transducer A of Example 4.1.3. If for an R-transducer B =
(Σ, {x}, B, Ω, {y}, P ′ , B ′ ) we have (σ(x, x), ω(y)) ∈ τB , then at the first step of a
derivation bσ(x, x) ⇒∗B ω(y) (b ∈ B ′ ) we should apply a production of the form
bσ → b′ ξ1 , bσ → b′ ξ2 , bσ → ω(b′ ξ1 ), bσ → ω(b′ ξ2 ) or bσ → ω(y), where b′ ∈ B. In
each of the above cases one of the auxiliary variables ξ1 and ξ2 is deleted. Therefore,
dom(τB ) is infinite.
(ii) Take the DR-transducer A of Example 4.1.6. Assume that an F-transducer
B = (Σ, {x}, B, Ω, {y1 , y2 }, P ′ , B ′ ) induces τA . Obviously, P ′ should then contain a
production of the form
σ(b) → b1 ω2 (q1 , q2 ) (b, b1 ∈ B).
We may confine ourselves to the following cases:
(I) q1 = σ k (y1 ) and q2 = σ k (y2 ),
Corollary 4.2.6 DF and DR are incomparable and so are DF and R, and F and DR.
✷
144
4.2 Some classes of tree transformations
Proof. By (i) in the proof of Theorem 4.2.5, LF is not a subclass of LR. Thus, it is
enough to show the validity of LR ⊆ LF.
Let A = (Σ, X, A, Ω, Y, P, A′ ) be an LR-transducer. Then the productions from P can
be written in the form
(i) ax → q (a ∈ A, x ∈ X, q ∈ FΩ (Y )), or
σ(b1 , . . . , bm ) → bq(ξ1 , . . . , ξm ) (σ ∈ Σm , m ≥ 0, b1 , . . . , bm , b ∈ B, q ∈ FΩ (Y ∪ Ξm ))
bσ → q(c1 ξ1 , . . . , cm ξm ),
Obviously B is linear.
In order to complete the proof of Theorem 4.2.7, it is enough to show that the equiv-
alence
p ⇒∗B bq ⇐⇒ bp ⇒∗A q (1)
holds for all b ∈ B, p ∈ FΣ (X) and q ∈ FΩ (Y ). We shall proceed by induction on hg(p).
If hg(p) = 0, then (1) obviously holds by the definition of P ′ .
145
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
Now let p = σ(p1 , . . . , pm ) (σ ∈ Σm , m > 0), and assume that (1) has been proved for
all trees in FΣ (X) of lesser height.
(I) Let p ⇒∗B bq hold. More in detail, let
also exists in A.
(II) Assume that in A we have a derivation
is also valid. ✷
For linear nondeleting tree transformations we have the following stronger result.
Theorem 4.2.8 LN R = LN F.
and
146
4.3 Compositions and decompositions of tree transformations
F R
DF LF DR
LR
LN F = LN R
Frel = Rrel
Figure 4.3.
147
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
148
4.3 Compositions and decompositions of tree transformations
Lemma 4.3.2 F ◦ H ⊆ F.
q(b0 ξ1 , . . . , b0 ξm ) ⇒∗B b0 r
(ii) σ(a1 , . . . , am ) → ar (σ ∈ Σm , m ≥ 0, a1 , . . . , am , a ∈ A, r ∈ F∆ (Z ∪ Ξm )) is in P ′′
iff there is a production σ(a1 , . . . , am ) → aq in P such that q ⇒∗B b0 r holds. Since
at each step of the transformation of a tree the number of applications is finite,
P ′′ is finite.
(II) Suppose that (4) and the derivations pi ⇒∗C ai ri (i = 1, . . . , m) are valid. Then, by
the induction hypothesis, there are trees qi ∈ FΩ (Y ) (i = 1, . . . , m) such that pi ⇒∗A ai qi
149
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
and
q ⇒∗B q(b0 r1 , . . . , b0 rm ) ⇒∗B b0 r(r1 , . . . , rm ) = b0 r
hold. ✷
From Theorem 4.2.7 and the Lemmas 4.3.1 and 4.3.2 we directly obtain
Theorem 4.3.3 F = LF ◦ H = LR ◦ H. ✷
The constructions in the proofs of Lemma 4.3.1 and 4.3.2 preserve determinism. Thus,
we have
Now we investigate some special classes of F-transformations for closure under com-
position.
P ′ = P ∪ {x → ∗y | x ∈ X, y ∈ Y } ∪ {σ(b1 , . . . , bm ) → ∗y | σ ∈ Σm ,
m ≥ 0, b1 , . . . , bm ∈ B, y ∈ Y }.
If A is linear, then so is B. ✷
(i) LF ◦ LF = LF,
(ii) LR ◦ LR = LF.
150
4.3 Compositions and decompositions of tree transformations
The fact that the left side of (5) implies its right side can be shown by reversing the
above argument.
In order to prove (ii) it is enough to note that the HF-transducer C constructed to the
LF-transducer A in the proof of Lemma 4.3.1 is also linear. Moreover, by Theorem 4.2.7,
the inclusion LR ⊆ LF holds. ✷
Using an argument similar to that used in the proof of Theorem 4.3.6 (i), one can
prove
151
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
Theorem 4.3.9 F ◦ DF = F. ✷
(i) ax → r (x ∈ X) is in P ′′ iff it is in P .
some n1 , . . . , nm ).
For each p ∈ FΣ (X) let us denote by p′ ∈ FΩ (X) the tree given as follows:
(I) if p = x ∈ X, then p′ = x,
152
4.3 Compositions and decompositions of tree transformations
The fact that the right side of (6) implies its left side can be proved by the converse
of the computation above. ✷
Lemma 4.3.11 H ◦ R ⊆ R.
Theorem 4.3.13 For each n ≥ 1 the inclusions F n ⊆ Rn+1 and Rn ⊆ F n+1 hold. ✷
One can show that F is not closed under composition by LNF-transformations either.
For R, we have
Theorem 4.3.15 R ◦ LN R = R.
153
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
From Theorem 4.1.10 and Lemma 4.3.16, using the inclusion R ⊆ F 2 (see Theorem
4.3.13), we get
154
4.4 Tree transducers with regular look-ahead
Definition 4.4.1 A root-to-frontier tree transducer with regular look-ahead (RR -trans-
ducer) is a system A = (Σ, X, A, Ω, Y, P, A′ ), where
(1) Σ, X, A, Ω, Y and A′ have the same meanings as in Definition 4.1.4,
(2) P is a finite set of productions (or rewriting rules) of the form (p → q, D), where
p → q is an R-transducer production and D is a mapping of the set of all auxiliary
variables occurring in p into Rec(Σ, X).
If p is of the form ax (x ∈ X) or aσ with σ ∈ Σ0 , then the domain of D is empty. We
write such rules generally as ax → q and aσ → q, respectively. Moreover, for any a ∈ A,
we put A(a) = (Σ, X, A, Ω, Y, P, a).
155
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
Example 4.4.5 Let X = {x} and Σ = Σ1 ∪ Σ2 , where Σi = {σi } (i = 1, 2). Take the
forests T1 = {σ1 (x)}∗x and T2 = {σ1 (x)}. Let A = (Σ, X, {a0 , a1 }, Ω, Y, P, a0 ) be the
RR -transducer where Ω = Ω1 = {ω}, Y = {y} and P consists of the productions
B = (Σ, X, B, Ω, Y, P ′ , B ′ )
exists. Then for every n(≥ 0), the production applied first in a derivation b0 σ2 (σ1n (x),
σ1 (x)) ⇒∗B ω n+1 (y) (b0 ∈ B ′ ) should be of the form
156
4.4 Tree transducers with regular look-ahead
(i) b0 σ2 → q(bξ1 ) or
Let k be the maximum of the heights of right sides of productions from P ′ and n ≥ 3k.
Then the considered production should be of the form (i). But in this case all pairs
(σ2 (σ1n (x), p), ω n+1 (y)) (p ∈ FΣ (X)) are in τB , which is a contradiction. ✷
(i) RR ⊆ DFrel ◦ R,
(II) σ → (σ A1 , . . . , σ Ak )σ (σ ∈ Σ0 ),
(σ ∈ Σm , m > 0; a, ai ∈ B, vi ∈ V, i = 1, . . . , m),
where
a = (σ A1 (a11 , . . . , am1 ), . . . , σ Ak (a1k , . . . , amk ))
and vij = 1 iff aij ∈ A′j . Obviously, B is a deterministic F-relabeling.
One can easily show that B relabels every ΣX-tree p in the following way:
157
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
(α′ ) ap → r (a ∈ A, p ∈ X ∪ Ω0 , r ∈ F∆ (Y )) is in P ′′ iff it is in P,
(β ′ ) a(σ, (v1 , . . . , vm )) → r (a ∈ A; σ ∈ Σm , m > 0; vi ∈ V, i = 1, . . . , m; r ∈ F∆ [Y ∪
AΞm ]) is in P ′′ iff (σ, (v1 , . . . , vm )) occurs in a tree τB (p) (p ∈ FΣ (X)) and P
contains a production (aσ → r, D) such that vij = 1 whenever D(ξi ) = Tj (1 ≤
i ≤ m, 1 ≤ j ≤ k).
In order to prove τA = τB ◦ τC it is enough to show that for arbitrary a ∈ A, p ∈ FΣ (X)
and r ∈ F∆ (Y ) the equivalence
ap ⇒∗A r ⇐⇒ aτB (p) ⇒∗C r
holds. This can be carried out by induction on hg(p).
It is also easy to show that C is deterministic (linear) if A is deterministic (linear). ✷
Theorem 4.4.6 (iii) shows that DRR -transducers induce (partial) mappings.
Next we show that RR is closed under certain special F-transformations.
∗ br(ξ , . . . , ξ ) with b ∈ B; b ∈ B ni , ξ ∈
is a derivation q(b1 ξ 1 , . . . , bm ξ m ) ⇒B 1 m i i
Ξni , ξij = ξn1 +...+ni−1 +j , 1 ≤ j ≤ ni , i = 1, . . . , m and r ∈ F∆ (Z ∪ Ξn ). Then P ′′
contains the production ((a, b)σ → r(a1 b1 ξ1n1 , . . . , am bm ξm
T
nm ), D ′ ), where D ′ (ξ ) =
i
−1
(τA(ai ) (dom(τB(bij ) )) | j = 1, . . . , ni ) ∩ D(ξi ) (i = 1, . . . , m). If b ∈ B ′ , then
j
((a, b0 )σ → r(a1 b1 ξ1n1 , . . . , am bm ξm
nm ), D ′ ) is also in P ′′ .
158
4.4 Tree transducers with regular look-ahead
159
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
k1n k
derivation q(bn0 1 ξ 1 , . . . , bn0 m ξ m ) ⇒∗B b0 r(ξ1k111 , . . . , ξ1n 1 , . . . , ξm
km1 , . . . , ξ mnm ) where
1 mnm
1
ξ i ∈ Ξni , ξij = ξn1 +...+ni−1 +j , 1 ≤ j ≤ ni , i = 1, . . . , m, k11 + . . . + k1n1 + . . . + km1 +
. . . + kmnm = k, r ∈ F̂∆ (Z ∪ Ξk ). Then the production
k1n k1n1
(aσ → r(ak1111 ξ1k11 , . . . , a1n11 ξ1
, . . . , akmm1
1
km1
ξm kmnm kmnm
, . . . , amnm
ξm ), D ′ )
T
is in P ′′ , where for every i(= 1, . . . , m), D ′ (ξi ) = (dom(τA(aij ) ) | ξij occurs in q
but it does not occur in r) ∩ D(ξi ).
Using a similar argument as in the proof of (ii), we get that D ′ (ξi ) is a regular forest.
It is obvious that C is deterministic.
Finally, to show τA ◦ τB = τC it is enough to prove that for all a ∈ A, p ∈ FΣ (X) and
r ∈ F∆ (Z) the equivalence
(i) RR ◦ Frel ⊆ RR ,
hold. ✷
Next we show that the classes of LF-transformations and LRR -transformations coin-
cide.
(i) If x → aq (x ∈ X, a ∈ A, q ∈ FΩ (Y )) is in P , then ax → q is in P ′ .
(ii) If σ(a1 , . . . , am ) → aq (σ ∈ Σm , m ≥ 0, a1 , . . . , am , a ∈ A, q ∈ FΩ (Y ∪ Ξm )) is in P ,
then (aσ → q(a1 ξ1 , . . . , am ξm ), D) is in P ′ , where for every i(= 1, . . . , m),
dom(τA(ai ) ) if ξi does not occur in q,
D(ξi ) =
FΣ (X) otherwise.
160
4.4 Tree transducers with regular look-ahead
p ⇒∗A aq ⇐⇒ ap ⇒∗B q
In the proof of the above theorem we used look-ahead to ensure that the LRR -
transducer will not transform any tree which contains a subtree for which the LF-
transducer has no transform but which it would later delete.
From Theorem 4.4.9, by Theorem 4.3.6 (i), we get
Next we show that RR is closed under LRR -transformations and DRR is closed under
composition.
(i) RR ◦ LRR = RR ,
Proof. The inclusion H ◦ LRR ⊆ RR directly follows from Theorem 4.4.11 (i). To show
RR ⊆ H ◦ LRR , consider an RR -transducer A = (Σ, X, A, ∆, Z, P, A′ ). Omit regular
look-ahead in A and for the resulting R-transducer consider the H-transducer B and
LR-transducer C given in the proof of Lemma 4.3.10. Now it is impossible to provide C
with a suitable regular look-ahead in an obvious way since H-transducers do not preserve
regularity. We shall solve this problem in the following way.
Take the tree homomorphism h : FΩ (X) → FΣ (X) given as follows:
161
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
One can easily verify that for every p ∈ FΣ (X) the equality h(τB (p)) = p holds, i.e.,
h(p′ ) = p (for p′ , see the proof of Lemma 4.3.10).
Now replacing each production aσ ′ → r(a1 ξ 1 , . . . , am ξ m ) (σ ∈ Σm , m > 0, (aσ →
r(a1 ξ1n1 , . . . , am ξm
nm ), D) ∈ P ) in P ′′ by (aσ ′ → r(a ξ , . . . , a ξ ), D ′ ), where D ′ (ξ ) =
1 1 m m ij
h−1 (D(ξi )) (i = 1, . . . , m, j = 1, . . . , k), from C we get an LRR -transducer since, by The-
orem 2.4.18, h−1 preserves recognizability. Let us denote the resulting LRR -transducer
also by C.
Using tree induction, it is easy to prove that τA = τB ◦ τC . ✷
(5) P is a finite set of productions (or rewriting rules) of the following two types:
(i) ax → w (a ∈ A, x ∈ X, w ∈ Y ∗ ),
(ii) aσ → w (a ∈ A, σ ∈ Σm , m ≥ 0, w ∈ (Y ∪ AΞm )∗ ). (Here AΞm is treated as
an alphabet; the elements of it are the trees of the form aξi with a ∈ A and
ξi ∈ Ξm .)
For ap → w we shall use the notation (ap, w), too. Moreover, for any a ∈ A, we put
A(a) = (Σ, X, A, Y, P, a).
Next we define translations induced by a GSDT A. To this end, we associate with
each a ∈ A and p ∈ FΣ (X) a subset pτA,a as follows:
(i) if p ∈ (X ∪ Σ0 ), then pτA,a = {w | (ap, w) ∈ P };
(iii) nothing is in any pτA,a unless this follows from (i) and (ii).
162
4.5 Generalized syntax directed translators
163
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
i.e., τB (p) = yd(τA (p)), where A is the R-transducer of Example 4.1.6. One can easily
show that the previous equality holds for every p ∈ FΣ ({x}). ✷
The above relation generally holds between GSDTs and R-transducers as it is shown
by
Theorem 4.5.4 For each GSDT A = (Σ, X, A, Y, P, A′ ) there exist a ranked alphabet Ω
and an R-transducer B = (Σ, X, A, Ω, Y, P ′ , A′ ) such that τA = {(p, yd(q)) | (p, q) ∈ τB }.
Moreover, if A is linear, deterministic, nondeleting or a GSDH-transducer, then B
can also be chosen, correspondingly, as a linear, deterministic, nondeleting or an RH-
transducer.
Conversely, for every R-transducer B there exists a GSDT A such that {(p, yd(q)) |
(p, q) ∈ τB } = τA . If B is, respectively linear, deterministic, nondeleting or an RH-
transducer, then A is linear, deterministic, nondeleting or a GSDH-translator.
164
4.6 Surface forests
holds for arbitrary b ∈ B, p ∈ FΣ (X) and w ∈ Y ∗ . This can be carried out by induction
on hg(p). Moreover, the remaining conclusions of the second part of Theorem 4.5.4 are
obviously valid. ✷
Lemma 4.6.2 If K is a class of tree transformations which contains all identity trans-
formations, then Rec is included as a subclass in Surf(K). ✷
Of course, this lemma applies to all of the classes of tree transformations which we
have considered (F, R, LF , H etc.).
Next we characterize F-transformations preserving regularity. For this we should in-
troduce some more terminology.
Definition 4.6.4 For each p ∈ FΣ (X ∪Ξn ), pathi (p) (1 ≤ i ≤ n) is given in the following
way:
(i) if p ∈ Σ0 ∪ X, then pathi (p) = ∅,
165
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
Thus, pathi (p) is a language over the alphabet {1, . . . , m}, where m is the maximal
integer with Σm 6= ∅.
Obviously, the elements of pathi (p) describe paths leading from the root of p to a leaf
labelled by ξi .
If pathi (p) consists of a single word, then l pathi (p) denotes the length of this word.
Proof. Since the F-transducer given in the proof of Lemma 4.1.11 is linear, by Theorem
4.3.6 (i), it is enough to show that for each LF-transducer A = (Σ, X, A, Ω, Y, P, A′ ),
range(τA ) is regular. Without loss of generality, we may assume that A is connected.
Consider the regular ΩY -grammar G = (A, Ω, Y, P ′ , A′ ), where P ′ is given as follows:
(i) if x → aq x ∈ X, a ∈ A, q ∈ FΩ (Y ) is in P , then a → q is in P ′ ,
(ii) if σ(a1 , . . . , am ) → aq σ ∈ Σm , m ≥ 0, a1 , . . . , am , a ∈ A, q ∈ FΩ (Y ∪ Ξm ) is in P ,
then a → q(a1 , . . . , am ) is in P ′ .
In order to prove the lemma it is enough to show that the equivalence
a ⇒∗G q ⇐⇒ ∃p ∈ FΣ (X) (p ⇒∗A aq) (1)
166
4.6 Surface forests
(II) Assume that p ⇒∗A aq holds. We shall show by induction on hg(p) that the left
side of (1) is also valid. If hg(p) = 0, then, by the choice of P ′ , the right side of
(1) obviously implies its left side.
Now let p = σ(p1 , . . . , pm ) (σ ∈ Σm , m > 0), and assume that our statement
has been proved for all trees from FΣ (X) with height less than hg(p). Moreover,
let us write p ⇒∗A aq in the form p ⇒∗A σ(a1 q1 , . . . , am qm ) ⇒A aq(q1 , . . . , qm ),
where σ(a1 , . . . , am ) → aq is in P and pi ⇒∗A ai qi (i = 1, . . . , m). Then, by the
definition of P ′ and the induction hypothesis, we have a ⇒G q(a1 , . . . , am ) ⇒∗G
q(q1 , . . . , qm ) = q. ✷
From Lemma 4.6.5, using Theorems 4.2.7 and 4.4.9, respectively, we get the following
results.
Proof. Assume that τA preserves regularity. Let a ∈ A be a copying state, and take two
trees p ∈ F̂Σ (X ∪ Ξ1 ) and q ∈ F̂Ω (Y ∪ Ξn ) such that p(aξ1 ) ⇒∗ a′ q(ξ1n ) where a′ ∈ A′
and n > 1. Suppose that range(τA(a) ) is infinite. Then there is an s ∈ range(τA(a) ) with
hg(s) > k · |A|, where k is the maximum of the heights of the right-hand sides of the
productions in P . Let r ∈ FΣ (X) be a tree such that r ⇒∗ as. Since hg(s) > k · |A|,
there are trees r1 , r2 ∈ F̂Σ (X ∪ Ξ1 ) and r3 ∈ FΣ (X) such that the following conditions
are satisfied:
(i) r1 r2 (r3 ) = r,
167
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
Therefore, for each i(= 0, 1, . . .), there is a derivation pi = p r1 (r2i (r3 )) ⇒∗ a′ q(tni ) = qi
where ti = s1 si2 (s3 ) (the powers ti of any tree t ∈ FΣ (X ∪ Ξ1 ) are defined thus: t0 = ξ1 ,
and ti+1 = t(ti ) for each i ≥ 0). Obviously, hg(qi ) increases with i when i is large enough.
Now consider the forest T = {pi | i = 0, 1, . . .}. Obviously, T is regular. Since τA
preserves regularity, this implies that T ′ = T τA is also regular. Take an ΩY -recognizer
B = (B, Ω, Y, β, B ′ ) with T ′ = T (B). Choose an
i ≥ 2k(hg(p(r)) + 1) + 2|B| k hg(p(r)) + 1 .
Then
there exists a tree t ∈ F Ω (Y ) with k hg(p(r)) + 1 + |B| ≤ hg(t) < k hg(p(r)) +
1 + 2|B| such that
q = q(t, tin−1 ) (2)
is also in T ′ . To prove the lemma it is enough to show that there exist no j and a′′ ∈ A′
such that pj ⇒∗ a′′ q. Suppose
m
pj ⇒∗ a′′ q ′ (t′ ) = a′′ q
holds, where a′′ ∈ A′ , q ′ ∈ F̂Ω (Y ∪ Ξm ), r3 ⇒∗ b1 s′1 , r2 (bl ξ1 ) ⇒∗ bl+1 s′l+1 b1 , bl+1 ∈ A,
sl+1 ∈ FΩ (Y ∪ Ξ1 ), l = 1, . . . , j, s′1 ∈ FΩ (Y ) , r1 (bj+1 ξ1 ) ⇒∗ bj+2 s′j+2 bj+2 ∈ A,
s′j+2 ∈ FΩ (Y ∪ Ξ1 ) , p(bj+2 ξ1 ) ⇒∗ a′′ s′j+3 = a′′ q ′ and t′ = s′j+2 s′j+1 (. . . (s′1 ) . . .) .
By the choice of i, there exists a u (2 ≤ u ≤ j + 3) such that ξ1 occurs in
su , s′u+1 , . . . , s′j+3 but ξ1 does not occur in s′u−1 . Moreover, let u − 1 ≤ u1 < . . . <
′
Proof. Suppose that a1 , . . . , ak areS all the copying states of A. Let Ti = range(τA(ai ) )
(i = 1, . . . , k). Moreover, set T = (Ti | i = 1, . . . , k). By our assumptions, T is finite.
Define an F-transducer B = (Σ, X, B, Ω, Y, P ′ , B ′ ), where
[
B = (A − {ai | i = 1, . . . , k}) ∪ ({ai } × Ti | i = 1, . . . , k)
and
B ′ = (A′ ∪ A′ × T ) ∩ B.
Moreover, P ′ is given as follows:
168
4.6 Surface forests
(ii) Let
σ(b1 , . . . , bm ) → aq(ξ1 , . . . , ξm )
(σ ∈ Σm , m > 0, b1 , . . . , bm , a ∈ A, q ∈ FΩ (Y ∪ Ξm )) be in P . We distinguish the
following cases:
(iia) The state a is deleting. Fix any q ∈ FΩ (Y ∪ Ξm ) such that every ξi occurs
at most once in q. Then P contains every linear production σ(c1 , . . . , cm ) →
aq(ξ1 , . . . , ξm ) such that
(bj , qj )(qj ∈ Tl ) if bj is copying and bj = al ,
cj =
bj otherwise.
(iib) The state a is nondeleting but not copying. Then all productions
σ(c1 , . . . , cm ) → aq(η1 , . . . , ηm )
and
ξj if ξj occurs at most once in q,
ηj =
qj (= π2 (cj )) otherwise.
(Observe that if ξj occurs at least twice in q, then bj is copying.)
(iic) The state a is copying. Then P ′ contains all productions
and
qj if ξj occurs in q,
ηj =
any fixed tree from FΩ (Y ) otherwise.
169
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
σ(c1 , . . . , cm ) → aq ′ (η1 , . . . , ηm )
σ(c1 , . . . , cm ) → (a, q ′ )q ′
σ(c1 , . . . , cm ) → aq ′
given by (iia) is in P ′ .
Thus, in all three cases the required derivations in B exist.
170
4.6 Surface forests
The following result shows that Surf(F) ⊂ Surf(R). More precisely, we have
Proof. The first statement of Theorem 4.6.12 follows from Theorem 4.3.3 and Lemma
4.6.5.
It is obvious that Surf(H) ⊆ Surf(R). We show that the inclusion is proper. For this,
consider Example 4.1.6. Moreover, let S = {ω2 (ω1n (y1 ), ω1n (y2 )) | n = 0, 1, . . .}. If R
denotes the regular forest {σ(x)} ·x {σ(x)}∗x , then RτA = S. Therefore, S ∈ Surf(R).
Assume that for an HR-transducer B = (∆, Z, {b0 }, Ω, Y, P ′ , b0 ) and regular forest
T ⊆ F∆ (Z), we have S = T τB. Then B can be chosen linear since in the opposite case
in T τB there is a tree with at least two occurrences of a subtree. Therefore, by Theorem
2.4.16, S is regular. But one can show similarly as in Example 2.4.15 that S is not
regular. ✷
Next we show some closure properties of surface forests which will be needed also in
Section 4.7.
171
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
Theorem 4.6.14 The intersection of an R-surface forest with a regular forest is again
an R-surface forest.
Proof. The proof is similar to that of the previous theorem, but now we shall use the fact
that the transformation given in the proof of Lemma 4.1.11 is an LNR-transformation.
Moreover, by Theorem 4.3.15, the composition of an R-transformation by an LNR-
transformation is again an R-transformation. ✷
where (aσ, q(. . . , aij ξi , . . .)) ∈ P (q ∈ F̂Ω (Y ∪ Ξn ) for some n) and aij pi ⇒∗A qij , i.e.,
the considered copy of pi is translated by A starting in state aij into qij . Furthermore,
suppose that applying to q the transducer B starting in b, we get
bq = bq(. . . , qij , . . .) ⇒∗B r(. . . , bij1 qij , . . . , bijk qij , . . .) ⇒∗B r(. . . , rij1 , . . . , rijk , . . .) = r
in P ′′ and suppose that C has the required property for trees with height less than hg(p),
then (a, b)p ⇒∗C r also holds. Accordingly, the formal definition of P ′′ reads as follows:
(i) The production (a, b)x → r (a, b) ∈ C, x ∈ X, r ∈ F∆ (Z) is in P ′′ if there is an
ax → q in P such that bq ⇒∗B r.
n′ n′1n n′ n′
bq ⇒∗B r b11 ξ1111 , . . . , b1n1 ξ1n1 1 , . . . , bm1 ξm1
m1 mnm
, . . . , bmnm ξmn m
172
4.7 Auxiliary concepts and results
′
bij ∈ B nij , ξij = ξn1 +...+ni−1 +j , i = 1, . . . , m, j = 1, . . . , ni , n′11 + . . . + n′mnm =
n′ , r ∈ F̂∆ (Z ∪ Ξn′ ) holds, then the production
n′ n′1n n′ n′
(a, b)σ → r (a1111 b11 , . . . , a1n 1 b1n1 )ξ1k1 , . . . , (amm1 mnm km
1 bm1 , . . . , amnm bmnm )ξm
1
Let us note that the C constructed above may delete certain subtrees of input trees so
that dom(τC ) becomes larger than dom(τA ◦ τB ).
If R in Theorem 4.6.15 is regular then, by Corollary 4.3.17 and Theorem 2.4.2, S is
also regular. Thus we have
f (p) = {q(σ(q1′ , . . . , qm
′
)) | q ∈ Tσ , qi′ ∈ f (pi ), i = 1, . . . , m}, and
S
(iii) if T ⊆ FΣ (X), then f (T ) = f (p) | p ∈ T .
173
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
Proof. Let T ⊆ FΣ (X) be a regular forest and f a regular insertion given by f (d) = Td
(d ∈ Σ ∪ X, Td ⊆ FΩ (Ξ1 )). Consider a regular tree grammar G = (N, Σ, X, P, a0 )
given in normal form such that T (G) = T . Moreover, for every Td (d ∈ Σ ∪ X) let
Gd = (N d , Ω, Ξ1 , P d , ad0 ) be a regular tree grammar in normal form generating Td . For
each d ∈ Σ ∪ X and a ∈ N consider the tree grammar Gda = (Nad , Ω, Ξ1 , Pad , (ad0 , a)),
where Nad = N d × {a} and
P ′ = {a → (ad0 , a) | a ∈ N, d ∈ Σ ∪ X}
[
∪ Pad − {(ad , a) → ξ1 | ad ∈ N d } | a ∈ N, d ∈ Σ ∪ X
∪ {(ad , a) → (a, d) | ad → ξ1 ∈ Pad , ad ∈ N d , a ∈ N, d ∈ Σ ∪ X}
∪ {(a, σ) → σ(a1 , . . . , am ) | a → σ(a1 , . . . , am ) ∈ P, σ ∈ Σm , m > 0, a, a1 , . . . , am ∈ N }
∪ {(a, d) → d | a → d ∈ P, a ∈ N, d ∈ Σ0 ∪ X}.
From the construction of G′ it is obvious that the following statements are valid:
Conversely,
(ii) for any a ∈ N and p ∈ FΣ∪Ω (X) each derivation a ⇒∗G′ p should have the form
174
4.7 Auxiliary concepts and results
Lemma 4.7.3 Let K be a class of forests closed under regular insertion. Then R(K)
is also closed under regular insertion.
P9 ={ωd → ω | ω ∈ Ω0 , d ∈ Σ ∪ X} and
175
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
One can easily see that B works as follows: assume that for some a ∈ A, p ∈ FΣ (X)
and q ∈ FΩ (Y ) a derivation ap ⇒∗A q exists. Let q ′ be a tree obtained by inserting
in q arbitrary trees from {#(ξ1 )}∗ξ1 below symbols from Ω ∪ Y . Then for a p′ ∈ f (p),
ap′ ⇒∗B q ′ holds. Conversely, if for some a ∈ A, p ∈ FΣ (X), p′ ∈ f (p) and q ′ ∈ FΩ∪{#} (Y )
a derivation ap′ ⇒∗B q ′ holds then there is a q ∈ FΩ (Y ) such that q ′ ∈ g(q) and ap ⇒∗A q.
Now, consider an arbitrary regular insertion h (into ΩY -trees). For each d ∈ Ω ∪ Y ,
there is a regular tree grammar Gd = (Nd , Ω(d), Ξ1 , Pd , {ad0 }) such that h(d) = T (Gd ).
We may assume that every Gd is in normal form. Since Ω(d) is unary, this means that
the productions of Gd are of the form ad → ωd (a′d ) or ad → ξ1 (ad , a′d ∈ Nd , ωd ∈ Ω(d)).
Furthermore we may assume that the sets Nd are pairwise disjoint. Now construct the
R-transducer
C = (Ω ∪ {#}, Y, C, ∆, Y, P ′′ , C ′ )
with [
C= (Nd | d ∈ Ω ∪ Y ), C ′ = {ad0 | d ∈ Ω ∪ Y }
and
[ [
∆= Ω(d) | d ∈ Ω ∪ Y ∪ Ω ∆1 = Ω(d) | d ∈ Ω ∪ Y ∪ Ω1 , ∆m = Ωm (m 6= 1) .
176
4.7 Auxiliary concepts and results
(III) For arbitrary x ∈ X and (a1 , a2 ) ∈ A×A, P ′ contains the production (a1 , a2 )x → q,
where a1 x ⇒A wa2 (w ∈ Y ∗ ) and q ∈ FΩ (Y ) is a fixed tree with yd(q) = w (such
q exists by the definition of ωa1 x ).
We shall now introduce some more concepts that will be needed in the next section.
Let A = (Σ, X, A, Ω, Y, P, A′ ) be an R-transducer. Take a tree p ∈ FΣ (X) and a node
d of p. Denote by s the subtree of p at this node d. Consider a state a and a derivation
α : ap ⇒∗ q (q ∈ FΩ (Y )). Suppose exactly k copies of this occurrence of s are created
during α and that these are translated into the trees t1 , . . . , tk (∈ FΩ (Y )) starting the
translations, respectively, in states a1 , . . . , ak . In the next definition we distinguish a
sequence of these states which will be called the state-sequence of α at d.
α : ap ⇒∗ q (a ∈ A, p ∈ FΣ (X), q ∈ FΩ (Y )).
177
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
Let d be a node of p and s the subtree at this node d. Replace the given occurrence of
s in p by ξ1 and denote by r the resulting tree. Write α in the form
(a1 d1 → q1 , . . . , an dn → qn )
is the production-sequence of α at d.
α : ap ⇒∗ w (a ∈ A, p ∈ FΣ (X), w ∈ Y ∗ ).
Like in the case of R-transducers, we shall also speak about the state-sequence of α at
the subtree s.
We shall use the notation Rk for the class of all transformations induced by k-copying
R-transducers. Similarly, Gk denotes the class of all transformations induced by k-
copying GSDT’s. Moreover, Rf and Gf will stand for the classes of transformations
induced by finite-copying R-transducers and finite copying GSDT’s, respectively. Cor-
responding notations will be used for the classes DR, DG etc.
The next result shows that R-transformational languages can be studied through gen-
eralized syntax directed translations.
178
4.7 Auxiliary concepts and results
Theorem 4.7.8 For every k-copying GSDT A = (Σ, X, A, Y, P, A′ ) there exist a ranked
alphabet Ω and a k-copying R-transducer B = (Σ, X, A, Ω, Y, P ′ , A′ ) such that τA =
{(p, yd(q)) | (p, q) ∈ τB}.
Conversely, for every k-copying R-transducer B there exists a k-copying GSDT A such
that τA = {(p, yd(q)) | (p, q) ∈ τB }.
Proof. The R-transducer and GSDT constructed in the proof of Theorem 4.5.4 obviously
have the required properties. ✷
The following theorem gives sufficient conditions under which Rk (K) = DRk (K) holds
for a given class K of forests.
Theorem 4.7.9 Let K be a class of forests closed under relabeling and regular insertion.
Take an R-transducer A = (Σ, X, A, Ω, Y, P, A′ ), an R ∈ K and a positive integer k.
Then
is in DRk (K).
Proof. Since K is closed under regular insertion, we may assume that A′ is a singleton.
Indeed, in the opposite case enlarge A by a new state a0 , Σ by a new unary operational
symbol σ and P by all productions a0 σ → aξ1 (a ∈ A′ ). Let A be the resulting R-
transducer with initial state a0 , and let R = f (R) , where f is a regular insertion given
by f (d) = {σ(ξ1 )} (d ∈ X ∪ Σ). Then R ∈ K and τA (R) = τA (R). Furthermore,
a derivation ap ⇒∗A q (a ∈ A′ , p ∈ R, q ∈ FΩ (Y )) is k-copying if the corresponding
derivation a0 σ(p) ⇒A∗ q is k-copying, and conversely. Thus, we shall assume that A′ =
and
b0 σ → ((a1 σ, q1 ), . . . , (at σ, qt ))(b0 ξ1 , . . . , b0 ξm )
(σ ∈ Σm , ((a1 σ, q1 ), . . . , (at σ, qt )) ∈ ∆m , m = 0, 1, . . .).
Obviously, B is an R-relabeling which relabels trees in the following way: if σ ∈ Σ
[resp. x ∈ X] is a label at a node d of a tree p ∈ FΣ (X), then B relabels d by a
179
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
C = {(u; a1 , . . . , at ) | 1 ≤ u ≤ t ≤ k, ai ∈ A (i = 1, . . . , t)}
α : a0 p ⇒∗A q.
Consider the tree p with (p, p) ∈ τB which is the result of relabeling each node d of p by
the production-sequence of α at d. Then in C we have a derivation
β : (1; a0 )p ⇒∗C q
such that if a = (a1 , . . . , an ) (n ≤ k) is the state-sequence of α at d then ((1; a), . . . , (n; a))
is the state-sequence of β at d. Conversely, if for a p′ ∈ F∆ (X) and q ′ ∈ FΩ (Y ) there is
a derivation
β ′ : (1; a0 )p′ ⇒∗C q ′ ,
then for the (uniquely determined) tree p′ ∈ FΣ (X) with (p′ , p′ ) ∈ τB we have the
derivation
α′ : a0 p′ ⇒∗A q ′ .
Moreover, the state-sequence of β ′ at a node d of p′ is of the form ((1; a′ ), . . . , (m; a′ ))
(a′ = (a′1 , . . . , a′m )) with m ≤ k, and a′ is the state-sequence of α′ at d. Therefore, C
is k-copying and S = RτB ◦ τC holds. Since K is closed under relabelings, this implies
S ∈ DRk (K). ✷
180
4.7 Auxiliary concepts and results
Corollary 4.7.10 Let K be a class of forests closed under relabeling and regular inser-
tion. Take a GSDT A = (Σ, X, A, Y, P, A′ ), a T ∈ K and a positive integer k. Then the
language
is in DG k (K). ✷
Theorem 4.7.12 Let K be a class of forests closed under regular insertion. For each
R ∈ K there exist a linear nondeleting GSDT A and a forest S ∈ K such that
res(yd(R), #) = SτA .
α : a0 p ⇒∗ w1 b1 p1 w2 b2 p1 w3 . . . ws bs p1 ws+1 ⇒∗ w1 v1 w2 v2 w3 . . . ws vs ws+1 = w,
181
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
is in P ′ .
is in P ′ .
182
4.7 Auxiliary concepts and results
By the definition of B, it relabels trees in the following way: take a tree p ∈ FΣ (X),
and let σ(p1 , . . . , pm ) (m > 0) be the subtree of p at a node d. The B provides us with the
information about which of the subtrees p1 , . . . , pm is translated by A(ai ) (i = 1, . . . , k)
into a word from (Y ∪ {#})∗ with
It is clear that C is deterministic. Moreover, one can show by induction on hg(p) for
arbitrary a ∈ A, p ∈ FΣ (X) and w ∈ (Y ∪ {#})∗ the implication
183
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
Proof. Suppose R ⊆ FΣ (X) and let L = yd(R). We introduce the ranked alpha-
bet ∆ = ∆1 = {d | d ∈ Σ ∪ X} and define a regular insertion f by f (d) = {d(ξ1 )}∗ξ1
(d ∈ Σ ∪ X). Moreover, let Ω be the ranked alphabet for which Ω1 = Σ1 ∪ ∆ and
Ωm = Σm (m ≥ 0, m 6= 1). Consider the GSDT
where
P = {a1 d → a1 ξ1 a2 ξ1 # | d ∈ Σ ∪ X}
∪ {a2 d → a2 ξ1 | d ∈ Σ ∪ X}
∪ {a1 x → e | x ∈ X} ∪ {a1 σ → e | σ ∈ Σm , m ≥ 0}
∪ {a2 x → x | x ∈ X} ∪ {a2 σ → a2 ξ1 . . . a2 ξm | σ ∈ Σm , m ≥ 0}.
A = {(a, b) | a ∈ A, b ∈ B n , n = 0, 1, . . . , k}
and a0 = a0 , (b0 ) . Moreover, P is given in the following way:
184
4.7 Auxiliary concepts and results
(i) Let ap → q a ∈ A, p ∈ X ∪ Σ0 , q ∈ FΩ (Y ) be in P and take a vector b ∈ B n
(0 ≤ n ≤ k). Then the production (a, b)p → q is in P .
Assume that a state a ∈ A occurs more than once in a, and let ai1 , . . . , aij (1 ≤ i1 <
. . . < ij ≤ n) be all occurrences of a in a. Then the state-sequences of
β ′ : b0 q ⇒∗A (w#)m ∈ (Z ∪ {#})∗
185
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
at the subtrees ti1 , . . . , tij coincide. Let (b1 , . . . , bs ) be this common state-sequence.
Among ti1 , . . . , tij let ti1 be the tree for which τB(b1 ) (ti1 ) . . . τB(bs ) (ti1 ) has a maximal
number of occurrences of #. Replace the considered occurrences of ti1 , . . . , tij in q by
′
ti1 , and denote by q ′ the resulting tree. We claim that for q ′ we have τB (q ′ ) = (w#)m
with m′ ≥ m. To prove it let us distinguish the following two cases:
(I) There exists an r (1 ≤ r ≤ s) such that # occurs at least twice in the word
τB(br ) (ti1 ). Then our claim obviously holds.
(II) # occurs at most once in each word τB(b1 ) (ti1 ), . . . , τB(bs ) (ti1 ). Take a fixed r
(1 < r ≤ j), and write β ′ in the form
where ∗ is a new symbol. Moreover, define the ranked alphabet ∆, where for each
m (≥ 0),
∆m = { σ, (c1 , . . . , cs ) | σ ∈ Σm , ci = (ai σ, qi ) ∈ P or ci = ∗, i = 1, . . . , s}.
is in P1 .
(β) For each ai ∈ A and σ, (c1 , . . . , cs ) ∈ ∆m , if ci = (ai σ, qi ), then the production
ai σ, (c1 , . . . , cs ) → qi
is in P1 .
186
4.7 Auxiliary concepts and results
187
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
188
4.8 The hierarchies of tree transformations, surface forests andtransformational languages
The following results show that in studying (n, R)-surface forests and (n, R)-
transformational languages we can use RR -transformations, too.
Theorem 4.8.3 For each natural number n, the equality Surf(Rn ) = Surf(RnR ) holds.
Proof. This follows from Theorems 4.4.6 (i) and 4.3.15 and Lemma 4.6.5. ✷
Corollary 4.8.4 For every natural number n, the class of (n, R)-transformational lan-
guages coincides with the class of (n, RR )-transformational languages. ✷
Using Theorems 4.4.7 (i) and 4.2.7, from Theorem 4.8.3 we obtain
Corollary 4.8.5 For every natural number n, Surf(Rn ) is closed under LF-
transformations and LR-transformations. ✷
Now we can state and prove a result giving a recursive procedure by which the hierarchy
theorems can be proved easily. The procedure will be based on the “bridge theorems” of
the previous section which concern the operations res, c2 and c∗ . These associate with
each language which is not in a given class another language which is not in another,
larger class.
Theorem 4.8.6 Let K be a class of forests closed under relabeling and regular insertion.
If ydDRf (K) ⊂ ydR(K), then for each integer n ≥ 1,
ydRn (K) ⊂ ydDRf Rn (K) ⊂ ydDR Rn (K) ⊂ ydRn+1 (K).
Proof. By Theorem 4.3.15 and Lemma 4.7.3, Rn (K) is closed under relabeling and
regular insertion, for every n ≥ 1. In the sequel these facts will be used without further
mention.
We shall proceed by induction on n. Let n = 1. Take a forest R such that R ∈ R(K)
and yd(R) 6∈ ydDRf (K). Then by Theorems 4.7.12, 4.5.4 and 4.2.8 there exist an LNF-
transformation τ and a forest S ∈ R(K) such that res yd(R), # = yd(Sτ ). Moreover,
by Theorem 4.3.15, Sτ ∈ R(K). On the other hand, since yd(R) 6∈ ydDRf (K), by
Theorems 4.7.13 and 4.5.4, res yd(R), # 6∈ ydDR(K). Thus, the proper inclusion
ydDR(K) ⊂ ydR(K) holds.
Next take an R ∈ R(K) with yd(R) 6∈ ydDR(K). Then, by Theorems 4.7.18 and
4.7.8, there exist a 2-copying homomorphism τ and a forest S ∈ R(K) such that
c2 yd(R), # = yd(Sτ ). On the other hand, since yd(R) 6∈ ydDR(K), by Theorems 4.5.4
189
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
and 4.7.19, c2 yd(R), # 6∈ ydR(K). Therefore, the inclusion ydR(K) ⊂ ydDRf (R(K))
is valid.
Again take an R ∈ R(K) with yd(R) 6∈ ydDR(K). By Theorems 4.7.15 and 4.5.4 there
exist a DR-transformation τ and a forest S ∈ R(K) such that, c∗ yd(R), # = yd(Sτ ).
Moreover, since yd(R) ∈
6 ydDR(K), by Theorems 4.7.16 and 4.7.8, c∗ yd(R), # 6∈
ydDRf R(K) . Thus we have got that
ydDRf R(K) ⊂ ydDR R(K) .
Finally, take an R ∈ R2 (K) with yd(R) 6∈ ydDRf R(K) . Then again by Theorems
2
there exist an LNF-transformation τ and a forest S2 ∈ R (K) such that
4.7.12 and 4.5.4,
res yd(R), # = yd(Sτ ). Moreover, by Theorem 4.3.15, Sτ ∈ R (K). On the other
hand, since yd(R)
6∈ ydDRf R(K) , by Theorems 4.7.13 and 4.7.8, res yd(R), # 6∈
ydDR R(K) . Therefore, ydDR R(K) ⊂ ydR2 (K).
Summarizing our results, we have
ydR(K) ⊂ ydDRf R(K) ⊂ ydDR R(K) ⊂ ydR2 (K)
c∗
c2
res
ydDR(Rn (K)) ydRn+1 (K) ydDRf (Rn+1 (K)) ydDR(Rn+1 (K)) ydRn+2 (K)
Figure 4.4.
Lemma 4.8.7 For each k-copying DGSDT A = (Σ, X, A, Y, P, a0 ) there exists a lin-
ear DGSDT B = (Σ, X, B, Y, P ′ , b0 ) such that Par(T τB ) = Par(T τA ), for every forest
T ⊆ FΣ (X).
Proof. For each w ∈ (Y ∪ AΞ)∗ , let w denote the word obtained from w by erasing all
aξ’s (a ∈ A, ξ ∈ Ξ).
Let B = {(a1 , . . . , an ) | n ≤ k, ai ∈ A(i = 1, . . . , n)} and b0 = (a0 ). Moreover, P ′ is
defined in the following way:
190
4.8 The hierarchies of tree transformations, surface forests andtransformational languages
From Lemma 4.8.7, by Theorems 1.6.17 and 4.5.4 and Corollary 4.6.6, we get
We now can state and prove that the hierarchy of (n,R)-transformational languages is
infinite.
hold.
Proof. By Lemma 4.7.2 and Corollary 4.6.6, Rec is closed under regular insertion and
relabeling. Thus, by Theorems 4.8.6, 4.5.4, and 4.7.8, and Corollary 4.8.8, it is enough
to show that there exist a regular forest T ⊆ FΣ (X) and a GSDT A = (Σ, X, A, Y, P, a0 )
such that Par(T τA ) is not semilinear. For this let Σ = Σ1 = {σ}, A = {a0 }, X = {x},
191
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
are valid.
Proof. By Theorems 4.3.3 and 4.3.12 and Corollary 4.6.6, the inclusions ydRn (Rec) ⊆
yd F n+1 (Rec) ⊆ ydRn+1 (Rec) hold. By the proofs of Theorems 4.8.6 and 4.8.9,
n n
ydR (Rec) is a proper subclass of ydH R (Rec) . Moreover, by Theorems 4.3.3
and 4.3.12 and Corollary 4.6.6, the equality H Rn (Rec) = F n+1 (Rec) holds.
Thus, the inclusion ydRn (Rec) ⊂ ydF
n+1 (Rec) is valid. Finally, by Theorem
4.8.9, ydH R (Rec) ⊆ ydDR R (Rec) ⊂ ydRn+1 (Rec). Therefore, the inclusion
n n
From Theorem 4.8.11, using Theorems 4.3.3 and 4.3.12 and Corollary 4.6.6, we get the
following results.
hold. ✷
192
4.9 The equivalence of tree transducers
193
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
(i) p1 (p2 ) ∈ T ,
′
(ii) a0 p1 ⇒∗ q1 (aξ1n ), a′0 p1 ⇒∗ q1′ (a′ ξ1n ),
′
(iii) apn2 ⇒∗ q2 , a′ pn2 ⇒∗ q′2 ,
Then there exists an r ∈ FΣ (X) with |r| < |p2 | such that p1 (r) ∈ Q.
′
Proof. Set R = {r ∈ FΣ (X) | p1 (r) ∈ T , |r| ≤ |p2 |, ar n ⇒∗ s, a′ r n ⇒∗ s′ for some
′
s ∈ FΩ (Y )n and s′ ∈ FΩ (Y )n }. Obviously, R is nonvoid. Denote by r an element from
R with minimal length. We prove that p1 (r) ∈ Q and hg(r) < |pA|2 |B|.
First assume that hg(r) ≥ |pA|2 |B|. Then there are
that
(I) r = r1 r2 (r3 ) , r2 6= ξ1 ,
′ ′
(II) ar1n ⇒∗ s1 (b1 ξ1m1 ), a′ r1n ⇒∗ s′1 (b′1 ξ m1 ),
m′1 m′
(III) b1 r2m1 ⇒∗ s2 (b2 ξ1m2 ), b′1 r2 ⇒∗ s′2 (b′2 ξ1 2 ),
m′2
(IV) b2 r3m2 ⇒∗ s3 , b′2 r3 ⇒∗ s′3 ,
Take two mappings f : {1, . . . , m1 } → {1, . . . , m2 } and g : {1, . . . , m′1 } → {1, . . . , m′2 }
such that b1i = b2f (i) (1 ≤ i ≤ m1 ) and b′1i = b′2g (i) (1 ≤ i ≤ m′1 ). Obviously,
′
atn ⇒∗ s1 (s3f (1) , . . . , s3f (m1 ) ) and a′ tn ⇒∗ s′1 (s′3g(1) , . . . , s′3 ), where t = r1 (r3 ). More-
g(m′ )
1
over, r1 (r3 )β̂ = r β̂ also holds. Therefore, r1 (r3 ) ∈ R, which is a contradiction since
|r1 (r3 )| < |r|.
Thus, we got that hg(r) < |pA|2 |B|. Therefore, for arbitrary vectors s ∈ FΩ (Y )n and
′ ′
s′ ∈ FΩ (Y )n satisfying ar n ⇒∗ s and a′ r n ⇒∗ s′ , the inequalities hg(s1 ), hg(s′1 ) ≤
|pA|2 |B|K hold. This, by (iv), obviously implies the conclusion of Lemma 4.9.3. ✷
194
4.9 The equivalence of tree transducers
n′ n′
(iv) a2 pn3 2 ⇒∗ q3 (a3 ξ1n3 ), a′2 p3 2 ⇒∗ q′3 (a′3 ξ1 3 ),
ap3 ⇒∗ aξ1 , b2 pm ∗
3 ⇒ r3 (b3 ξ1 ),
2 m3
n′
(v) a3 pn4 3 ⇒∗ q4 , a′3 p4 3 ⇒∗ q′4 , ap4 ⇒∗ r, b3 pm ∗
4 ⇒ r4 ,
3
(vi) p4 β̂ = p3 (p4 )β̂ = p2 p3 (p4 ) β̂, A1 ⊆ A2 ⊆ A3 ,
A′1 ⊆ A′2 ⊆ A′3 , B1 = B2 ⊆ B3 ,
such that
aij = ai+1fi (j) (i = 1, 2, 1 ≤ j ≤ ni ) a′ij = a′i+1g (j) (i = 1, 2, 1 ≤ j ≤ n′i ),
i
bij = bi+1hi (j) (i = 1, 2, 1 ≤ j ≤ mi ).
195
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
n′ n′
(iv) a2 pn3 2 ⇒∗ q3 (a3 ξ1n3 ), a′2 p3 2 ⇒∗ q′3 (a′3 ξ1 3 ), b2 pm ∗ m3
3 ⇒ r3 (b3 ξ1 ),
2
196
4.9 The equivalence of tree transducers
n′
(v) a3 pn4 3 ⇒∗ q4 , a′3 p4 3 ⇒∗ q′4 , b3 pm ∗
4 ⇒ r4 ,
3
(vi) p4 β̂ = p3 (p4 )β̂ = p2 p3 (p4 ) β̂,
A1 ⊆ A2 ⊆ A3 , A′1 ⊆ A′2 ⊆ A′3 , B1 = B2 ⊆ B3 ,
p1 , p2 ∈ F̂Σ (X ∪ Ξ1 ), p3 ∈ FΣ (X), k, l, m, k′ , l′ , m′ ≥ 0,
q1 ∈ F̂Ω (Y ∪ Ξk+1 ), q1′ ∈ F̂Ω (Y ∪ Ξk′ +1 ), q2 ∈ F̂Ω (Y ∪ Ξl+1 ), q2′ ∈ F̂Ω (Y ∪ Ξl′ +1 ),
′
r ∈ F̂Ωk (Y ∪ Ξm ), r′ ∈ F̂Ωk (Y ∪ Ξm′ ), q3 ∈ F̂Ω (Y ∪ Ξ1 ), q3′ , r ∈ FΩ (Y ),
′ ′
s ∈ FΩ (Y )l , s′ ∈ FΩ (Y )l , t ∈ FΩ (Y )m , t′ ∈ FΩ (Y )m , a0 , a′0 ∈ A′ , a, a′ ∈ A,
′ ′ ′
a ∈ Ak , a′ ∈ Ak , b ∈ Al , b′ ∈ Al , c ∈ Am and c′ ∈ Am .
Then p1 (p3 ) ∈ Q.
Proof. Introduce the notation d = (b, c), d′ = (b′ , c′ ), u = (s, t) and u′ = (s′ , t′ ).
Moreover, take two mappings f : {1, . . . , k} → {1, . . . , l + m} and g : {1, . . . , k ′ } →
{1, . . . , l′ + m′ } satisfying the equalities ai = df (i) (1 ≤ i ≤ k) and a′i = ug(i)
(1 ≤ i ≤ k′ ). Obviously, there are derivations a0 p1 (p3 ) ⇒∗ q1 q3 (r), uf (1) , . . . , uf (k) and
a′0 p1 (p3 ) ⇒∗ q1′ q3′ , u′g(1) , . . . , u′g(k′ ) . Moreover, p1 (p3 ) ∈ T . Since
path1 q1 (q3 (ξ1 ), uf (1) , . . . , uf (k) ) = path1 q1′ (ξ1 , u′g(1) , . . . , u′g(k′ ) )
197
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
and q3′ 6= r, q1 q3 (r), uf (1) , . . . , uf (k) ) 6= q1′ (q3′ , u′g(1) , . . . , u′g(k′ ) ). Hence, p1 (p3 ) ∈ Q. ✷
Now we are ready to state a theorem from which the main decidability results of this
section easily follow.
Proof. Let K denote the maximum of the heights of the right-hand sides of the pro-
ductions from P, kAk = 2|A| and let L be the number of all words over {1, . . . , rΣ } with
length at most kAk2 |B|K, where rΣ is the maximal m for which Σm 6= ∅. Moreover, let
k = kAk2 |A|2 |B|2L + 1, l = k + (2kAk3 |A||B|)(kAk2 |B|K + 1) and m = l + 2kAk3 |B|.
We shall show that Q is nonvoid iff it contains a tree with height less than m. The
case K = 0 being obvious, we assume that K 6= 0.
Let p be an element of Q with minimal length, and q, q ′ ∈ FΩ (Y ) trees such that
q 6= q ′ and (p, q), (p, q ′ ) ∈ τA . Assume that hg(p) ≥ m. Then there are a0 , a′0 ∈ A′ ,
p0 , . . . , pm ∈ F̂Σ (X ∪ Ξ1 ), pm+1 ∈ FΣ (X), ni , n′i ≥ 0 (i = 0, . . . , m), q0 ∈ F̂Ω (Y ∪ Ξn0 ),
n n′
q0′ ∈ F̂Ω (Y ∪ Ξn′0 ), qi ∈ F̂Ω i−1 (Y ∪ Ξni ), q′i ∈ F̂Ω i−1 (Y ∪ Ξn′i ) (i = 1, . . . , m), qm+1 ∈
′ ′
FΩ (Y )nm , q′m+1 ∈ FΩ (Y )nm , ai ∈ Ani , a′i ∈ Ani (i = 0, . . . , m) such that the following
conditions are satisfied:
(1) p = p0 p1 (. . . (pm+1 ) . . .) , pi 6= ξ1 (i = 1, . . . , m),
(2) q = q0 q1 (. . . (qm+1 ) . . .) , q ′ = q0′ q′1 (. . . (q′m+1 ) . . .) ,
n′
(3) a0 p0 ⇒∗ q0 (a0 ξ1n0 ), a′0 p0 ⇒∗ q0′ (a′0 ξ1 0 ),
n n′ n′
ai pni+1
i
⇒∗ qi+1 (ai+1 ξ1 i+1 ), a′i pi+1
i
⇒∗ q′i+1 (a′i+1 ξ1 i+1 )
n′
(i = 0, . . . , m − 1), am pnm+1
m
⇒∗ qm+1 , a′m pm+1
m
⇒∗ q′m+1 .
For i = 0, . . . , m, introduce the notations p̌ i = p 0 p 1 (. . . (p i ) . . .) , q̌i =
′ ′ ′ ′
q0 q1 (. . . (qi ) . . .) and q̌i= q0 (q1 (. . . (qi ) . . .) . Moreover, let p̂i = pi+1 . . . (pm+1 ) . . . ,
q̂i = qi+1 . . . (qm+1 ) . . . and q̂i′ = q′i+1 . . . (q′m+1 ) . . . (i = 0, . . . , m). Finally, set
Ai = {aij | 1 ≤ j ≤ ni } and A′i = {a′ij | 1 ≤ j ≤ n′i } (i = 0, . . . , m).
′
If q̌l (r) 6= q̌l′ (r′ ) holds for all r ∈ FΩ (Y )nl and r′ ∈ FΩ (Y )nl , then the fact that
m − l + 1 > |pA|2 |B| makes Lemma 4.9.2 applicable and hence there are i and j with
l ≤ i < j ≤ m such that p̌i (p̂j ) ∈ Q. This is obviously a contradiction since |p̌i (p̂j )| < |p|.
Thus, we may assume that at least one of nl and n′l , say nl , is greater than 0. Moreover,
it can also be supposed that there are an il (1 ≤ il ≤ nl ), an r ′ ∈ F̂Ω (Y ∪ Ξ1 ) and an
s′ ∈ FΩ (Y ) such that q ′ = r ′ (s′ ), path1 (r ′ ) = pathil (q̌l ) and s′ 6= q̂lil . Then for each
j < l, nj > 0. Now let ij (0 ≤ j < l, 1 ≤ ij ≤ nj ) be those uniquely determined integers
for which pathij (q̌j ) are initial segments of pathil (q̌l ). Without loss of generality, we may
assume that i0 = . . . = il = 1.
Now suppose that there exists no w ∈ {pathi (q̌l′ ) | 1 ≤ i ≤ n′l } such that path1 (q̌l ) is an
initial segment of w or w is an initial segment of path1 (q̌l ). Then for each i (l ≤ i ≤ m),
198
4.9 The equivalence of tree transducers
set
Bi = {aij | path1 (q̌l ) is an initial segment of pathj (q̌i )}
and
Ci = {aij | path1 (q̌l ) is not an initial segment of pathj (q̌i )}.
Since the cardinality of {l, . . . , m} is 2kAk3 |B|+1, there are i1 , i2 , i3 (l ≤ i1 < i2 < i3 ≤
m) such that the following conditions are satisfied: p̂i1 β̂ = p̂i2 β̂ = p̂i3 β̂, Bi1 = Bi2 ⊆ Bi3 ,
Ci1 ⊆ Ci2 ⊆ Ci3 and A′i1 ⊆ A′i2 ⊆ A′i3 . From this, by Lemma 4.9.5 we get that at least
one of the trees p̌i2 (p̂i3 ), p̌i1 (p̂i2 ) and p̌i1 (p̂i3 ) is in Q, which is again a contradiction.
Therefore, for an il (1 ≤ il ≤ n′l ), pathil (q̌l′ ) is an initial segment of path1 (q̌l ) or
path1 (q̌l ) is an initial segment of pathil (q̌l′ ). Let ij (0 ≤ j < l, 1 ≤ ij ≤ n′j ) be
those uniquely determined integers for which pathij (q̌j′ ) are initial segments of pathij (q̌l′ ).
Without loss of generality we may assume that i0 = . . . = il = 1. We can also assume
that path1 (q̌l ) is an initial segment of path1 (q̌l′ ).
Now let us distinguish the following two cases:
a) path1 (q̌k′ ) is an initial segmentof path1 (q̌l ). If in addition for some i (0 ≤ i ≤ k),
abs l(path1 (q̌i )) − l(path1 (q̌i′ )) > kAk2 |B|K then, by Lemma 4.9.3, there exists
an r ∈ FΩ (Y ) such that q̌i (r) ∈ Q and |r| < |p̂i |. (Here abs stands for absolute
value.) This obviously is a contradiction.
Therefore, for each i (0 ≤ i ≤ k),
abs l(path1 (q̌i )) − l(path1 (q̌i′ )) ≤ ||A||2 |B|K. Then, since the cardinality of
{1, . . . , k} is kAk2 |A|2 |B|2L + 1, for some integers i and j (1 ≤ i < j ≤ k),
we have:
(I) path1 (q̌i ) is an initial segment of path1 (q̌i′ ), path1 (q̌j ) is an initial segment of
path1 (q̌j′ ), path1 (q̌i′ )/path1 (q̌i ) = path1 (q̌j′ )/path1 (q̌j ), or
(II) path1 (q̌i′ ) is an initial segment of path1 (q̌i ), path1 (q̌j′ ) is an initial segment
of path1 (q̌j ), path1 (q̌i )/path1 (q̌i′ ) = path1 (q̌j )/path1 (q̌j′ ). (Here uv/u = v for
any two words u and v.) Moreover, p̂j β̂ = p̂i β̂, ai1 = aj1 , a′i1 = a′j1 , Bi ⊆ Bj
and Bi′ ⊆ Bj′ , where Bs = {ast | 2 ≤ t ≤ ns } and Bs′ = {a′st | 2 ≤ t ≤
n′s } (s = i, j). Then, by Lemma 4.9.6, p̌i (p̂j ) ∈ Q, which is a contradiction
since |p̌(p̂ij )| < |p|.
199
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
and
Cj = {a′jt | 1 ≤ t ≤ n′j , path1 (q̌i′1 ) is not an initial segment of path1 (q̌j′ )}.
Since the cardinality of {i1 , . . . , i2 } is 2kAk3 |A||B| + 1, there are integers j1 , j2 and
j3 (i1 ≤ j1 < j2 < j3 ≤ i2 ) such that p̂j1 β̂ = p̂j2 β̂ = p̂j3 β̂, aj11 = aj21 = aj31 ,
Aj1 ⊆ Aj2 ⊆ Aj3 , Bj1 = Bj2 ⊆ Bj3 and Cj1 ⊆ Cj2 ⊆ Cj3 , where Ajt = {ajts | 2 ≤
s ≤ njt } (t = 1, 2, 3). Therefore, by Lemma 4.9.4, at least one of the trees p̌j2 (p̂j3 ),
p̌j1 (p̂j2 ) and p̌j1 (p̂j3 ) is in Q which is again a contradiction. ✷
Now we are ready to prove
Proof. By Theorem 4.9.7, (i) is true. Moreover, (iii) and (iv) follow from (ii) since the
domain of an R-transformation is regular and, by Theorem 2.10.3, it is decidable for two
regular forests whether one of them contains the other one. Therefore, it is enough to
prove (ii).
We may assume that A ∩ B = ∅. Let us construct an R-transducer C =
(Σ, X, C, Ω, Y, P ′′ , C ′ ) with C = A ∪ B, C ′ = A′ ∪ B ′ and P ′′ = P ∪ P ′ . Obviously,
τC |T = τA |T ∪ τB|T . Thus τA |T ⊆ τB|T holds iff dom(τA ) ∩ T ⊆ dom(τB ) ∩ T and τC |T
is a partial mapping. ✷
200
4.9 The equivalence of tree transducers
We shall show that for all {a, a′ } ⊆ A and p ∈ FΣ (X) the equivalence
|τA(a) (p) ∪ τA(a′ ) (p)| > 1 ⇐⇒ |τA(a) (p) ∪ τA(a′ ) (p)| > 1 (1)
and
n′ n′ n′ n′ n′ n′
a′ σ ⇒A r′ (b1 1 ξ1 1 , . . . , bmm ξmm ), bi i pi i ⇒A r′i (i = 1, . . . , m),
where a, a′ , ai , bi ∈ A, i = 1, . . . , m, n1 + . . . + nm = n, n′1 + . . . + n′m = n′ ,
r ∈ F̂∆ (Y ∪ Ξn ), r ′ ∈ F̂∆ (Y ∪ Ξn′ ), r(r1 , . . . , rm ) = r and
r′ (r1 , . . . , rm ) = r ′ . Moreover, σ(a1 , . . . , am ), ar(ξ1n1 , . . . , ξm
nm ) ,
n′ n′
σ(b1 , . . . , bm ), a′ r ′ (ξ1 1 , . . . , ξmm ) ∈ P.
(I) There exists an i (1 ≤ i ≤ m) with ni > 0 and |τA(ai ) (pi )| > 1 or there exists a
j (1 ≤ j ≤ m) with n′j > 0 and |τA(bj ) (pj )| > 1. Then, by the induction hypothesis,
|τA(ai ) (pi )| > 1 or |τA(bj ) (pj )| > 1. Therefore, by the definition of P , |τA(a) (p)| > 1
or |τA(a′ ) (p)| > 1 also holds.
(II) Assume that there are no i and j satisfying (I). Then, ri1 = . . . = rini = ri
(1 ≤ i ≤ m) if ni > 0. For all such i, by τA(ai ) ⊆ τA(ai ) and the choice of D, we
have pi ⇒∗A ai ri . Moreover, again by the choice of D, if ni = 0 then also there
exists an ri ∈ F∆ (Y ) such that pi ⇒∗A ai ri holds. Thus, we have the derivation
p ⇒∗A ar. Using similar arguments, one can show that p ⇒∗A a′ r ′ is also valid.
Therefore, |τA(a) (p) ∪ τA(a′ ) (p)| > 1.
201
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
Proof. Obviously, (i) follows from Theorem 4.9.8 by Lemma 4.9.9. Moreover, (ii) im-
plies (iii) and (iv) since, by Theorem 4.1.10 (i), the domain of an F-transformation is
recognizable. Thus, it suffices to prove (ii).
Assume that A ∩ B = ∅, and construct the F-transducer
C = (Σ, X, C, Ω, Y, P ′′ , C ′ )
4.10 EXERCISES
1. Define generalized sequential machines as tree transducers when strings are inter-
preted as unary trees in the usual way.
3. Show that the classes LDF and LDR, and similarly the classes LN DF and
LN DR, are incomparable.
8. Show that F is not closed under composition with LNF-transformations from the
right.
202
4.10 Exercises
203
4 TREE TRANSDUCERS AND TREE TRANSFORMATIONS
24. For every F-transducer there is an equivalent totally defined F-transducer with a
single final state.
25. For every DF-transducer (DR-transducer) one can effectively give an equivalent
DF-transducer (DR-transducer) with a minimal number of states.
204
4.11 Notes and references
trees. Buda showed that the equivalence problem of sp-machines is solvable and that
this implies that the equivalence of certain program schemes is also decidable.
Engelfriet and Filè introduced a new type of tree transducer called macro tree trans-
ducer which is a combination of the R-transducer and the context-free tree grammar
(see Engelfriet [82]). They propose to use macro tree transducers to model attribute
grammars of D. E. Knuth (Math. Systems Theory 2 (1968), 127–145: Correction: ibid
5 (1971), 95–96). For tree transformations in terms of magmoids we refer the reader to
Arnold and Dauchet [13, 16], Dauchet [61, 62], and Lilin [159, 160].
Finally, we note that much of the category theoretic work mentioned in the Notes and
References of Chapter 2 deal with tree transductions.
205
Bibliography
We hope that most of the literature dealing with tree automata, tree grammars, forests,
tree transductions, or their applications (published by the end of 1982) is listed in this
bibliography. It also includes some more general works which devote at least a part to
our subject, as well as a few items on closely related topics. As to the latter category
the decision on inclusion or exclusion has sometimes been difficult. Of a paper published
more than once in almost identical form, just the more complete, or the more widely
available, version is mentioned. Preliminary reports and unpublished theses are not
included except for a few cases. Items published by the same author(s) in the same year
are distinguished for reference by a letter after the year. For some of the most often
recurring journals and proceedings we use the following abbreviations:
n. Ann. ACM STC = Proceedings of the nth Annual ACM Symposium on Theory of
Computing
n. Coll. Lille = Les Arbres en Algébre et en Programmation, nth Colloque du Lille,
Université de Lille I
IC = Information and Control
n. IEEE Symp. (n ≤ 15) = nth Annual Symposium on Switching and Automata Theory
n. IEEE Symp (n > 15) = nth Annual Symposium on Foundations of Computer Science
J. ACM = J. Assoc. Comput. Mach.
J. CSS = J. Comput. System Sci.
LN in CS = Lecture Notes in Computer Science (Springer-Verlag)
MST = Mathematical Systems Theory
S-C-C = Systems-Computers-Controls
[1] ADÁMEK, J. and TRNKOVÁ, V. (1981): Varietors and machines in a categry. – Al-
gebra Universalis 13 (1981), 89-132.
[3] ALAGIĆ, S. (1975a): Categorical theory of tree processing. – Category Theory Ap-
plied to Computation and Control (Proc. Symp., San Francisco, 1974), LN in CS
25 (1975), 65-72.
207
Bibliography
[7] ARBIB, M. A. and MANES, E. G. (1978): Tree transformations and the semantics of
loop-free programs. – Acta Cybernet. 4 (1978), 11-17.
[9] ARNOLD, A. (1977a): Rational sets of trees. – 2. Coll. Lille (1977), 20-28.
[12] ARNOLD, A. and DAUCHET, M. (1976a): Theorie des magmoides. – 1. Coll. Lille
(1976), 15-30.
[15] ARNOLD, A. and DAUCHET, M.(1976d): Un théorème de duplication pour les forêts
algébriques. – J. CSS 13 (1976), 223-244.
[19] ARNOLD, A. and DAUCHET, M. (1978b): Sur l’inversion des morphismes d’arbres.
– Automata, Languages and Programming (Fifth Coll., Udine 1978), LN in CS 62
(1978), 26-35.
[20] ARNOLD, A. and DAUCHET, M. (1978c): Une relation d’equivalence decidable sur la
classe des forêts reconnaissables. – MST 12 (1978), 103-128.
208
Bibliography
209
Bibliography
[37] BLOOM, S. L. and ELGOT, C. C. (1976): The existence and construction of free
iterative theories. – J. CSS 12 (1976), 305-318.
[42] BRAYER, J. M. and FU, K.-S. (1977): A note on the k-tail method of tree grammar
inference. – IEEE Trans. Systems Man Cybernetics SMC – 7 (1977), 293-300.
[43] BUDA, A. (1978a): The equivalence problem for sequential program machines. –
3. Coll. Lille (1978), 19-26.
[44] Buda, A.O. (1978b): Abstaktnye maxiny programm. – Akad. Nauk SSSR
Sib. otd., Vyqisl. centr, Preprint 108, Novosibirsk (1978).
[51] CATALANO, A., GNESI, S. and MONTANARI, U. (1978): Shortest path problems and
tree grammars: An algebraic framework. – Graph-grammars and their application
to computer science and biology (International workshop, Bad Honnef, 1978), LN
in CS 73 (1978), 167-179.
210
Bibliography
[54] COURCELLE, B. (1978): Frontiers of infinite trees, – 3. Coll. Lille (1978), 76-102.
[55] CRESPI REGHIZZI, S. and DELLA VIGNA, P. (1973): Approximation of phrase markers
by regular sets. – Automata, Languages and Programming (Proc. Coll., Rocquen-
court, 1972), North Holland, Amsterdam (1973), 367-376.
[60] DAMM, W. (1982): The IO- and OI-hierarchies. – Theor. Comput. Sci. 20 (1982),
95-207.
[63] DAUCHET, M. and MONGY, J. (1979a): Image de noyaux reconnaissables par diverses
classes de transformations. – 4. Coll. Lille (1979), 79-101.
[65] DONER, J. E. (1965): Decidability of the weak second-order theory of two successors.
– Notices Amer. Math. Soc. 12 (1965), Abstract 65T-468, 819.
[66] DONER, J. E. (1970): Tree acceptors and some of their applications. – J. CSS 4
(1970), 406-451.
211
Bibliography
[70] ELGOT, C. C. (1975): Monadic computation and iterative algebraic theories. – Logic
Colloquium ’73, Studies in Logic, Vol. 80 (Eds. M. E. Rose and J. C. Sheperdson),
North-Holland, Amsterdam (1975), 175-230.
[71] ELGOT, C. C., BLOOM, S. L. and TINDELL, R. (1978): On the algebraic structure of
rooted trees. – J. CSS 16 (1978), 362-399.
[74] ENGELFRIET, J. (1975a): Tree automata and tree grammars, – Lecture notes, DAIMI
FN-10, Inst. Math., Aarhus Univ., Aarhus (1975).
[76] ENGELFRIET, J. (1976a): Surface tree languages and parallel derivation trees. –
Theor. Comput, Sci. 2 (1976), 9-27.
[79] ENGELFRIET, J. (1977): Macro grammars, Lindenmayer systems and other copying
devices. – Automata, Languages and Programming (Proc. Coll., Turku, 1977), LN
in CS 52 (1977), 221-229.
[81] ENGELFRIET, J. (1978b): On tree transducers for partial functions. – Inform. Pro-
cess. Lett. 7 (1978), 170-172.
[82] ENGELFRIET, J. (1980): Some open questions and recent results on tree transducers
and tree languages. – Formal language theory. Perspectives and open problems (ed.
R. V. Book), Academic Press, New York (1980), 241-286.
212
Bibliography
[84] ENGELFRIET, J., ROZENBERG, G. and SLUTZKI, G. (1980): Tree transducers, L sys-
tems, and two way machines. – J. CSS 20 (1980), 150-202.
[87] ENGELFRIET, J. and SKYUM, S. (1982): The copying power of one-state tree trans-
ducers. – J. CSS 25 (1982), 418-435.
[90] ÉSIK, Z. (1980): Decidability results concerning tree transducers I. – Acta Cybernet.
5 (1980). 1-20.
[96] FU, K.-S. (1980): Picture syntax. – Pictorial Information Systems (Eds, S. K. Chang
and K.-S. Fu), LN in CS 80 (1980), 104-127.
[97] FU, K.-S. (1982): Syntactic pattern recognition and applications. – Prentice-Hall,
Englewood Cliffs, N. J. (1982).
[98] FU, K.-S. and BHARKAVA, B. K. (1973): Tree systems for syntactic pattern recog-
nition. – IEEE Trans. Computers C-22 (1973), 1087-1099.
213
Bibliography
[99] FU, K.-S. and FAN, T.-I. (1982): Tree translation and its application to a time-
varying image analysis problem. – IEEE Trans. Systems, Man and Cybernetics,
SMC – 12 (1982), 856-867.
[103] GÉCSEG, F. and HORVÁTH, GY. (1976): On representation of trees and context-free
languages by tree automata. – Found. Control Engrg, 1 (1976), 161-168.
[104] GÉCSEG, F. and STEINBY, M. (1978a): Minimal ascending tree automata. – Acta
Cybernet. 4 (1978), 37-44.
[106] GÉCSEG, F. and E.-TÓTH, P. (1977): Algebra and logic in theoretical computer sci-
ence. – Mathematical Foundations of Computer Science, 1977 (Tatranska Lomnica),
LN in CS 53 (1977), 78-92.
[108] GINALI, S. (1979): Regular trees and the free iterative theory. – J. CSS 18 (1979),
228-242.
[109] GINSBURG, G. and MAYER, O. (1982): Tree acceptors and grammar forms. – Com-
puting 29 (1982), 1-9.
[111] GIVE’ON, Y. and ARBIB, M. A. (1968): Algebra automata II: the categorical frame-
work for dynamic analysis. – IC 12 (1968), 346-370.
214
Bibliography
215
Bibliography
[130] ITO, H., INAGAKI, Y. and FUKUMURA, T. (1973b): Scattered tree automata and
scattered context-sensitive tree-generating systems. – S-C-C 4 (1973), No.4, 22-28.
[131] ITO, H., INAGAKI, Y. and FUKUMURA, T. (1973c): Hierarchy of the families of
dendrolanguages. – S-C-C 4 (1973), No. 5, 48-56.
[132] ITO, H., INAGAKI, Y. and FUKUMURA, T. (1974): Dendrolanguage generating sys-
tems on control state sets. A hierarchy between context-free and context-sensitive
dendrolanguages, – S-C-C 5 (1974), No. 5, 1-8.
[135] JOSHI, A. K., LEVY, L. S. and TAKAHASHI, M. (1973): A tree generating system.
– Automata, Languages and Programming (Proc. Symp., Rocquencourt, 1972),
North-Holland, Amsterdam (1973), 453-465.
[136] JOSHI, A. K., LEVY, L. S. and TAKAHASHI, M. (1975): Tree adjunct grammars. –
J. CSS 10 (1975), 136-163.
[137] JOSHI, A. K., LEVY, L. S. and YUEH, K. (1980): Local constraints in programming
languages. Part I: Syntax. – Theoret. Comput. Sci. 12 (1980), 265-280.
[138] KAMIMURA, T. and SLUTZKI, G. (1979): DAGs and Chomsky hierarchy (extended
abstract). – Automata, languages and programming, (6th Colloq., Graz 1979), LN
in CS 71 (1979), 331-337.
[139] KAMIMURA, T. and SLUTZKI, G. (1982): Transductions of dags and trees. – MST
15 (1982), 225-249.
216
Bibliography
[142] KARPIŃSKI, M.(1975): Stretching by probabilistic tree automata and Santos gram-
mars. – Mathematical Foundations of Computer Science (Proc. Symp., Jadwisin
1974), LN in CS 28 (1975), 249-255.
[143] KARPIŃSKI, M. (1977): The equivalence problems for binary EOL-systems are
decidable. Fundamentals of Computation Theory (Proc, Symp., Poznań-Kórnik,
1977), LN in CS 56 (1977), 423-434.
[144] KAWAHARA, Y. (1980): Relational tree automata and context-free sets. – Bull.
Kyushu Inst. Technol., Math. Nat. Sci. 27 (1980), 17-25.
[145] KAWAHARA, Y. and YAMAGUCHI, M. (1980): Minimal realization theory for free
process machines in monoidal categories. – Mem. Fac. Sci. Kyushu Univ. Ser. A. 34
(1980), No. 1, 71-78.
[148] KOZEN, D. (1977): Complexity of finitely presented algebras. – 9. Ann. ACM STC
(Boulder, Co1. 1977), 164-177.
[152] LEVINE, B. (1981): Derivatives of tree sets with applications to grammatical infer-
ence. – IEEE Trans. Pattern Anal. & Mach. Intell., PAMI-3 (1981), 285-293.
[153] LEVINE, B. (1982): The use of tree derivatives and a sample support parameter for
inferring tree systems. – IEEE Trans. Pattern Anal. Mach. Intell., PAMI-4 (1982),
25-34.
[154] LEVY, L. S. (1971): Tree adjunct, parenthesis, and distributed adjunct grammars.
– Theory of machines and computations (Eds. Z. Kohavi and A. Paz), Academic
Press, New York (1971), 127-142.
217
Bibliography
[156] LEVY, L. S. (1980): Discrete structures of computer science. – John Wiley & Sons,
New York (1980).
[157] LEVY, L. S. and JOSHI, A. K. (1973): Some results in tree automata. – MST 6
(1973), 334-342.
[160] LILIN, E. (1978b): Une generalization des transducteurs d’etats finis d’arbres: les
S-transducteurs. – Thése de doctorat, Université de Lille I (1978).
[161] LILIN, E. (1981): Transducteurs finis d’arbres et tests d’egalite. – RAIRO Inform.
Theor. 15 (1981), 213-232.
[163] LU, S. Y. (1979a): Stochastic tree grammar inference for texture synthesis and
discrimination. – Comput. Graphics and Image Process. 9 (1979), 234-245.
[164] LU, S. Y. (1979b): A tree-to-tree distance and its application to cluster analysis.
– IEEE Trans. Pattern. Anal. & Mach. Intell., PAMI-1 (1979), 219-224.
[165] LU, S.Y.and FU, K.-S. (1978): Error-correcting tree automata for syntactic pattern
recognition. IEEE Trans. Comput, C-27 (1978), 1040-1053.
[166] MAGIDOR, M. and MORAN, G. (1969): Finite automata over finite trees. – Technical
Report 30, Hebrew University, Jerusalem (1969).
218
Bibliography
219
Bibliography
[189] NIVAT, M. (1973): Langages algébriques sur le magma libre et sémantique des
schémas de programme. – Automata, Languages and Programming (Proc. Symp.,
Rocquencourt 1972), North-Holland, Amsterdam (1973), 367-376.
[191] OPP, M. (1975a): Eine Beschreibung contextfreier Sprachen durch endliche Men-
gensysteme. Automata Theory and Formal Languages (2nd GI Conf., Kaiserslautern
1975), LN in CS 33 (1975), 190-197.
[194] PAIR, C. (1976a): Inference for regular bilanguages. – Formal Languages and Pro-
gramming (Proc. Semin., Madrid 1975), North-Holland, Amsterdam (1976), 15-30.
[195] PAIR, C. (1976b): Les arbres en theorie des langages. – 1. Coll. Lille (1976),196-216.
[196] PAIR, C. and QUERE, A. (1968): Definition et étude des bilangages réguliers, – IC
13 (1968), 565-593.
[199] PETROV, S. V. (1978): Graph grammars and automata (survey). – Autom. Remote
Control 39 (1978), 1034-1050.
220
Bibliography
[205] RABIN, M. O. (1970): Weakly definable relations and special automata. – Mathe-
matical Logic and Foundations of Set Theory (Proc. Coll., Jerusalem 1968), North-
Holland, Amsterdam (1970), 1-23.
[206] RAOULT J.-C. (1981): Finiteness results on rewritting systems. – RAIRO Inform.
Théor, 15 (1981), 373-391.
[208] RÉVÉSZ, Gy. (1977): Algebraic properties of derivation words. – 2. Coll. Lille
(1977), 224-234.
221
Bibliography
[220] SHEPARD, C. D. (1969): Languages in general algebras. – 1. Ann. ACM STC (1969),
155-163.
[221] SHI, Q.-Y. and FU, K.-S. (1982): Efficient error-correcting parsing for (attributed
and stochastic) tree grammars. – Information Sciences 26 (1982), 159-188.
[222] SIEFKES, D. (1978): An axiom system for the weak monadic second-order theory
of two successors. – Israel J. Math. 30 (1978), 264-284.
[225] STEINBY, M.(1977b): On the structure and realizations of tree automata. – 2. Coll.
Lille (1977), 235-248.
[226] STEINBY, M. (1979): Syntactic algebras and varieties of recognizable sets. – 4. Coll.
Lille (1979), 226-240.
[228] STEYART, J.-M. (1977a): Sur les index rationelles des feuillages de forêts lineaires.
– C. R. Acad. Sci. Paris, Sér, A, t. 285 (1977), 473-476.
[229] STEYART, J.-M. (1977b): Evaluation des index rationnels de quelques familles de
langages. – Technical Report No. 261, IRIA, Rocquencourt, France (1977).
[230] STEYART, J.-M. (1978): Index rationnel des ETOL-Jangages. – 3. Coll. Lille (1978),
246-249.
[232] TAI, K.-CH. (1979): The tree-to-tree correction problem. – J. ACM 26 (1979),
422-433.
222
Bibliography
[242] TIURYN, J. (1977a, b): Fixed-points and algebras with infinitely long expressions.
I – Mathematical Foundations of Computer Science 1977 (Proc. Symp., Tatran-
ska Lomnica), LN in CS 53 (1977), 513-522.
II – Fundamentals of Computation Theory (Proc. Symp., Poznań-Kórnik 1977),
LN in CS 56 (1977), 332-339.
[243] TOKURA, N. and KASAMI, T. (1974): Automata with labelled tree inputs. – S-C-C 5
(1974), No. 3, 88-95.
223
Bibliography
[253] YEH, R. T. (1971): Some structural properties of generalized automata and alge-
bras. – MST 5 (1971), 306-318.
[254] ZACHAR, Z. (1979): The solvability of the equivalence problem for deterministic
frontier-to-root tree transducers. – Acta Cybernet. 4 (1979), 167-177.
224
Index
Algebra, 11 upper, 24
Boolean, 11 branch of tree, 49
clone, 115
finite, 11 chain, 24
finite ND, 55 Chomsky hierarchy, 35
finitely generated, 12 class
free, 20 congruence, 13
freely generated over a class, 20 equivalence, 7
ND, 55 of tree transformations closed under
NDR, 57 composition, 147
nondeterministic, 55 of tree transformations preserving
nondeterministic root-to-frontier, 57 regularity, 165
of finite type, 11 closure
power, 16 of forest, 104
quotient, 14 x-substitution, 124
ΣX-term, 20 comparable elements, 24
subset, 16 compatible partition, 13
substitution, 115 complete sublattice, 25
trivial, 11 complete variety, 129
universal, 10 composition of
alphabet, 27 mappings, 8
frontier, 48 operations, 10
ranked, 48 relations, 7
terminal, 36 tree transformations, 131
arity of congruence
operation, 9 of DR ΣX-recognizer, 107
operator, 11 of recognizer, 33
associated ΣX-recognizers, 58 of Σ-algebra, 13
of ΣX-recognizer, 80
bijection, 8 right, 31
binoid, 114 syntactic, 32
bound connected component of DR ΣX-
greatest lower, 24 recognizer, 108
least upper, 24 connected part of recognizer, 34
lower, 24 converse of relation, 6
225
Index
226
Index
227
Index
228
Index
229
Index
230
Index
231
Index
yield of
forest, 117
tree, 117
z-product, 65
0-state, 104
232
5 APPENDIX
SOME FURTHER TOPICS AND REFERENCES
by Magnus Steinby
The purpose of this Appendix is to supplement the original book with notes on some
further topics and a selection of more recent references. The choice of topics and ref-
erences is partly influenced by personal preferences, but I trust that the areas included
deserve to be mentioned, and that the general expositions, surveys and research papers
appearing in the bibliography are useful. Hence, I hope that these notes may serve as
an initial guide to the subjects discussed, and that they give an idea of the continuing
vitality of the theory and of its applications.
Before considering any specific areas, let me note some works of a general nature
published after Tree Automata was written. J. R. Büchi’s posthumous book Finite Au-
tomata, Their Algebras and Grammars [11] appeared in 1989 (edited by D. Siefkes).
The main part of it treats unary algebras, finite acceptors, regular languages and pro-
duction systems, but in a manner that suggests tree automata and tree languages as
natural generalizations. The last two chapters deal with terms, trees, algebras as tree
automata, tree grammars, and connections between context-free languages and push-
down automata. Especially this latter part of the book appears quite unfinished, but
the author’s grand design, a theory that would encompass algebras, automata, formal
languages and rewriting systems, is clearly discernible. The terminology and notation
is often nonstandard, sometimes even confusing, but a patient reader is rewarded by
original insights and interesting historical remarks.
The book Tree Automata and Languages [66] edited M. Nivat and A. Podelski, which
appeared in 1992, is a collection of papers that discuss a variety of topics involving trees.
The survey paper [46] by F. Gécseg and M. Steinby may be viewed as a condensed and
somewhat modernized version of Tree Automata, but it also takes up some further topics
and its bibliography includes many additional items.
In their book Syntax-Directed Semantics. Formal Models Based on Tree Transducers
[44], Z. Fülöp and H. Vogler consider formal models of syntax-directed semantics based
on tree transducers. They also develop a fair amount of the general theory of total
deterministic top-down, macro, attributed, and macro attributed tree transducers. In
particular, they compare with each other the classes of tree transformations defined
by the different types of tree transducers, and they present several composition and
decomposition results for these tree transformations.
The internet book Tree Automata Techniques and Applications [13], to be referred to
as TATA, is a joint enterprise of several authors. First launched in 1997, it has already
233
5 APPENDIX
been revised and extended a few times. The presentation is often rather informal, but
the ideas are richly illustrated by examples and many interesting facts are also given as
exercises. The first two chapters review some basic material about finite tree recognizers,
regular tree languages, and regular tree grammars, but also mention context-free tree
languages. Chapter 6 contains a brief account of tree transducers (without proofs). The
remaining five chapters deal with topics not covered by our book. The tutorial [55] by
C. Löding focuses on applications of tree automata and emphasizes algorithmic aspects.
Automata on infinite trees and the connections between tree automata and logic were
the most important topics excluded from Tree Automata. The two are strongly linked
with each other and have been studied intensively ever since tree automata were intro-
duced, and by now they form an extensive theory with important applications to logic
and computer science. Although mainly concerned with the word case, the survey pa-
pers [81] and [82] by W. Thomas offer very readable introductions to this area, and they
also include extensive bibliographies. Chapter 3 of TATA [13] is a further useful general
reference, and some of the papers in [66] deal with this topic. The book Automata,
Logics, and Infinite Games [50] edited by E. Grädel, Thomas and T. Wilke contains
twenty tutorial papers that form an excellent overview of the study of automata, logics
and games. About half of them concern trees and tree automata. Besides MSO logics,
they elucidate the uses and properties of various modal logics, fixed-point logics and
guarded logics, and demonstrate the usefulness of alternating tree automata.
The continual development of the theory of tree transformations is also largely driven
by applications, and tree transducers will be mentioned also in connection with some
the other themes to be discussed below. Here I shall note separately a few important
topics. The study of compositions of tree transformation classes initiated by B. S. Baker
(1973, 1979)1 and J. Engelfriet (1975) has been pursued further especially by Fülöp and
S. Vágvölgyi [40, 42, 43, 35]. In particular, they have considered semigroups of the com-
positions of some given tree transformation classes, and presented rewriting systems by
which the equality of two composition classes can be decided. They have also considered
some variants of Engelfriet’s (1977) important idea of regular look-ahead for top-down
tree transducers ([41], for example). Recently, Engelfriet, S. Maneth and H. Seidl [25]
have shown that in certain cases it can be decided whether a deterministic top-down
tree transducer with regular look-ahead is equivalent to a deterministic top-down tree
transducer, and that such a transducer without look-ahead can be constructed if the
answer is positive. Macro tree transducers were first defined by Engelfriet (1980) but, as
noted in [44] for example, the primitive recursive program schemes independently intro-
duced by B. Courcelle and P. Franchi-Zannettacci [14] amount to many-sorted versions
of them. Macro and other higher-level tree transducers have been studied in depth by
Engelfriet and Vogler [26, 27, 28, 29] (cf. also [21, 22]). For further information about
these matters, I recommend the bibliographic notes in [44]. The work [8] on equational
tree transformations by S. Bozapalidis, Fülöp and G. Rahonis is a natural extension of
a classical theme.
The decidability of the question whether the image of a given regular tree language
1
The references can be found in the original bibliography of Tree Automata
234
under a given tree homomorphism is regular, has been a relatively long-standing open
problem, but recently an affirmative solution was presented by G. Godoy and O. Giménez
[48]. Their approach uses tree automata with equality or disequality tests, and their work
contains also some results of independent interest concerning such automata. Moreover,
it has some applications to term rewriting and XML theory. Fülöp and P. Gyenizse [37]
have shown that injectivity is undecidable for tree homomorphisms while it is decidable
for linear deterministic top-down tree transformations. Furthermore, in [36] Fülöp proves
that several questions concerning the ranges of deterministic top-down tree transforma-
tions are undecidable. The decidability of the equivalence of deterministic top-down tree
transducers was proved by Ésik already in 1980. More recently, Engelfriet, Maneth and
Seidl [24] showed that the equivalence of total deterministic top-down tree transducers
can be decided in polynomial time by reducing the transducers to a certain canonical
form, and their method can be applied also to deterministic top-down tree transducers
with regular look-ahead. In [34], S. Friese, Seidl and Maneth present a corresponding
equivalence checking algorithm based on normal forms for bottom-up tree transducers.
In [23], Engelfriet and Maneth prove that the equivalence of deterministic MSO tree
transducers is decidable. These results, as well as many other decidability questions for
tree transducers are discussed in the recent survey paper [58] by Maneth. Finally, two
quite recent contributions should be mentioned. Firstly, Seidl, Maneth and G. Kemper
[78] prove the decidability of the equivalence of deterministic top-down tree-to-string
transducers. In [33], E. Filiot, Maneth, P.-A. Reynier and J.-M. Talbot introduce tree
transducers for which every output tree is augmented with information about the origin
of each of its nodes, and prove several decidability results concerning the equivalence or
injectivity of such transducers.
Since terms can be seen as syntactic representations of trees over ranked alphabets,
it is to be expected that there are some connections between tree automata and term
rewriting systems (TRSs). Indeed, various tree automata and tree grammars are often
defined as special term rewriting systems. On the other hand, tree automata can be
used for solving problems concerning TRSs and such applications have, in turn, inspired
new developments in the theory tree automata. In the mid-1980s it was noted that the
set Red(R) of terms reducible by a finite left-linear TRS R, as well as its complement,
the set Irr(R) of irreducible terms, are regular tree languages. Since this means that
many questions concerning reducibility and normal forms are decidable for such TRSs,
the observation was quickly followed by several studies of related matters. Thus it
was shown that a finite TRS R for which Red(R) is regular can be “linearized” and
that the regularity of Red(R) is decidable, the regular sets Red(R) were characterized
in terms of a new class of finite tree automata, and questions of ground reducibility
were considered. So-called monadic and semi-monadic TRSs were studied using tree
pushdown automata. For extending such applications to TRSs that are not left-linear,
new classes of tree automata are needed. The problem here is that automata that are
able to recognize also non-regular sets Red(R) or the sets of all ground instances of
a given non-linear term, tend to be too powerful to be manageable themselves. An
example of increased power combined with good decidability properties is provided by
the automata with comparisons between brothers introduced in the 1990s. The ground
235
5 APPENDIX
tree transducer is another important tree automaton sprung from the theory of term
rewriting. Much material concerning these matters can be found in TATA [13], and
introductions to this subject and many references are provided also by the surveys [47],
[67] and [79]. For some recent work on this theme, cf. [83], for example.
Weighted tree automata, tree series and weighted tree transformations have been stud-
ied quite extensively in recent years. Most aspects of this work (up to around 2009) are
reviewed in the handbook chapter [45] by Fülöp and Vogler, and a broad introduction
is provided also by the survey paper [31] by Z. Ésik and W. Kuich. Weighted logics for
weighted tree automata have been studied by M. Droste, Vogler and others, cf. [18, 39],
for example. Equational weighted tree transformations are considered by Bozapalidis,
Fülöp and Rahonis [9]. In [71] Rahonis introduces weighted Muller-automata on infinite
trees and a corresponding weighted MSO-logic. The dissertation [61] of C. Mathissen
contains, among other matters, also much interesting material belonging to this area as
well as a useful bibliography.
In an unranked tree a node labeled with a given symbol may have any number of
children. Languages of such trees were considered already in the 1960s in two notable
papers. J. W. Thatcher (1967) introduced finite unranked tree recognizers and showed
that the yields of the recognizable unranked tree languages are precisely the context-free
languages. C. Pair and A. Quere (1968) created an algebraic framework for the study
of regular unranked tree languages that also incorporated hedges, i.e. finite sequences
of unranked trees, and they proved many of the usual properties of regular sets for
recognizable unranked tree languages. Nevertheless, the topic received little attention
before it was discovered that it is natural to represent XML documents by unranked
trees and that unranked tree automata may be useful for handling questions concerning
them. The revival of the theory of unranked tree and hedge languages by M. Murata et al.
[63, 64, 10] initiated a lively activity in the area. TATA [13] devotes a chapter to unranked
tree languages and their applications. As a sample from the extensive literature, let us
mention just the papers [15, 59, 60, 65] and the survey [77] by T. Schwentick. Since this
work is mostly quite application-oriented, algorithmic and complexity issues are much
to the fore. X. Piao and K. Salomaa [69, 70] have considered state complexity questions
connected with conversions between different types of unranked automata as well as
lower bounds for the size of unranked tree automata. An overview of logics for unranked
trees is given by L. Libkin [54]. Weighted unranked tree automata are studied in [19]
and [17] by Droste, Vogler, and D. Heusel.
Natural language description and processing has become an important area of applica-
tion of the theory of tree automata and tree languages. Of course, parse trees of natural
languages have always been prime examples of ‘trees’ and some of the early works on
tree automata explicitly refer to linguistic motivations, but the current activity took
really off much later. In his book [62] F. Morawietz discusses formalizations of natural
language syntax that are based on monadic second-order (MSO) logic on trees and tree
language theory. A key fact here is the effective correspondence between weak MSO logic
and finite tree automata established already by Thatcher and J. B. Wright (1965, 1968)
and J. Doner (1965, 1970), but actually a whole array of tree language-related notions
are utilized or noted as potentially useful. These include tree walking automata [4, 6, 7]
236
macro tree transducers [26, 21], and tree-adjoining grammars (cf. [51], for a survey).
Recently, the theory of tree automata has attracted the attention of linguists especially
because of the promise shown by tree-based approaches to machine translation. Besides
classical notions and results appearing already in our book, work in this area draws
also upon some newer developments. In particular, it has both utilized and inspired
work on unranked and weighted tree languages as well as weighted tree transducers.
Furthermore, it has revived the interest in the generalized top-down tree transducers
studied much earlier by E. Lilin (1978). Also compositions and decompositions of vari-
ous tree transformations are used in machine translation systems. The papers [52, 53]
expose some of the relevant questions from a linguist’s point of view, while the papers
[20, 49, 56, 57] form a sample of theoretical work in the area.
Almost all papers on varieties of tree languages, and classes of special regular tree
languages in general, have appeared after 1984. Most of the work in this area published
before 2005 is at least mentioned in the survey [80], and all the references pointed to
(by author and year) below can be found there. Eilenberg-like variety theories for tree
languages were presented by Steinby (1979, 1992, 1998) and J. Almeida (1990, 1995).
Ésik (1999) has set forth a variety theory in which finitary algebraic theories take the
place of finite algebras, and later he together with P. Weil [32] formulated a similar theory
in terms of preclones. Syntactic monoids of tree languages were introduced by Thomas
(1982, 1984) and studied further by Salomaa (1983). A similar notion for binary trees
has been used by Nivat and Podelski (1989, 1992). The families of regular tree languages
considered in the literature include those of the finite and co-finite tree languages (Gécseg
and B. Imreh 1988), definite, reverse definite and generalized definite tree languages
(U. Heuter 1989, 1992), k-testable tree languages (Heuter 1989, T. Knuutila 1992), and
aperiodic tree languages (Thomas 1984). All of them are varieties of tree languages (cf.
Steinby 1992, 1998), and in some cases the corresponding varieties of finite algebras are
also known.
Although Thomas (1984) could characterize the aperiodic tree languages by their syn-
tactic monoids, it was obvious that such a characterization is not possible for all varieties
of tree languages. This was confirmed when S. Salehi [72] described the (generalized) va-
rieties definable by syntactic monoids or semigroups. His result shows, for example, that
the definite tree languages cannot be characterized by syntactic semigroups (as claimed
in an earlier paper). However, in [12] A. Cano Gomez and Steinby introduce generalized
syntactic semigroups (and monoids) in terms of which the definite tree languages can
be characterized. Wilke (1996) gave an effective characterization of the reverse definite
binary tree languages in terms of so-called tree algebras. Salehi and Steinby [74] stud-
ied the tree algebra formalism in some detail and presented a variety theorem for it.
Noticing that the well-known equivalence of aperiodicity, star-freeness, and first-order
definability of string languages fails for trees, Thomas (1984) introduced logics in which
set quantifications are limited to chains or to antichains of nodes. He proved then, for
example, that a regular tree language is star-free iff it is antichain-definable. This line of
research has been pursued further by Heuter (1989, 1991) and A. Potthoff (1994, 1995),
for example.
Some families of tree languages have been introduced by first defining a class of finite
237
5 APPENDIX
algebras. For example, the monotone tree languages studied by Gécseg and Imreh (2002)
were defined as the languages recognized by monotone algebras. Similarly, Ésik and
Sz. Iván [30] introduce a hierarchy of aperiodicity notions for finite algebras and consider
then, besides the properties of the obtained varieties of finite algebras, the corresponding
families of tree languages. There are a few different extensions of the variety theory
of tree languages: positive varieties of tree languages by T. Petković and Salehi [68],
varieties of many sorted sets (with tree languages as a special case) by Salehi and Steinby
[73], and varieties of recognizable tree series by Fülöp and Steinby [38].
A section of Tree Automata is devoted to deterministic root-to-frontier (DR) recogniz-
ers and DR tree languages, but the topic has been studied quite extensively also later. In
her thesis E. Jurvanen (1995) considers closure properties and the variety generated by
DR tree languages as well as ways of strengthening DR recognizers. The latter include,
in particular, the regular frontier check mechanism introduced by Jurvanen, Potthoff and
Thomas (1994). The thesis is also a good general introduction and a reference for work
done before 1995. In the synchronized deterministic top-down automata of Salomaa
[75, 76] a limited communication between the computations in different branches is al-
lowed. Gécseg and Steinby (2001) introduced syntactic monoids for DR tree languages,
and these were used by Gécseg and Imreh (2002, 2004) for characterizing monotone,
nilpotent and definite DR tree languages. In [59] W. Martens, F. Neven and Schwentick
discuss several aspects of DR-recognition. In particular, motivated by applications to
schema languages for XML, they study DR recognizers of unranked tree languages.
The book Grammatical Picture Generation. A Tree-Based Approach [16] by F. Drewes
is a comprehensive treatment of tree-based picture generation. The picture generating
systems considered consist, roughly speaking, of a device for producing a tree language
and a picture algebra that interprets trees as pictures. The devices used for producing
the tree languages include regular tree grammars, ET0L tree grammars, branching tree
grammars, and tree transducers. The needed tree language theory is given in several
inserts in the main text and in a separate appendix. Thus this fascinating book offers
also a general introduction to tree languages.
A great number of concepts and results from several branches of mathematics are
used in the theory of tree automata. However, as a conclusion of this appendix, I shall
mention some introductions to just two subjects most intimately connected with tree
automata: universal algebra and term rewriting. Besides the texts listed at the end of
Chapter I of Tree Automata, there are several other good books on universal algebra. As
general introductions, I recommend the classic [5] by S. Burris and H. P. Sankappanavar
and the more recent textbook by C. Bergman [3]. The book [84] by W. Wechler, written
expressly for computer scientists, is also very useful. The books [1] by J. Avenhaus and
[2] by F. Baader and T. Nipkow offer two good introductions to term rewriting systems.
238
Bibliography of the Appendix
[1] AVENHAUS, J. (1995): Reduktionssysteme. Springer-Verlag, Berlin 1995.
[2] BAADER, F. and NIPKOW, T. (1998): Term Rewriting and All That. Cambridge
University Press, Cambridge, UK 1998.
[3] BERGMAN, C. (2012): Universal Algebra. Fundamentals and Selected Topics. CRC
Press, A Chapman & Hall Book, Boka Raton, Fl 2012.
[4] BLOEM, J. and ENGELFRIET, J. (1997): Monadic second order logic and node re-
lations on graphs and trees. – Structures in Logic and Computer Science (Eds.
J. Mycielski, G. Rozenberg and A. Salomaa), Lecture Notes in Computer Science
1261, Springer-Verlag, Berlin 1997, 144-161.
[5] BURRIS, B. and SANKAPPANAVAR, H.P. (1981): A Course in Universal Algebra.
Springer-Verlag, New York 1981.
[6] BOJANCZYK, M. and COLCOMBET, T. (2006): Tree-walking automata cannot be
determinized. Theoretical Computer Science 350 (2006), 164-173.
[7] BOJANCZYK, M. and COLCOMBET, T. (2008): Tree-walking automata do not recog-
nize all regular languages. SIAM Journal of Computing 38 (2008), 658-701.
[8] BOZAPALIDIS, S., FÜLÖP, Z. and RAHONIS, G. (2011): Equational tree transforma-
tions. Theoretical Computer Science 412 (2011), 3676-3692.
[9] BOZAPALIDIS, S., FÜLÖP, Z. and RAHONIS, G. (2012): Equational weighted tree
transformations. Acta Informatica 49 (2012), 29-52.
[10] BRÜGGEMANN-KLEIN, A., MURATA, M. and WOOD, D. (2001): Regular tree and reg-
ular hedge languages over unranked alphabets: Version 1, April 3, 2001. Technical
Report HKUST-TCSC-2001-05, The Hongkong University of Technology 2001.
[11] BÜCHI, J. R (1989): Finite Automata, Their Algebras and Grammars. Towards a
Theory of Formal Expressions (Ed. D. Siefkes), Springer-Verlag, New York 1989.
[12] CANO GOMEZ, A. and STEINBY, M. (2011): Generalized contexts and n-ary syntactic
semigroups of tree languages. Asian-European Journal of Mathematics 4 (2011), 49-
79.
[13] COMON, H., DAUCHET, M., GILLERON, R., JACQUEMARD, F., LUGIEZ, D., LÖDING, C.,
TISON, S. and TOMMASI, M. (2008): Tree Automata Techniques and Applications.
Available at http://tata.gforge.inria.fr.
239
Bibliography of the Appendix
[15] CRISTAU, J., LÖDING, C. and THOMAS, W. (2005): Deterministic automata on un-
ranked trees. – Foundations of Computation Theory, FCT 2005 (Eds. M. Liśkiewicz
and R. Reinschuk), Lecture Notes in Computer Science 3623, Springer-Verlag,
Berlin 2005, 68-79.
[17] DROSTE, M. and HEUSEL, D. (2015): The supports of weighted unranked tree au-
tomata. Fundamenta Informaticae 136 (2015), 37-58.
[18] DROSTE, M. and VOGLER, H. (2006): Weighted tree automata and weighted logics.
Theoretical Computer Science 366 (2006), 228-247.
[19] DROSTE, M. and VOGLER, H. (2011): Weighted logics for unranked tree automata.
Theory of Computing Systems 48 (2011), 23-47.
[20] ENGELFRIET, J., LILIN, E. and MALETTI, A. (2009): Extended multi bottom-up tree
transducers – Composition and decomposition. Acta Informatica 46 (2009), 561-590.
[21] ENGELFRIET, J. and MANETH, S. (1999): Macro tree transducers, attribute gram-
mars, MSO definable tree translations. Information and Computation 154 (1999),
34-91.
[22] ENGELFRIET, J. and MANETH, S. (2003): Macro tree translations of linear size are
MSO definable. SIAM Journal of Computing 32 (2003), 950-1006.
[23] ENGELFRIET, J. and MANETH, S. (2006): The equivalence problem for deterministic
MSO tree transducers is decidable. Information Processing Letters 100 (2006), 206-
212.
[24] ENGELFRIET, J., MANETH, S. and SEIDL, H. (2009): Deciding equivalence of top-
down XML transformations in polynomial time. Journal of Computer and Systems
Science 75 (2009), 271-286.
[25] ENGELFRIET, J., MANETH, S. and SEIDL, H. (2014): How to remove the look-ahead
of top-down tree transducers. – Developments in Language Theory, DLT 2014 (Eds.
A.M Shur and M.V. Volkov), Lecture Notes in Computer Science 8633, Springer
International Publishing Switzerland 2014, 103-115.
[26] ENGELFRIET, J. and VOGLER, H. (1985): Macro tree transducers. Journal of Com-
puter and Systems Science 31 (1985), 71-146.
[27] ENGELFRIET, J. and VOGLER, H. (1986): Pushdown machines for the macro tree
transducer. Theoretical Computer Science 42 (1986), 251-368.
240
Bibliography of the Appendix
[28] ENGELFRIET, J. and VOGLER, H. (1988): High level tree transducers and iterated
pushdown tree transducers. Acta Informaticae 26 (1988), 131-192.
[30] ÉSIK, Z. and IVÁN, Sz. (2007): Aperiodicity in tree automata. – Algebraic Infor-
matics CAI 2007 (Eds. S. Bozapalidis and G. Rahonis), Lecture Notes in Computer
Science 4782, Springer-Verlag, Berlin 2007, 189-207.
[31] ÉSIK, Z. and KUICH, W. (2003): Formal tree series. Journal of Automata, Languages
and Combinatorics 8(2) (2003), 219-285.
[32] ÉSIK, Z. and WEIL, P. (2005): Algebraic recognizability of tree languages. Theoret-
ical Computer Science 340 (2005), 291-321.
[33] FILIOT, E., MANETH, S., REYNIER, P.-A. and TALBOT, J.-M. (2015): Decision prob-
lems of tree transducers. – Automata, Languages, and Programming (Proc. 42nd
Intern. Coll. ICALP 2015, Kyoto, Japan, July 2015), Lecture Notes in Computer
Science 9135, Springer-Verlag, Berlin 2015, 209-221.
[34] FRIESE, S., SEIDL, H. and MANETH, S. (2011): Earliest normal form and mini-
mization for bottom-up tree transducers. International Journal of Foundations of
Computer Science 22 (2011), 1607-1623.
[38] FÜLÖP, Z. and STEINBY, M. (2011): Varieties of recognizable tree series over fields.
Theoretical Computer Science 412 (2011), 736-752.
[39] FÜLÖP, Z., STÜBER, T. and VOGLER, H (2012): A Büchi-like theorem for weighted
tree automata over multioperator monoids. Theory of Computation Systems 50
(2012), 241-278.
[41] FÜLÖP, Z. and VÁGVÖLGYI, S. (1989): Variants of top-down tree transducers with
look-ahead. Mathematical Systems Theory 21 (1989), 125-145.
[42] FÜLÖP, Z. and VÁGVÖLGYI, S. (1990): A complete rewriting system for a monoid
of tree transformation classes. Information and Computation 86 (1990), 195-212.
241
Bibliography of the Appendix
[45] FÜLÖP, Z. and VOGLER, H. (2009): Weighted tree automata and tree transducers.
– Handbook of Weighted Automata (Eds. M. Droste, W. Kuich and H. Vogler),
Springer-Verlag, Berlin 2009, 313-403.
[46] GÉCSEG, F. and STEINBY, M. (1997): Tree languages. – Handbook of Formal Lan-
guages, Vol. 3 (Eds. G. Rozenberg and A. Salomaa), Springer-Verlag, Berlin 1997,
1-68.
[47] GILLERON, R. and TISON, S. (1995): Regular tree languages and rewrite systems.
Fundamenta Informaticae 24 (1995), 157-175.
[48] GODOY, G. and GIMÉNEZ, O. (2013): The HOM problem is decidable. Journal of
the ACM 60(4) (2013), Article 23.
[49] GRAEHL, J., KNIGHT, K. and MAY, J. (2008): Training tree transducers. Computa-
tional Linguistics 34 (2008), 391-427.
[50] GRÄDEL, E, THOMAS, W. and WILKE, T. (Eds.) (2002): Automata, Logics, and
Infinite Games, Springer-Verlag, Berlin 2002.
[54] LIBKIN, L. (2006): Logics for unranked trees: an overview. Logical Methods in
Computer Science 2 (2006), 1-31.
[56] MALETTI, A. (2011a): Survey. Weighted top-down tree transducers. Part I – Basics
and expressive power. Acta Cybernetica 20 (2011), 223-250.
242
Bibliography of the Appendix
[58] MANETH, S. (2014): Equivalence problems for tree transducers: a brief survey. –
Automata and Formal Languages 2014, AFL 2014 (Eds. Z. Ésik and Z. Fülöp),
EPTCS 151, 2014, 74-93.
[60] MARTENS, W. and NIEHREN, J. (2007): On the minimization of XML Schemas and
tree automata for unranked trees. Journal of Computer and System Sciences 73
(2007), 550-583.
[61] MATHISSEN, C. (2009): Weighted Automata and Weighted Logics over Tree-like
Structures. Dissertation, Faculty of Mathematics and Informatics, University of
Leipzig, Leipzig 2009.
[64] MURATA, M. (2000): Hedge automata: A formal model for XML schemata. Fuji-
Xerox Information Systems, Japan 2000.
[65] NEVEN, F. (2002): Automata, logic, and XML. – Computer Science Logic (Proc.
16th Internat. Workshop, CSL 2002, Edinburgh, UK, 2002). Lecture Notes in Com-
puter Science 2471, Springer-Verlag, Berlin 2002, 2-26.
[66] NIVAT, M. and PODELSKI, A. (Eds.) (1992): Tree Automata and Languages, Studies
in Computer Science and Artificial Intelligence 10, North-Holland, Amsterdam 1992.
[67] OTTO, T. (1999): On the connections between rewriting and formal languages. –
Rewriting Techniques and Applications, RTA-99 (Proc. Conf., Trento, Italy, 1999),
Lecture Notes in Computer Science 1631, Springer-Verlag, Berlin 1999, 332-355.
[68] PETKOVIĆ, T. and SALEHI, S. (2005): Positive varieties of tree languages. Theoretical
Computer Science 347 (2005), 1-35.
[70] PIAO, X. and SALOMAA, K. (2012): Lower bounds for the size of deterministic
unranked tree automata. Theoretical Computer Science 454 (2012), 231-239.
243
Bibliography of the Appendix
[71] RAHONIS, G. (2007): Weighted Muller tree automata and weighted logics. Journal
of Automata, Languages and Combinatorics 12 (2007), 455-483.
[72] SALEHI, S. (2005): Varieties of tree languages definable by syntactic monoids. Acta
Cybernetica 17 (2005), 21-41.
[74] SALEHI, S. and STEINBY, M. (2007b): Tree algebras and varieties of tree languages.
Theoretical Computer Science 377 (2007), 1-24.
[77] SCHWENTICK, T. (2007): Automata for XML – A survey. Journal of Computer and
System Sciences 73 (2007), 289-315.
[78] SEIDL, H., MANETH, S. and KEMPER, G. (2015): Equivalence of deterministic top-
down tree-to-string transducers is decidale. arXiv: 1503.09163v [cs.FL] 31Mar2015.
[79] STEINBY, M. (2003): Tree automata in the theory of term rewriting. – Words,
Languages and Combinatorics III (Proc. Intern. Conf., Kyoto, Japan, 2000) (Eds.
M. Ito and T. Imaoka), World Scientific, New Jersey 2003, 434-449.
[82] THOMAS, W. (1997): Languages, automata, and logic. – Handbook of Formal Lan-
guages, Vol. 3 (Eds. G. Rozenberg and A. Salomaa), Springer-Verlag, Berlin 1997,
389-455.
244