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

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

Algebraic classiﬁcations of regular tree languages 417

In particular, a subset L of F

is in LRec(K) if and only if L∩F

∈ Rec

(K) for every n ≥ 1.

Similarly LCon(K) is closely related to the family of all Con

(K)(n ≥ 1).

A variety of K-languages is a sequence V =(V

)

n≥1

such that for all n, m ≥ 1,

(1) V

is a Boolean subalgebra of Rec

(K),

(2) p

−1

(T ) ∈ V

whenever T ∈ V

and p ∈ Tr(F

), and

(3) Tϕ

−1

∈ V

for any T ∈ V

and any homomorphism ϕ: F

→F

A global variety of K-languages is a Boolean subalgebra W of LRec(K) closed under inverse

translations and inverse endomorphisms of F

such that if L ∈ LRec(K) and for every ﬁnite

H ⊆ F

there is an L

∈Wfor which L ∩H = L

∩H,thenL ∈W. The last condition

may be interpreted to mean that W contains any subset of F

that belongs to it locally.

A variety of ﬁlters of K-congruences is a sequence (Φ

)

n≥1

such that for all m, n ≥ 1,

(1) Φ

is a ﬁlter of Con

(K), and

(2) θ ∈ Φ

implies ϕ ◦ θ ◦ϕ

−1

∈ Φ

for any homomorphism ϕ: F

→F

Similarly, a global variety of ﬁlters of K-congruences is a ﬁlter Φ of LCon(K) closed under

inverse endomorphisms of F

such that if θ ∈ LCon(K) and for every ﬁnitely generated

subalgebra A =(A, Σ) of F

there is a  ∈ Φsuchthatθ

= 

,thenθ ∈ Φ.

Now Almeida’s Variety Theorem establishes isomorphisms between the complete lattices

formed by (1) all varieties of K-languages, (2) all global varieties of K-languages, (3) all

varieties of ﬁlters of K-congruences, (4) all global varieties of ﬁlters of K-congruences, and

(5) all Σ-VFAs contained in V.

Salehi and Steinby [73] extend the theory of varieties of recognizable sets to many-sorted

algebras (cf. [51] for a survey and many further references). Many-sorted algebras are much

used in computer science, especially in the theory of data types. Many-sorted tree languages

were introduced by Maibaum [48], and Courcelle [13, 14] has studied recognizable subsets of

general many-sorted algebras. Moreover, it can be noted that Wilke’s [92] tree algebras—to

be considered in the next section—involve three sorts. For a given set S of sorts, there are

actually two natural kinds of recognizable subset of an S-sorted algebra A =(A, Ω), where

A = A



s∈S

is the S-sorted set of elements and Ω is an S-sorted ranked alphabet. Firstly, we

may consider sorted subsets L = L



s∈S

that include for each sort s ∈ S a subset L

⊆ A

of that sort. On the other hand, there are the ‘pure’ subsets in which all elements are of the

same sort. In [48] and [13, 14] sets of the second kind are considered, but in [73] the variety

theory is presented primarily for sorted subsets. However when S is ﬁnite, the recognizable

subsets the two types are deﬁnable in terms of each other, and in [73] a variety theorem is

also derived for varieties of pure recognizable sets.

In the theories mentioned so far, all varieties considered are over a given ﬁxed ranked

alphabet. In [84] the variety theory of tree languages is generalized so that we may speak

generally about, say, the variety of deﬁnite tree languages or the variety of locally testable tree

languages without ﬁxing the ranked alphabet. Corresponding to such generalized varieties

of tree languages (GVTLs) we have generalized varieties of ﬁnite algebras (GVFAs) and

generalized varieties of ﬁnite congruences (GVFCs). To deﬁne these one has to generalize

the basic notions of universal algebra in such a way that algebras of diﬀerent types can be

considered together. For example, a generalized homomorphism from a Σ-algebra A =(A, Σ)

418 M. Steinby

to an Ω-algebra B =(B,Ω) consists of two mappings ι:Σ→ Ωandϕ: A → B such that

ι(Σ

) ⊆ Ω

for every m ≥ 0, and f

,...,a

)ϕ = ι(f )

ϕ,...,a

ϕ) for all m ≥ 0,

f ∈ Σ

and a

,...,a

∈ A. Also the deﬁnitions of syntactic congruences and syntactic

algebras have to be suitably modiﬁed. All the examples of Σ-VTLs mentioned in Section 7

yield also examples of GVTLs. Thus, there are the GVTLs of deﬁnite, reverse deﬁnite,

generalized deﬁnite, locally testable and aperiodic tree languages, for example. A recent

example is provided by the piecewise testable tree languages studied by Piirainen [62]. Here

piecewise testability is deﬁned using the well-known homeomorphic embedding order of trees

(cf. [3], for example). In fact for each k ≥ 0, the k-piecewise testable tree languages form a

GVTL, and the GVTL of all piecewise testable tree languages is the union of the ascending

chain of these sub-GVTLs. Let us also note that if V = {V

(X)}

Σ,X

is a GVTL (where Σ

ranges over all ranked alphabets and X over all leaf alphabets), then for any ﬁxed Σ we get

aΣ-VTLV

= {V

(X)}

A positive ∗-variety is deﬁned as a generalized ∗-variety that is not required to be closed

under complementation. Pin [64] shows that these families of regular languages can be

characterized by ordered syntactic monoids, and he proves a variety theorem that connects

positive ∗-varieties with varieties of ﬁnite ordered monoids. Of course there is a corresponding

notion of positive +-varieties. Recently Petkovi´c and Salehi [60] have presented some tree

language counterparts to this theory. In particular they extend the above mentioned theory

of generalized varieties by establishing a correspondence between generalized positive varieties

of tree languages and generalized varieties of ﬁnite ordered algebras. Any GVTL is naturally

a generalized positive variety of tree languages but also other examples are presented in [60].

14 Alternative approaches

Transition semigroups of tree automata were already considered in the 1970’s (for references,

cf. [28, p. 123]), but syntactic monoids as a means to classify regular tree languages were

introduced several years later by Thomas [88, 89]. A similar notion deﬁned for binary trees

is used in [53, 54, 55, 65].

LetusﬁrstnotethatthesetC

(X)ofallΣX-contexts forms a monoid with respect

to the product p · q = q(p)withξ as the unit element. Recall also that for any ΣX-tree t

and any ΣX-context p, t · p is the ΣX-tree p(t). Following [88, 89], the syntactic monoid

congruence of a ΣX-tree language T is now deﬁned as the relation µ

on C

(X) such that

for any p, q ∈ C

(X),

pµ

q if and only if (∀t ∈ T

(X))(∀r ∈ C

(X))[t · p · r ∈ T ↔ t · q · r ∈ T ].

The syntactic monoid SM(T )ofT is the quotient monoid C

(X)/µ

.Itiseasytoshow

that a ΣX-tree language is regular if and only if its syntactic monoid is ﬁnite. Of course,

the syntactic semigroup congruence σ

and the syntactic semigroup SS(T )=C

(X)/σ

are

deﬁned similarly, but restricting p and q to C

(X):=C

(X) −{ξ}.

The following facts about syntactic monoids of tree languages are due to K. Salomaa [75]:

(1) Every ﬁnite monoid is isomorphic to the syntactic monoid of a regular tree language

over some (unary) ranked alphabet and a suitable leaf alphabet.

(2) The syntactic monoid of a regular tree language T is isomorphic to the translation

monoid Tr(SA(T )) of the syntactic algebra of T .

Algebraic classiﬁcations of regular tree languages 419

(3) SM(T

(X) − T )=SM(T ) and SM(T ∩ U ), SM(T ∪ U) / SM(T) × SM(U) for any

T,U ⊆ T

(X).

(4) SM(p

−1

(T )) / SM(T ) for any T ⊆ T

(X)andanyp ∈ C

(X).

(5) SM(Tϕ

−1

) / SM(T) for any homomorphism ϕ: T

(X) →T

(Y )andT ⊆ T

(Y ).

Let M be a variety of ﬁnite monoids. For any Σ and X,letM

(X)bethesetofall

ΣX-tree languages T such that SM(T ) ∈ M. If follows from the above facts (3)–(5) that

= {M

(X)}

is a Σ-VTL.

14.1 Example AΣX-tree language T is called aperiodic,ornon-counting,ifthereisa

number n ≥ 0 such that for all t ∈ T

(X)andp, q ∈ C

(X), t · p

n+1

· q ∈ T if and only if

t · p

· q ∈ T . It is easy to verify directly that the family Ap

= {Ap

(X)}

of such tree

languages is a Σ-VTL, but Thomas [88, 89] proved that Ap

= Ap

,whereAp is the VFM

of ﬁnite aperiodic monoids, that is to say ﬁnite monoids in which all subgroups are trivial.

He also shows that the families of aperiodic, ﬁrst-order deﬁnable and star-free tree languages

are all pairwise distinct although the corresponding string language families are all equal (cf.

[50]). These families and related matters are studied further in [35, 36, 66, 68, 67, 69].

14.2 Example AΣ-algebraA =(A, Σ) is said to be monotone if there is an order ≤ on A

such that a

,...,a

≤ f

,...,a

) for all m>0,f ∈ Σ

and a

,...,a

∈ A.AΣX-tree

language is monotone if it is recognized by a ﬁnite monotone Σ-algebra. An element u ∈ S

of a semigroup S is a divisor of an element s ∈ S if s = uv or s = vu for some v ∈ S.A

subsemigroup is said to be closed under divisors if it contains all divisors of its elements.

Finally, a subsemigroup S



of a semigroup S is called a right-unit subsemigroup if there is

an element s ∈ S such that S



= {u ∈ S | su = s}.G´ecseg and Imreh [25] prove that a

regular tree language is monotone if and only if every right-unit subsemigroup of its syntactic

monoid is closed under divisors. Piirainen [61] notes that the ﬁnite monotone algebras form

a GFVA and the monotone tree languages the corresponding GVTL. Moreover he shows that

a regular tree language is monotone if and only if its syntactic monoid is R-trivial.

Like the generalized variety theory discussed in the previous section, the syntactic monoid

approach does not require a ﬁxed ranked alphabet. In [84] it is noted that every family of

recognizable tree languages M

deﬁnable by syntactic monoids is a GVTL, but that the

converse does not hold: not every GVTL is of the form M

. Indeed, for each VFM M, M

is just the greatest GVTL V such that SM(T ) ∈ M whenever T is in V. For example, in

[92] Wilke shows that the reverse deﬁnite tree languages cannot be characterized by syntactic

monoids (or syntactic semigroups). Recently, Salehi [71] has described the GVTLs that can be

characterized by syntactic monoids or syntactic semigroups. His results conﬁrm the intuitive

impression that the deﬁning power of the syntactic monoid framework is quite limited for

tree languages. In particular, it turns out that the deﬁnite tree languages cannot be deﬁned

by syntactic monoids or semigroups, contrary to what is claimed in [54]. Furthermore, in

[62] Piirainen shows that the piecewise testable tree languages cannot be deﬁned by syntactic

monoids. In the paper [60] mentioned already in the previous section, Petkovi´c and Salehi

also consider ordered syntactic monoids of tree languages and, extending the result of [71],

they characterize the generalized positive varieties of tree languages that can be characterized

by these.

420 M. Steinby

The syntactic monoid of a regular language L is isomorphic to the transition monoid of

the minimal recognizer of L, and this again is the monoid of all unary term functions of the

algebra underlying the recognizer. This observation may be seen as the starting point of the

classiﬁcation theory by Z.

Esik [22], where everything is formulated in terms of (algebraic)

theories of Lawvere (cf. [20, 22]). Such a theory is a category of a certain kind in which the

objects are the non-negative integers. A theory T is ﬁnitary if for each pair of objects n, p,the

set T (n, p) of morphisms n → p is ﬁnite. Each ranked alphabet Σ deﬁnes a theory ΣTM of

trees such that for each n ≥ 0, we may identify ΣTM(n, 1) with the set T

)ofΣX

-trees.

A tree language L ⊆ ΣTM(n, 1) is then said to be recognizable if there exist a ﬁnitary theory

T , a morphism ϕ : ΣTM → T of theories and a set P ⊆ T (n, 1) such that T = Pϕ

−1

Esik

develops a theory of varieties of such recognizable tree languages that in its form resembles

the theory described in Section 11, but syntactic algebras are replaced by syntactic theories,

varieties of ﬁnite algebras by varieties of ﬁnitary theories, etc. The paper [22] also considers

several examples, suggests some open problems, and compares the presented theory with

other approaches. In particular, the relationship to the theory of generalized varieties of [84]

is discussed in some detail.

As noted in [22],

Esik’s theory could be reformulated in terms of clones (cf. [10, 15, 49]). In

[23]

Esik and Weil introduce syntactic preclones and present a variety theorem that connects

each variety of tree languages with a variety of ﬁnitary preclones. Within this framework

they characterize the ﬁrst-order deﬁnable tree languages as well as some families obtained by

extending the FO language with various restricted second-order quantiﬁers.

The tree algebra framework of Wilke [92] is designed for languages of binary trees. The

nodes of the trees considered are labelled with symbols taken from a ﬁnite label alphabet

A, and each of these symbols may be used both as a binary symbol labelling an inner node

or as a nullary symbol labelling a leaf. Hence A may be regarded as a (generalized) ranked

alphabet such that A

= A

= A. Then the set T

of A-trees and the set C

of A-contexts

are deﬁned inductively by the following two clauses:

(1) A ⊆ T

and ξ ∈ C

;

(2) if a ∈ A, s, t ∈ T

and p ∈ C

,thena(s, t) ∈ T

and a(p, t),a(t, p) ∈ C

To represent such trees and contexts, Wilke introduces a sorted ranked alphabet Γ with the

three sorts l (labels), t (trees)andc (contexts), and the six operation symbols ι, κ, λ, ρ,

η and σ. The types of these operation symbols and their interpretations in the Γ-algebra

=(A, T

, Γ) of A-trees and A-contexts are as follows:

ι : l → t,a→ a; κ : ltt → t, (a, s, t) → a(s, t); λ : lt → c, (a, t) → a(ξ, t);

ρ : lt → c, (a, t) → a(t, ξ); η : ct → t, (p, t) → p(t); σ : cc → c, (p, q) → p(q).

Hence in T

the ι-operator forms from a label a ∈ A the one-node A-tree a,theκ-operator

creates from a label a and two A-trees s and t anewA-tree with an a-labelled root and

s and t as the two maximal proper subtrees, etc. As a matter of fact Wilke considers the

subalgebra T

=(A, T

, Γ) of T

,whereC

:= C

−{ξ}, obtained by omitting the unit

A-context ξ. Each Γ-term with variables in A of sort t or of sort c represents in a natural

way an A-tree or an A-context respectively, when these interpretations of the operators are

adopted. In fact, it is obvious that every A-tree and every A-context has at least one such

Algebraic classiﬁcations of regular tree languages 421

representation. For example, the A-tree a(b(a, a),b), where a, b ∈ A, is represented both by

κ(a, κ(b, ι(a),ι(a)),ι(b)) and by η(λ(a, ι(b)),κ(b, ι(a),ι(a))).

It is easy to verify that the algebra of A-trees T

satisﬁes the identities

σ(σ(p, q),r)  σ(p, σ(q,r)), (TA1)

η(σ(p, q),t)  η(p, η(q,t)), (TA2)

η(λ(a, s),t)  κ(a, t, s), (TA3)

η(ρ(a, s),t)  κ(a, s, t), (TA4)

where p, q and r are variables of sort c, s and t are variables of sort t,anda is a variable

of sort l. Any Γ-algebra satisfying the identities (TA1)–(TA4) is called a tree algebra. Wilke

shows that T

is the free tree algebra generated by the sorted set A, ∅, ∅.Thesyntactic

tree algebra congruence τ

of an A-tree language T ⊆ T

is the greatest congruence on

saturating the sorted subset ∅,T,∅,andthesyntactic tree algebra STA(T )ofT is

deﬁned as the corresponding quotient algebra T

/τ

. It is not hard to see that an A-tree

language T is regular if and only if its syntactic tree algebra STA(T ) is ﬁnite. In fact, the t-

component of STA(T) is in essence the syntactic algebra SA(T )ofT while the c-component

corresponds to the syntactic semigroup SS(T )ofT . As an application of syntactic tree

algebras, Wilke presents an elegant eﬀective equational characterization of the reverse deﬁnite

A-tree languages. The general theory of tree algebras is developed further in [74, 72].

15 Deterministic top-down tree languages

In this section we consider tree languages recognized by deterministic top-down tree recogniz-

ers,orDT recognizers for short, that read their input trees in a deterministic way starting

at the root and ending at the leaves. Such tree automata are also called deterministic root-

to-frontier recognizers,orDR recognizers. That DT recognizers are much weaker than the

bottom-up recognizers considered above was already observed in the 1960s. However, the

family of DT-recognizable tree languages is still quite interesting and it includes, for exam-

ple, the sets of production trees of context-free grammars (cf. [29], for example). For general

introductions to the topic and further references we refer the reader to [28, 29, 38, 39]. Here

we shall consider the variety properties of this family of tree languages. In particular, we de-

ﬁne the syntactic path monoid introduced by G´ecseg and Steinby [30] as a tool for classifying

DT-recognizable tree languages.

Let Σ be a ranked alphabet and X a leaf alphabet. To simplify matters, we assume that

= ∅.Adeterministic top-down Σ-algebra,aDT Σ-algebra for short, A =(A, Σ) consists

of a non-empty set A and a Σ-indexed family of top-down operations

: A −→ A

(m>0,f∈ Σ

Such a DT Σ-algebra A is ﬁnite if A is a ﬁnite set. In [27] it is shown that subalge-

bras, homomorphisms, congruences, quotient algebras and direct products—with their usual

properties—can be deﬁned in a natural way for DT-algebras.

15.1 Deﬁnition A deterministic top-down ΣX-recognizer,oraDT ΣX-recognizer, is a sys-

tem A =(A,a

,α), where

422 M. Steinby

(1) A =(A, Σ) is a ﬁnite DT Σ-algebra,

(2) a

∈ A is the initial state,and

(3) α : X → ℘A is the ﬁnal state assignment.

The elements of A are the states of A. To deﬁne the tree language recognized by A,weﬁrst

extend α to a mapping α

: T

(X) → ℘A thus:

• xα

= xα for each x ∈ X;

• f(t

,...,t

)α

= {a ∈ A | f

(a) ∈ t

×···×t

Now the tree language recognized by A is deﬁned as

T (A)={t ∈ T

(X) | a

∈ tα

AΣX-tree language T is said to be DT-recognizable if T = T (A)foraDTΣX-recognizer A.

Let DRec

= {DRec

(X)}

where, for each X,DRec

(X) is the set of all DT-recognizable

ΣX-tree languages.

The process by which a DT ΣX-recognizer A =(A,a

,α) accepts or rejects a given input

tree t ∈ T

(X) can be described as follows:

• A starts at the root of t in state a

;

• if A has reached node u labeled with f ∈ Σ

in state a, it continues to the i

immediate

successor node of u in state a

(1 ≤ i ≤ m), where (a

,...,a

)=f

(a);

• t is accepted if and only if A reaches each leaf in a state a ∈ xα matching the label x

of that leaf.

The family DRec

is closed under inverse translations and inverse homomorphisms, but

not under all Boolean operations. Hence, it is not a variety of Σ-tree languages, but its

Boolean closure BDRec

is. The Σ-VTL BDRec

has been studied extensively by Jurvanen

[38, 39]. For example, she has established the inclusion relations between BDRec

and many

of the other Σ-VTLs mentioned before. In particular it is shown that BDRec

is properly

includedinRec

(for any nontrivial Σ), a fact also established by Thomas [89] in a diﬀerent

way. However, it seems that the corresponding Σ-VFA is still not known.

In what follows, we shall consider a new kind of syntactic monoid introduced in [30]

especially for DT-recognizable tree languages.

As shown by G´ecseg and Steinby in [27], each DT ΣX-recognizer can be converted into

an equivalent minimal DT ΣX-recognizer of a certain kind, and that this minimal recognizer

is unique up to isomorphism. To make these statements precise, we have to introduce some

new concepts. For any DT ΣX-recognizer A =(A,a

,α)andanya ∈ A,let

T (A,a):={t ∈ T

(X) | a ∈ tα

and call state a a 0-state if T (A,a)=∅. Clearly T (A,a)=∅ means that A accepts no tree

starting in state a.Furthermore,astatea ∈ A is said to be reachable if a

⇒

∗

a,where⇒

∗

is the reﬂexive, transitive closure of the relation ⇒ (⊆ A × A) deﬁned by

a ⇒ b if and only if b = π

(a)) for some m>0,f∈ Σ

and 1 ≤ i ≤ m (a, b ∈ A),

where π

: A

→ A is the i

projection mapping.

Algebraic classiﬁcations of regular tree languages 423

15.2 Deﬁnition We call a DT ΣX-recognizer A =(A,a

,α)

(1) normalized if, for all m ≥ 1, f ∈ Σ

and a ∈ A, either every component in f

(a)=

,...,a

) is a 0-state or no a

is a 0-state,

(2) reduced if T (A,a)=T (A,b) implies a = b (a, b ∈ A),

(3) connected if all of its states are reachable, and

(4) minimal if it is connected and reduced.

15.3 Deﬁnition A homomorphism ϕ : A → B from a DT ΣX-recognizer A =(A,a

,α)to

aDTΣX-recognizer B =(B,b

,β) is deﬁned by a mapping ϕ : A → B such that

(1) f

(aϕ)=(a

ϕ,...,a

ϕ)iff

(a)=(a

,...,a

), m>0, f ∈ Σ

, a ∈ A,

(2) a

ϕ = b

,and

(3) xβϕ

−1

= xα for every x ∈ X.

A bijective homomorphism ϕ : A → B is an isomorphism of DT ΣX-recognizers and in this

case we say that A and B are isomorphic.

The following results of [27] show that the same facts about minimal recognizers hold

for deterministic top-down tree recognizers as in the bottom-up case with the exception that

uniqueness requires normalization.

15.4 Proposition Any DT ΣX-recognizer A can be converted to an equivalent normalized

minimal DT ΣX-recognizer B, and this is also minimal with respect to the number of states

among all DT ΣX-recognizers B such that T (B)=T (A). Moreover, any two equivalent

minimal normalized DT ΣX-recognizers are isomorphic.

Deterministic top-down recognizers are essentially weaker than their bottom-up counter-

parts because they have to accept or reject at each leaf separately without being able to

combine or compare in any way the information gathered from diﬀerent paths leading from

the root to leaves. In fact, a DT recognizer accepts any tree t such that every path of t appears

in some tree accepted by it, and this property actually characterizes the DT-recognizable tree

languages as shown in [12, 90]. Since paths are also used for deﬁning the syntactic monoids

to be considered here, we now deﬁne them formally.

The path alphabet associated with Σ is the ordinary ﬁnite alphabet



Σ=



{Σ

×{1,...,m}|m>0}.

We write (f, i) ∈



Σasf

.Iff is the label of a node, i indicates the direction taken at that

node. Hence words over



Σ represent paths leading from the root to a leaf in a ΣX-tree.

15.5 Deﬁnition For any x ∈ X,thesetg

(t)ofx-paths in a ΣX-tree t is deﬁned as follows:

(1) g

(x)={e};

(2) g

(y)=∅ for y ∈ X, y = x;

424 M. Steinby

(3) g

(t)=f

) ∪···∪f

)fort = f (t

,...,t

The x-path language of a tree language T ⊆ T

(X)isthesetT



(t) | t ∈ T }.Thex-

path languages T

of T (x ∈ X) are collectively called the path languages of T .Furthermore

the path closure of T is deﬁned as the ΣX-tree language

c(T ):={t ∈ T

(X) | (∀x ∈ X) g

(t) ⊆ T

and T is said to be closed if c(T )=T .

It is clear that T → c(T )isaclosureoperatoronT

(X). The following lemma shows

that a closed tree language is completely determined by its path languages.

15.6 Lemma If T ⊆ T

(X) is closed and t ∈ T

(X),thent ∈ T if and only if g

(t) ⊆ T

for every x ∈ X.

The following basic fact was proved by Courcelle [12] and by Vir´agh [90].

15.7 Proposition A regular tree language is DT-recognizable if and only if it is closed.

For example, the ﬁnite set T = {f (x, y),f(y, x)} cannot be recognized by a DT recognizer

since it is not closed. Indeed it is clear that if a DT recognizer accepts the trees f (x, y)and

f(y, x), then it must accept also f(x, x)andf(y,y). On the other hand, it is easy to construct

a DT recognizer for the closure c(T )={f(x, y),f(y, x),f(x, x),f(y, y)}.

We shall use also the following simple observation.

15.8 Lemma The path languages T

(x ∈ X) of any DT-recognizable ΣX-tree language T

are regular.

Proof By Proposition 15.4, we may assume that T = T (A) for a normalized DT ΣX-

recognizer A =(A,a

,α). Then for each x ∈ X, the language T

is recognized by the



Σ-recognizer A

=(A,



Σ,δ,a

,xα), where δ is deﬁned by setting δ(a, f

)=a

for all a ∈ A

and f

∈



Σ assuming that f

(a)=(a

,...,a

). The fact that A is normalized is needed to

prove L(A

) ⊆ T

. 2

The following notions were introduced in [30].

15.9 Deﬁnition The syntactic path congruence of a ΣX-tree language T is the relation µ



∗

deﬁned by

µ

⇐⇒ (∀x ∈ X)(∀u, v ∈



∗

)(uw

v ∈ T

↔ uw

v ∈ T

)(w

∈



∗

The syntactic path monoid of T is the quotient monoid PM(T )=



∗

/µ

.Thesyntactic path

semigroup PS(T)ofT is similarly deﬁned as a quotient monoid of



restricting µ



Since µ

is the intersection of the usual syntactic congruences of the path languages of

T , it really is a congruence on



∗

and the following lemma holds.

15.10 Lemma For any ΣX-tree language T , µ

is the greatest congruence on



∗

that sat-

urates every path language T

(x ∈ X) of T .

Algebraic classiﬁcations of regular tree languages 425

The following counterpart to the usual Myhill Theorem is noted in [30].

15.11 Theorem For any closed ΣX-tree language T the following are equivalent:

(1) T ∈ DRec

(X);

(2) there is a congruence on



∗

of ﬁnite index that saturates all the path languages of T ;

(3) µ

is of ﬁnite index.

Of course, the theorem yields the following immediate consequence.

15.12 Corollary A closed tree language T is DT-recognizable if and only if the monoid

PM(T ) is ﬁnite.

For any T ∈ DRec

(X), the syntactic path monoid PM(T ) is eﬀectively computable

because it can be shown to be isomorphic to the minimal recognizer of the family (T

| x ∈ X)

of path languages of T , and this can be formed by Lemma 15.8; a recognizer of (T

| x ∈ X)

is a ﬁnite automaton A =(A,



Σ,δ,a

, (F

| x ∈ X)) with a family of sets of ﬁnal states such

that for every x ∈ X, T

= L(A

)forthe



Σ-recognizer A

=(A,



Σ,δ,a

). One may

use the well-known minimization theory of Moore-automata to show that such a minimal

recognizer always exists. The transition monoid TM(A)ofA is formed by the mappings

: A −→ A, a → δ(a, w), (w ∈



∗

)

with u

=(uv)

as the operation.

In conclusion, we present some examples of characterizations by path monoids.

15.13 Example ADTΣX-recognizer A =(A,a

,α)ismonotone if there is an order ≤

on A such that a ≤ a

,...,a

, whenever f

(a)=(a

,...,a

)forsomem>0, f ∈ Σ

and a, a

,...,a

∈ A. A DT-recognizable tree language is monotone if it is recognized by

a monotone DT recognizer. G´ecseg and Imreh [25] show that a closed ΣX-tree language T

is monotone if and only if every right-unit subsemigroup of PM(T ) is closed under divisors.

By the results of Piirainen [61] noted in Example 14.2, this means that T is monotone if and

only if PM(T )isR-trivial.

The following example is from [26] but we have slightly modiﬁed the terminology.

15.14 Example For any given DT Σ-algebra A =(A, Σ), we deﬁne the state frontier map

sf : A × T

(X) → A

∗

as follows:

(1) sf(a, x)=a for a ∈ A and x ∈ X;

(2) sf(a, t)=sf(a

) ...sf(a

)fort = f (t

,...,t

), a ∈ A and f

(a)=(a

,...,a

The minimum height mh(t)ofaΣX-tree t is deﬁned by the conditions:

(1) mh(x) = 0 for any x ∈ X;

(2) mh(t) = min(mh(t

),...,mh(t

)) + 1 for t = f (t

,...,t

426 M. Steinby

For any k ≥ 0, a DT Σ-algebra A =(A, Σ) is called frontier k-deﬁnite if sf(a, t)=sf(b, t)for

all a, b ∈ A whenever mh(t) ≥ k,andwecallA frontier deﬁnite if it is frontier k-deﬁnite for

some k ≥ 0. A DT ΣX-recognizer A =(A,α,F) and the tree language T (A) recognized by

it are called frontier deﬁnite if the underlying DT Σ-algebra is frontier deﬁnite. Recall also

that a semigroup S is deﬁnite if Su = {u} for every idempotent u ∈ S, that is to say every

idempotent of S is a right zero. Now, G´ecseg and Imreh [26] show that a DT-recognizable tree

language T is frontier deﬁnite if and only if its syntactic path semigroup PS(T) is deﬁnite.

G´ecseg and Imreh [26] give also a characterization of a family of similarly deﬁned nilpotent

DT-recognizable tree languages. These examples may appear somewhat contrived as the

families of tree languages are deﬁned through properties of their recognizers, but it is to be

noted that the characterizations give decision methods that do not require any knowledge

about the parameter k. It seems that the syntactic monoid (or semigroup) approach is more

useful in the case of DT-recognizable tree languages than in the case of all recognizable tree

languages because DT-recognizable tree languages are determined by their path languages.

Acknowledgements

I have derived much inspiration from working with Tatjana Petkovi´c, Ville Piirainen and

Saeed Salehi on topics related to this paper. I also thank all of them for reading the

manuscript and for their many useful comments. Thanks are also due to the organizers

of the excellent seminar that led me to write this paper, as well to the patient editors of this

volume. I am especially grateful to Martin Goldstein for his careful editorial work.

References

[1] J. Almeida, On pseudovarieties, varieties of languages, ﬁlters of congruences, pseudo-

identities and related topics, Algebra Universalis 27 (1990), 333–350.

[2] J. Almeida, Finite Semigroups and Universal Algebra, World Scientiﬁc, Singapore, 1995.

[3] J. Avenhaus, Reduktionssysteme, Springer-Verlag, Berlin, 1995.

[4] C. J. Ash, Pseudovarieties, generalized varieties and similarly described classes, J.

Algebra 92 (1985), 104–115.

[5] J. T. Baldwin and J. Berman, Varieties and ﬁnite closure conditions, Colloq. Math. 35

(1976), 15–20.

[6] W. Brauer, Automatentheorie, B. G. Teubner, Stuttgart, 1984.

[7] J. A. Brzozowski, Canonical regular expressions and minimal state graphs of deﬁnite

events, in: Proc. Symp. Math. Theory of Automata, Microwave Research Inst. Symp.

Ser. 12, Brooklyn, New York, 1963, 529–561.

[8]J.R.B¨uchi, Finite Automata, Their Algebras and Grammars. Towards a Theory of

Formal Expressions, Springer-Verlag, New York, 1989.