Kudryavtsev V.B., Rosenberg I.G. Structural Theory of Automata, Semigroups, and Universal Algebra

Подождите немного. Документ загружается.

Algebraic classiﬁcations of regular tree languages 407

(1) K

(X)={T ⊆ T

(X) | SA(T ) ∈ K},and

(2) K

(X)={θ ∈ FCon

(X) |T

(X)/θ ∈ K}.

11.2 Lemma If K ∈ VFA(Σ),thenK

∈ VTL(Σ) and K

∈ VFC(Σ).

Proof The claim K

∈ VTL(Σ) follows by Proposition 8.7 when we use the fact that K

is a Σ-VFA. For example, if T ∈ K

(X), then p

−1

(T ) ∈ K

(X) for any p ∈ C

(X) because

SA(p

−1

(T )) / SA(T ) and SA(T ) ∈ K imply SA(p

−1

(T )) ∈ K.

To prove K

∈ VFC(Σ), consider any θ, ρ ∈ FCon

(X). If θ ⊆ ρ and θ ∈ K

(X),

then ρ ∈ K

(X) because T

(X)/ρ /T

(X)/θ ∈ K implies T

(X)/ρ ∈ K.Moreoverif

θ, ρ ∈ K

(X), then θ ∩ ρ ∈ K

(X) follows from T

(X)/θ ∩ ρ /T

(X)/θ ×T

(X)/ρ and

(X)/θ, T

(X)/ρ ∈ K. Because K

(X) contains at least the universal relation ∇

(X)

,this

meansthatitisaﬁlterinFCon

(X).

To verify that K

also satisﬁes the second condition of Deﬁnition 10.1, consider any

homomorphism ϕ : T

(X) →T

(Y ) and assume that θ ∈ K

(Y ). Let ρ = ϕ ◦ θ ◦ ϕ

−1

.Itis

easy to verify that t/ρ → tϕ/θ deﬁnes a monomorphism ψ : T

(X)/ρ →T

(Y )/θ. Because

(Y )/θ ∈ K, this implies that T

(X)/ρ ∈ K, and therefore ρ ∈ K

(X). 2

11.3 Deﬁnition For any family V of regular Σ-tree languages, let

({SA(T ) | T ∈V(X)forsomeX})

be the Σ-VFA generated by the syntactic algebras of the tree languages belonging to V,and

let V

be the family of ﬁnite Σ-congruences such that for any leaf alphabet X,

(X)=[{θ

| T ∈V(X)})

is the ﬁlter of FCon

(X) generated by the syntactic congruences of the members of V(X).

11.4 Lemma If V∈VTL(Σ),thenV

∈ VFA(Σ) and V

∈ VFC(Σ).

Proof As everything else is obvious, it suﬃces to prove that V

satisﬁes Condition (2) of

Deﬁnition 10.1. Let ϕ : T

(X) →T

(Y ) be a homomorphism and assume that θ ∈V

(Y ).

Then θ

∩···∩θ

⊆ θ for some T

,...,T

∈V(Y ). For each i =1,...,n,

ϕ ◦ θ

◦ϕ

−1



{θ

−1

)ϕ

−1

| p ∈ Tr(T

(Y ))}

by Lemma 8.8. Every set p

−1

)ϕ

−1

is in V(X)sinceV is a Σ-VTL, and by Proposition 6.7

the number of such sets is ﬁnite. Hence each ϕ ◦θ

◦ϕ

−1

is in V

(X), and therefore ϕ ◦θ

◦

−1

∈V

(X) as required. 2

Let us now introduce the remaining two transformations.

11.5 Deﬁnition For any family Γ of ﬁnite Σ-congruences, let

({T

(X)/θ | θ ∈ Γ(X)forsomeX}),

and let Γ

be the family of regular Σ-tree languages such that for any leaf alphabet X,

(X)={T ⊆ T

(X) | θ

∈ Γ(X)}.

408 M. Steinby

The ﬁrst assertion of the following lemma holds by deﬁnition, and the second assertion is

easily proved by using Proposition 8.6.

11.6 Lemma If Γ ∈ VFC(Σ),thenΓ

∈ VFA(Σ) and Γ

∈ VTL(Σ).

The following facts are completely obvious.

11.7 Lemma The six operations introduced above are isotone, that is to say

(1) for any K, L ∈ VFA(Σ), K ⊆ L implies K

⊆ L

and K

⊆ L

(2) for any U, V∈VTL(Σ), U⊆Vimplies U

⊆V

and U

⊆V

,and

(3) for any Γ, Φ ∈ VFC(Σ), Γ ⊆ Φ implies Γ

⊆ Φ

and Γ

⊆ Φ

To show that the six mappings considered above deﬁne isomorphisms between the lat-

tices (VTL(Σ), ⊆), (VFA(Σ), ⊆)and(VFC(Σ), ⊆), it suﬃces now to prove that they form

mutually inverse pairs. This is stated in the following lemma which we give without proof.

We compose the transformations in the natural way from left to right. For example, for any

Σ-VFA K, K

means (K

)

11.8 Lemma For any K ∈ VFA(Σ), V∈VTL(Σ) and Γ ∈ VFC(Σ),

(1) K

= K and K

= K,

(2) V

= V and V

= V,

(3) Γ

=Γand Γ

=Γ, and moreover

(4) K

= K

, K

= K

, V

= V

, V

= V

, Γ

=Γ

and Γ

=Γ

The results of the section can be summarized as the following Variety Theorem.

11.9 Theorem For any ranked alphabet Σ, the mappings

VFA(Σ) → VTL(Σ), K → K

; VTL(Σ) → VFA(Σ), V →V

the mappings

VFA(Σ) → VFC(Σ), K → K

; VFC(Σ) → VFA(Σ), Γ → Γ

and the mappings

VTL(Σ) → VFC(Σ), V →V

; VTL(Σ) → VFC(Σ), Γ → Γ

form three pairs of mutually inverse isomorphisms between the algebraic lattices (VFA(Σ), ⊆),

(VTL(Σ), ⊆) and (VFC(Σ), ⊆). Moreover, K

= K

, K

= K

, V

= V

, V

= V

=Γ

and Γ

=Γ

for all K ∈ VFA(Σ), V∈VTL(Σ) and Γ ∈ VFC(Σ).

Many well-known varieties of tree languages, as well as the associated varieties of ﬁnite

algebras and ﬁnite congruences, are actually unions of chains of subvarieties or, more gener-

ally, unions of directed families of subvarieties. Moreover, it is often natural to ﬁrst deﬁne

these subvarieties. Therefore, we note the following facts.

Algebraic classiﬁcations of regular tree languages 409

11.10 Proposition Let V =



i∈I

be the union of a directed family {V

| i ∈ I} of varieties

of Σ-tree languages. Then

(1) {V

| i ∈ I} is a directed family of Σ-VFAs such that



i∈I

= V

,and

(2) {V

| i ∈ I} is a directed family of Σ-VFCs such that



i∈I

= V

Proof The families {V

| i ∈ I} and {V

| i ∈ I} are directed because the maps U →U

and U →U

are isotone. Therefore K =



i∈I

is a Σ-VFA and Γ =



i∈I

is a Σ-VFC,

and it remains to be shown that K = V

and Γ = V

Of course, K ⊆V

since V

⊆V

for every i ∈ I. For the converse inclusion it suﬃces to

recall that V

is generated by syntactic algebras SA(T )withT ∈V(X)forsomeX. Indeed,

by the deﬁnition of V,anysuchT is in V

(X)forsomei ∈ I, and therefore SA(T ) ∈V

⊆ K.

The inclusion Γ ⊆V

is again obvious. If θ ∈V

(X)forsomeX,thenθ

∧···∧θ

⊆ θ,

where n ≥ 1andT

∈V

,...,T

∈V

for some i

,...,i

∈ I.NowV

,...,V

⊆V

for

some i ∈ I, and therefore θ ∈V

(X) ⊆ Γ(X). Hence also V

⊆ Γholds. 2

Let us just note without proofs the corresponding propositions for directed families of

Σ-VFAs and directed families of Σ-VFCs.

11.11 Proposition Let K =



i∈I

be the union of a directed family {K

| i ∈ I} of

varieties of ﬁnite Σ-algebras. Then

(1) {K

| i ∈ I} is a directed family of Σ-VTLs such that



i∈I

= K

,and

(2) {K

| i ∈ I} is a directed family of Σ-VFCs such that



i∈I

= K

11.12 Proposition Let Γ=



i∈I

be the union of a directed family {Γ

| i ∈ I} of varieties

of ﬁnite Σ-congruences. Then

(1) {Γ

| i ∈ I} is a directed family of Σ-VFAs such that



i∈I

=Γ

,and

(2) {Γ

| i ∈ I} is a directed family of Σ-VTLs such that



i∈I

=Γ

Often each subvariety V

(i ∈ I)formingaΣ-VTLV as in Proposition 11.10 is obtained

as follows. For every X, a ﬁnite congruence γ

(X) ∈ FCon

(X) is introduced and V

(X)is

deﬁned as the set of ΣX-tree languages saturated by γ

(X), and then the congruences γ

(X)

deﬁne a principal Σ-VFC Γ

= {[γ

(X))}

such that V

=Γ

. Moreover, in many cases the

congruences γ

(X) form, for any given X, a descending chain, and then {Γ

| i ∈ I} and

| i ∈ I} form, correspondingly, ascending chains.

Let us now note some special properties of the Σ-VTLs and Σ-VFAs that correspond to

principal Σ-VFCs.

11.13 Proposition Let Γ={[γ

)}

be a principal Σ-VFC. For any leaf alphabet X,let

:= T

(X)/γ

and

X := {¯x | x ∈ X},where¯x = x/γ

(a) For any X, Γ

(X) is the set of all ΣX-tree languages saturated by γ

(b) For any X and T ⊆ T

(X), T ∈ Γ

(X) if and only if SA(T ) is an epimorphic image

of F

410 M. Steinby

is freely generated by

X over Γ

(d) Γ

is the Σ-VFA generated by the algebras F

Proof For (a) it suﬃces to observe that for any T ∈ Rec

(X), T ∈ Γ

(X) if and only if

⊆ θ

, while γ

⊆ θ

if and only if γ

saturates T .

Let us now consider (b). If T ∈ Γ

(X), then γ

⊆ θ

implies immediately that SA(T )is

an image of F

. Assume now that there is an epimorphism ϕ: F

→ SA(T). For each x ∈ X

we may choose a term t

∈ T

(X) such that (t

/γ

)ϕ = x/T , and then the assignment x → t

can be extended to an endomorphism ψ : T

(X) →T

(X). Of course, ψγ



ϕ = ϕ

.Moreover,

if sγ

t for some s, t ∈ T

(X), then sψ γ

tψ since γ

is fully invariant by Corollary 10.6.

Hence, sγ

t implies s/T = sϕ

= sψγ



ϕ = tψγ



ϕ = tϕ

= t/T ,thatistosay,γ

⊆ θ

Since γ

is a fully invariant congruence on T

(X), F

is a free algebra. As the class of Σ-

algebras A =(A, Σ) for which any mapping ϕ

X → A can be extended to a homomorphism

ϕ : F

→Ais a variety (cf. [32, p. 165], for example), it suﬃces by (b) to verify that

the algebras F

belong to this class. Let Y be a leaf alphabet and consider any mapping

X → T

(Y )/γ

. Let us deﬁne a mapping ψ

: X → T

(Y ) by setting, for each x ∈ X,

xψ

= s

,wheres

is any ΣY -tree such that ¯xϕ

= s

/γ

.Ifψ : T

(X) →T

(Y )isthe

homomorphic extension of ψ

,then

ϕ : T

(X)/γ

→ T

(Y )/γ

,t/γ

→ tψ/γ

is the required extension of ϕ

to a homomorphism ϕ : F

→F

. Indeed,

(1) ϕ is well-deﬁned because γ

⊆ ψ ◦ γ

◦ψ

−1

(2) ϕ|

X = ϕ

as ¯xϕ = xψ/γ

= xψ

/γ

=¯xϕ

for every ¯x ∈

X,and

(3) a direct computation shows that ϕ is a homomorphism from F

to F

It remains to prove (d). By deﬁnition, Γ

is the Σ-VFA generated by the algebras

(X)/θ,whereX is any leaf alphabet and θ ∈ [γ

). However, γ

⊆ θ means that

(X)/θ /F

, and hence Γ

is already generated by the algebras F

. 2

Note that part (b) of Proposition 11.13 also means that every T ∈ Γ

(X) is recognized

by a ΣX-recognizer based on the algebra F

. Moreover, the proposition implies that the

Membership Problem “T (A) ∈ Γ

(X)?”, where A is any given ΣX-recognizer, is decidable

for any Σ-VTL deﬁned by a principal Σ-VFC Γ = {[γ

)}

assuming that the congruences

are eﬀectively given.

12 Examples of varieties

We shall now consider several natural families of regular tree languages that form varieties

and use them for illustrating the general notions and facts presented in the previous section.

Some further examples will be noted in the sections to follow.

12.1 Example The greatest Σ-VTL is the family Rec

= {Rec

(X)}

of all regular Σ-tree

languages—the required closure properties were noted in Section 6. That the corresponding

Σ-VFA is the class Fin

of all ﬁnite Σ-algebras follows from Lemma 9.4 and Proposition 8.14:

Algebraic classiﬁcations of regular tree languages 411

a Σ-VFA is generated by the syntactic algebras it contains and every ﬁnite syntactic Σ-algebra

is the syntactic algebra of some regular Σ-tree language. It is also clear that Rec

is the

family FCon

= {FCon

(X)}

of all ﬁnite Σ-congruences.

Since we excluded the variety of regular Σ-tree languages with empty components, the

least Σ-VTL is Triv

= {Triv

(X)}

,whereTriv

(X)={∅,T

(X)} for each X. Clearly,

Triv

is the class Triv

of all trivial Σ-algebras, and Triv

= {{∇

(X)

}}

The following notion of nilpotency of tree automata was introduced in [24]

12.2 Example Let us call a Σ-algebra A =(A, Σ) nilpotent if there is an element a

∈ A

and a number n ≥ 0 such that for any X,anyα : X → A and any t ∈ T

(X), if hg(t) ≥ n

then tα

= a

.LetNil

be the class of all ﬁnite nilpotent Σ-algebras. If A∈Nil

,the

element a

(obviously uniquely determined) and the smallest number n for which the above

condition is satisﬁed, are called, respectively, the absorbing state and the degree of nilpotency

of A. It is easy to see that Nil

is a Σ-VFA. In fact, for each n ≥ 0, the ﬁnite Σ-algebras with

degree of nilpotency ≤ n form a Σ-VFA Nil

Σ,n

,andNil

is the union of the ascending chain

Triv

= Nil

Σ,0

⊆ Nil

Σ,1

⊆ Nil

Σ,2

⊆ ... of such sub-Σ-VFAs. For example, let A =(A, Σ)

be in Nil

Σ,n

with absorbing state a

and let ϕ : A→Bbe an epimorphism onto a Σ-algebra

B =(B,Σ). Since ϕ is surjective, we may deﬁne for any β : X → B an α : X → A such

that xβ = xαϕ for every x ∈ X.Thentβ

= tα

ϕ for every t ∈ T

(X). In particular, if

hg(t) ≥ n,thentβ

= a

ϕ, and hence B∈Nil

Σ,n

with a

ϕ as the absorbing state.

As noted in [80], Nil

is the Σ-VTL Nil

= {Nil

(X)}

,whereforeachX,Nil

(X)is

the set of all ﬁnite ΣX-tree languages and their complements in T

(X) (the co-ﬁnite ΣX-tree

languages). For showing directly that Nil

isaΣ-VTL,itisusefultonotethathg(tϕ) ≥ hg(t)

for any tree t ∈ T

(X) and any homomorphism ϕ : T

(X) →T

(Y ), as this implies that

Tϕ

−1

is ﬁnite for every ﬁnite T ⊆ T

(Y ). A similar observation can be made about the

translations p : T

(X) → T

(X).

Let us consider the corresponding ﬁnite congruences. For each n ≥ 0 and any leaf alphabet

X,letν

Σ,n

(X) be the equivalence on T

(X) such that

(X)/ν

Σ,n

(X)={{t}|t ∈ T

(X)

}∪{T

(X)

≥n

Obviously, ν

Σ,n

(X) ∈ FCon

(X)and∇

(X)

= ν

Σ,0

(X) ⊇ ν

Σ,1

(X) ⊇ ν

Σ,2

(X) ⊇ ...,andthe

inclusions are proper whenever T

(X) is inﬁnite. It is also clear that Γ Nil

Σ,n

= {[ν

Σ,n

(X))}

is a principal Σ-VFC. Let Γ Nil

be the union of the ascending chain Γ Nil

Σ,0

⊆ ΓNil

Σ,1

⊆

ΓNil

Σ,2

⊆ ... of Σ-VFCs. Of course, Γ Nil

∈ VFC(Σ).

Clearly, a ΣX-tree language T is in Nil

(X) if and only if T is saturated by some ν

Σ,n

(X).

In fact, for any T ∈ Nil

(X)thereisaleastn ≥ 0 such that T is saturated by ν

Σ,k

(X)ifand

only if k ≥ n. For every n ≥ 0, let Nil

Σ,n

(X)bethesetofallΣX-tree languages saturated

by ν

Σ,n

(X). By Proposition 11.13, Nil

Σ,n

= {Nil

Σ,n

(X)}

is the Σ-VTL corresponding to

ΓNil

Σ,n

.Moreover,Nil

is the union of the chain Nil

Σ,0

⊆ Nil

Σ,1

⊆ Nil

Σ,2

⊆ ... and

Nil

=ΓNil

To complete the picture, we note that the chain Nil

Σ,0

⊆ Nil

Σ,1

⊆ ... matches the

chain Γ Nil

Σ,0

⊆ ΓNil

Σ,1

⊆ .... The quotient algebra N

Σ,n

(X):=T

(X)/ν

Σ,n

(X)isin

Nil

Σ,n

with the class T

(X)

≥n

as the absorbing state. It corresponds to the algebra F

Proposition 11.13. Hence, a ΣX-tree language T is in Nil

Σ,n

(X) if and only if SA(T )isan

image of N

Σ,n

(X), and N

Σ,n

(X) is freely generated by {x/ν

Σ,n

(X) | x ∈ X} over Nil

Σ,n

412 M. Steinby

For any given ΣX-recognizer A =(A,α,F), we may decide whether T (A) ∈ Nil

(X)by

using the correspondence between Nil

and Nil

. We may assume that A is minimal. Then

∼

SA(T(A)), and hence T (A) ∈ Nil

(X) if and only if A∈Nil

. The latter condition

can be tested directly. It is easy to see that if an n-element algebra is nilpotent, its degree of

nilpotency is ≤ n − 1. In [24] it is shown that an algebra A =(A, Σ) is nilpotent if and only

if the unary algebra (A, Tr(A)) is nilpotent, where the operations are the translations of A.

Recall that a string language L ⊆ X

∗

is deﬁnite [42, 56] if there is a k ≥ 0 such that for

any word w ∈ X

∗

of length ≥ k, w ∈ L if and only if the suﬃx of w of length k is in L.

Heuter [33, 35] was the ﬁrst to study deﬁnite tree languages, and we adopt her deﬁnition with

a minor modiﬁcation. That the deﬁnite Σ-tree languages form a variety of tree languages is

noted in [80]. Further relevant results can be found in [21].

12.3 Example As our tree recognizers read a tree in the direction from the leaves to the

root, we replace suﬃxes with root segments. The k-root root

(t)(k ≥ 0) of a ΣX-tree t is

deﬁned as follows:

(1) root

(t)= (the empty root segment) for every t ∈ T

(X).

(2) root

(t)=root(t) for every t ∈ T

(X).

(3) Let k ≥ 2. If hg(t) ≤ k,thenroot

(t)=t.Ifhg(t) >kand t = f (t

,...,t

), then

root

(t)=f(root

k−1

),...,root

k−1

)).

For example, if t = f (g(x),f(g(c),x)), then root

(t)=,root

(t)=f,root

(t)=f(g, f),

root

(t)=f(g(x),f(g, x)) and root

(t)=t for every k ≥ 4.

For any k ≥ 0andanyX,letδ

Σ,k

(X) be the equivalence on T

(X) deﬁned by

sδ

Σ,k

(X) t if and only if root

(s)=root

(t)(s, t ∈ T

(X)).

It is obvious that δ

Σ,k

(X)isinFCon

(X) with a congruence class corresponding to every

possible root segment root

(t). For any homomorphism ϕ : T

(X) →T

(Y ), any k ≥ 0and

any s, t ∈ T

(X), if root

(s)=root

(t) then clearly root

(sϕ)=root

(tϕ) also. This implies

by Proposition 10.5 that Γ Def

Σ,k

= {[δ

Σ,k

(X))}

is a principal Σ-VFC for each k =0, 1,...,

and hence Γ Def



k≥0

ΓDef

Σ,k

is a Σ-VFC.

For any k ≥ 0, a ΣX-tree language T is said to be k-deﬁnite if it is saturated by δ

Σ,k

(X),

that is to say, for any s, t ∈ T

(X), if root

(s)=root

(t), then s ∈ T if and only if t ∈ T .Let

Def

Σ,k

(X)denotethesetofk-deﬁnite ΣX-tree languages. It follows immediately from the

deﬁnition that Def

Σ,k

= {Def

Σ,k

(X)}

is the Σ-VTL corresponding to the Σ-VFC Γ Def

Σ,k

AΣX-tree language is deﬁnite if it is k-deﬁnite for some k ≥ 0. Let Def



k≥0

Def

Σ,k

the Σ-VTL of all deﬁnite Σ-tree languages. Of course, Def

=ΓDef

For each k ≥ 0, an algebra A =(A, Σ) is k-deﬁnite [21] if root

(s)=root

(t) implies

sα

= tα

for every leaf alphabet X,everyα : X → A and all s, t ∈ T

(X). Let Def

Σ,k

be the class of all ﬁnite k-deﬁnite Σ-algebras, and let Def



k≥0

Def

Σ,k

be the class of

all ﬁnite deﬁnite Σ-algebras. It is easy to verify directly that every Def

Σ,k

is a Σ-VFA, but

one can also show that Def

Σ,k

=ΓDef

Σ,k

by considering the quotient algebras D

Σ,k

(X):=

(X)/δ

Σ,k

(X). Indeed, it is clear that D

Σ,k

(X)isk-deﬁnite and that any k-deﬁnite Σ-

algebra with a generating set of size ≤|X| is an epimorphic image of D

Σ,k

(X). In fact,

Algebraic classiﬁcations of regular tree languages 413

Σ,k

(X) is generated freely over Def

Σ,k

by {x/δ

Σ,k

(X) | x ∈ X}. It follows from the results

of [33] that Def

Σ,k

is the Σ-VFA corresponding to Def

Σ,k

For any given k ≥ 0andX,thequestion“T (A) ∈ Def

Σ,k

(X)?” is again decidable for any

ΣX-recognizer A =(A,α,F); assuming that A is minimal, one has just to check whether

the algebra A is k-deﬁnite. On the other hand, it is not immediately clear that the question

“T (A) ∈ Def

(X)?” is decidable. However, Heuter [33, 34] has shown that if A has n states

and T (A) is deﬁnite, then T (A)is(n −1)-deﬁnite. Furthermore,

Esik [21] has shown that A

is k-deﬁnite if and only if the unary algebra (A, Tr(A)) is k-deﬁnite. Hence, the deﬁniteness

question of regular tree languages can be reduced to the well-known question of whether a

given unary algebra is deﬁnite. Let us also note that the paper [21] contains many further

results about deﬁnite tree automata. In particular, it is shown that the class of deﬁnite tree

automata is closed under cascade compositions, and various equational characterizations are

considered.

A language is reverse deﬁnite [7] if there is a k ≥ 0 such that for any word w ∈ X

∗

length ≥ k, w ∈ L if and only if the preﬁx of w of length k is in L. In the deﬁnition of

a generalized deﬁnite language [31] a preﬁx condition and a suﬃx condition are combined.

These notions can be extended to trees as follows.

12.4 Example The counterparts of preﬁxes of words are subtrees. However, two diﬀerences

should be noted. Firstly, a tree may have several subtrees of a given height, and secondly,

to take into account the whole frontier part of a tree up to a certain depth, we have to also

consider the subtrees of lesser height.

For any k ≥ 0, let sub

(t)={s ∈ sub(t) | hg(t) <k}. For example, if f (g(c),f(x, g(c)))

then sub

(t)=∅,sub

(t)={c, x},sub

(t)={c, x, g(c)},sub

(t)={c, x, g(c),f(x, g(c))} and

sub

(t)=sub(t) for all k ≥ 4.

For any k ≥ 0andanyX,letρ

Σ,k

(X) be the equivalence on T

(X) deﬁned by

sρ

Σ,k

(X) t if and only if sub

(s)=sub

(t)(s, t ∈ T

(X)).

It is obvious that ρ

Σ,k

(X) ∈ FCon

(X) with a congruence class for every possible collection

sub

(t) of subtrees of height <k. For any homomorphism ϕ : T

(X) →T

(Y ), any k ≥ 0

and any s, t ∈ T

(X), if sub

(s)=sub

(t) then clearly also sub

(sϕ)=sub

(tϕ). This

implies by Proposition 10.5 that Γ RDef

Σ,k

= {[ρ

Σ,k

(X))}

is a principal Σ-VFC for each

k =0, 1,..., and hence Γ RDef



k≥0

ΓRDef

Σ,k

is a Σ-VFC.

The ΣX-tree languages saturated by ρ

Σ,k

(X)aresaidtobereverse k-deﬁnite (k ≥ 0).

Let RDef

Σ,k

(X)denotethesetofallreversek-deﬁnite ΣX-tree languages. Then RDef

Σ,k

{RDef

Σ,k

(X)}

is the Σ-VTL corresponding to the Σ-VFC Γ RDef

Σ,k

.AΣX-tree language

is reverse deﬁnite if it is reverse k-deﬁnite for some k ≥ 0. Let RDef



k≥0

RDef

Σ,k

the Σ-VTL of all reverse deﬁnite Σ-tree languages. Of course, RDef

=ΓRDef

For any h, k ≥ 0andX,letγ

Σ,h,k

(X)=ρ

Σ,h

(X) ∩ δ

Σ,k

(X). It is again easy to see that

ΓGDef

Σ,h,k

= {[γ

Σ,h,k

(X))}

is a principal Σ-VFC for any pair h, k ≥ 0, and that the family

of these principal Σ-VFCs is directed. Therefore their union Γ GDef



h≥0,k≥0

ΓGDef

Σ,h,k

isalsoaΣ-VFC.

For any h, k ≥ 0andX,aΣX-tree language is called generalized (h, k)-deﬁnite if it is

saturated by γ

Σ,h,k

(X), and it is generalized deﬁnite if it is generalized (h, k)-deﬁnite for some

h, k ≥ 0. Hence, T ⊆ T

(X) is generalized (h, k)-deﬁnite, if s ∈ T if and only if t ∈ T ,for

414 M. Steinby

any s, t ∈ T

(X) such that sub

(s)=sub

(t)androot

(s)=root

(t). Let GDef

Σ,h,k

{GDef

Σ,h,k

(X)} be the Σ-VTL of all generalized (h, k)-deﬁnite Σ-tree languages, and let

GDef



h≥0,k≥0

GDef

Σ,h,k

be the Σ-VTL of all generalized deﬁnite Σ-tree languages.

Obviously, GDef

Σ,h,k

=ΓGDef

Σ,h,k

, and hence also GDef

=ΓGDef

. Moreover, it is clear

that

(1) Triv

⊆ GDef

Σ,h,k

⊆ Rec

for all h, k ≥ 0,

(2) GDef

Σ,0,k

=Def

Σ,k

(3) GDef

Σ,h,0

=RDef

Σ,h

,and

(4) GDef

Σ,i,j

⊆ GDef

Σ,h,k

whenever i ≤ h and j ≤ k.

Moreover, the inclusions in (4) are proper whenever i<jor j<k(for any non-trivial Σ).

The problems “T (A) ∈ RDef

?” and “T (A) ∈ GDef

?” were shown to be decidable by

Heuter [34, 35]. Wilke [92] characterizes the syntactic tree algebras (cf. Section 14) of reverse

deﬁnite binary tree languages.

A language L ⊆ X

∗

is local (in the strict sense) (cf. [17], for example), if there are sets

A, B ⊆ X and C ⊆ X

of initial letters, ﬁnal letters and allowed pairs of consecutive letters,

respectively, such that L = AX

∗

∩ BX

∗

− X

∗

− C)X

∗

. A corresponding notion also

appears in the theory of tree languages. Firstly, any regular tree language is the image of

a local tree language under an alphabetic tree homomorphism. Secondly, the production

trees of any context-free grammar form a local tree language, and hence every context-free

language is the yield of a local tree language (cf. [28, 29]).

12.5 Example The root symbol root(t)ofatreet corresponds to the last letter of a word.

The counterparts of pairs of consecutive letters, as well as of initial letters, are given by the

following notion. The set fork(t)offorks of a ΣX-tree t is deﬁned as follows:

(1) fork(x)=fork(c)=∅ for x ∈ X and c ∈ Σ

;

(2) fork(t)=fork(t

) ∪···∪fork(t

) ∪{f(root(t

),...,root(t

))} for t = f(t

,...,t

For example, if t = g(f(f(c, x),g(c))), then fork(t)={g(f),f(f,g),f(c, x),g(c)}. The (ﬁnite)

set of all possible forks appearing in any ΣX-tree is denoted by fork(Σ,X). For any F ⊆

fork(Σ,X)andR ⊆ Σ ∪ X,let

SL(F, R)={t ∈ T

(X) | fork(t) ⊆ F, root(t) ∈ R}.

Tree languages of this form are said to be local in the strict sense.LetSLoc

(X)bethe

set of all ΣX-tree languages local in the strict sense. Clearly, SLoc

(X) ⊆ Rec

(X) for any

ΣandX, but the family SLoc = {SLoc

(X)}

is not a Σ-VTL because it is not closed

under unions or complements. On the other hand, it is easy to see that it is closed under

inverse translations and inverse homomorphisms. For example, let ϕ : T

(X) →T

(Y )bea

homomorphism and let T = SL(F,R) ∈ SLoc

(Y ). Then Tϕ

−1

= SL(F



), where R



(R ∩Σ) ∪{x ∈ X | xϕ ∈ T },andF



consists of all forks f(d

,...,d

) ∈ fork(Σ,X) such that

f(e

,...,e

) ∈ F when for each i =1,...,m, e

= d

if d

∈ Σ, and e

=root(d

ϕ)ifd

∈ X.

This readily implies that the Σ-VTL generated by SLoc

, the family Loc

= {Loc

(X)}

Algebraic classiﬁcations of regular tree languages 415

of local Σ-tree languages, is simply the Boolean closure of SLoc

,thatistosay,Loc

(X)is

the Boolean closure of SLoc

(X)foreachX.

The family Loc

can also be obtained directly as the Σ-VTL corresponding to a Σ-VFC

as follows. For each X let us deﬁne the relation λ

(X)onT

(X) by the condition

sλ

(X) t if and only if fork(s)=fork(t)and root(s)=root(t)(s, t ∈ T

(X)).

It is easy to see that λ

(X) ∈ FCon

(X)foreachX,andthatΓLoc

= {[λ

(X))}

is the

Σ-VFC such that Γ Loc

=Loc

This example can be generalized by deﬁning for each k ≥ 0aΣ-VTLofk-testable tree

languages. For this we have to deﬁne in a natural way the set fork

(t)of“k-forks” of a tree

t; the forks deﬁned above are then 1-forks (cf. [43]).

13 Some generalizations

In this section we consider a few generalizations of the variety theory discussed above. Some

alternative approaches are then reviewed in the section to follow. Let us begin with the theory

of varieties of recognizable subsets of free algebras presented in [78]. The theory generalizes

also Eilenberg’s theories of ∗- and +-varieties. The point of view adopted is that the syntactic

algebra of a language L over an alphabet X is a monoid, the syntactic monoid of L, because

L is regarded as a subset of the free monoid X

∗

, while the syntactic algebra of a ΣX-tree

language T is a Σ-algebra because T is viewed as a subset of the term algebra T

(X). The

theory of syntactic congruences and syntactic algebras of subsets of algebras presented in

Section 8 is directly applicable to the generalization to be considered here.

Let V be any given variety of Σ-algebras. We shall consider recognizable subsets of the

free algebras over V generated by ﬁnite non-empty sets. Without loss of generality, we may

assume that these generating sets are the ﬁnite non-empty leaf alphabets X,Y,Z,... used

above. The free V-algebra generated by a set U is denoted by F

(U)=(F

(U), Σ).

A family of recognizable V-sets is a mapping R that assigns to every X asetR(X) ⊆

Rec(F

(X)) of recognizable subsets of F

(X). We write R = {R(X)}

and deﬁne the

⊆-relation as well as the unions and intersections of families of recognizable V-sets by the

natural componentwise conditions.

13.1 Deﬁnition A family of recognizable V-sets R = {R(X)}

is a variety of recognizable

V-sets,aV-VRS for short, if for all X and Y ,

(1) R(X) is a Boolean subalgebra of Rec(F

(X)),

(2) T ∈R(X) implies p

−1

(T ) ∈R(X) for any p ∈ Tr(F

(X)), and

(3) T ∈R(Y ) implies Tϕ

−1

∈R(X) for any homomorphism ϕ : F

(X) →F

(Y ).

Let VRS(V) denote the class of all V-VRSs.

Clearly, (VRS(V), ⊆) is a complete lattice. If V is the class of all Σ-algebras, the term

algebra T

(X) can be used as F

(X) and then the V-varieties of recognizable sets are

exactly the Σ-VTLs. Similarly, for the variety Mon of all monoids and the variety Sg of all

semigroups, VRS(Mon)andVRS(Sg) are the classes of all ∗- and +-varieties, respectively.

416 M. Steinby

Let R = {R(X)}

be a family of recognizable V-sets. The syntactic algebra SA(T)ofa

set T ⊆ F

(X) is deﬁned to be its syntactic algebra F

(X)/θ

as a subset of F

(X). Of

course, SA(T ) is ﬁnite if and only if T is recognizable in F

(X). Now, let

({SA(T ) | T ∈R(X)forsomeX})

be the Σ-VFA generated by the syntactic algebras of the subsets belonging to R. On the other

hand, for any class K of ﬁnite Σ-algebras, let K

= {K

(X)}

be the family of recognizable

V-sets such that K

(X)={T ⊆ F

(X) | SA(T ) ∈ K} for each X. Furthermore, let VFA(V)

denote the class of all Σ-VFAs contained in V. We may now formulate the following Variety

Theorem [78].

13.2 Theorem For any variety V of Σ-algebras, the mappings

VRS(V) → VFA(V), R →R

, and VFA(V) → VRS(V), K → K

form a pair of mutually inverse isomorphisms between the complete lattices (VRS(V), ⊆)

and (VFA(V), ⊆).

The theorem can be proved exactly as the parts of Theorem 11.9 that concern the con-

nection between VTL(Σ) and VFA(Σ). As noted above, the theory of syntactic algebras

presented in Section 8 is directly applicable here, too, and replacing the term algebras T

(X)

with the free algebras F

(X) does not require any essential changes either since just the

freeness property is needed.

We could complete Theorem 13.2 with varieties of ﬁnite congruences on the free algebras

(X). As a matter of fact, varieties of congruences appear both in the related theory to be

discussed next and the generalization to many-sorted mentioned thereafter.

In [1] Almeida studies various ways to describe varieties of ﬁnite algebras. Since varieties of

recognizable sets and varieties of ﬁnite congruences (in our terminology) are among these, his

work also includes a variety theory similar to that considered above. A detailed presentation

of this theory, as well as many related matters, can be found in [2]. Here we review just the

main notions and results adapting the terminology and notation to ours.

The starting point is any given Σ-VFA K. Syntactic congruences and syntactic algebras

of subsets of algebras are deﬁned as above. A subset L ⊆ A of an algebra A =(A, Σ) is

said to be K-recognizable if it is recognized by a member of K, i.e., if L = Fϕ

−1

for some

B =(B,Σ) in K, a subset F ⊆ B and a homomorphism ϕ : A→B.Moreover,L ⊆ A is

locally K-recognizable if L ∩H is K-recognizable for every ﬁnite H ⊆ A.

Let V =V(K) be the variety of Σ-algebras generated by K,andforeachn ≥ 1, let

=(F

, Σ) be the free V-algebra generated by X

:= {x

,...,x

}. Similarly let F

, Σ) be the free V-algebra generated by X

:= {x

,...}. We may assume that

⊆ F

⊆ ... ⊆ F



n≥1

.Foreachn ≥ 1, let Rec

(K)bethesetofall

K-recognizable subsets of F

,andletCon

(K)={θ ∈ Con(F

) |F

/θ ∈ K}.Moreover

let LRec(K) be the set of all locally K-recognizable subsets of F

, and let LCon(K) consist

of all congruences θ ∈ Con(F

) such that B/θ

∈ K for every ﬁnitely generated subalgebra

B =(B,Σ) of F

It is clear that the family (Rec

(K) | n ≥ 1) is essentially the V-VRS corresponding

to K since Rec

(K)=K

) for every n ≥ 1. The locally K-recognizable subsets of F

represent in some sense families of sets of K-recognizable subsets of the algebras F

(n ≥ 1).