Annales Academiæ Scientiarum Fennicæ Mathematica Volumen 25, 2000, 325–336

ON SOME CLASSES OF TREE AUTOMATA AND TREE LANGUAGES

Ferenc Gécseg

József Attila University, Department of Informatics Aradi vértanúk tere 1, H-6720 Szeged, Hungary; gecseg@inf.u-szeged.hu

Abstract. In this paper we give a structural characterization of three classes of tree automata. Namely, we shall homomorphically represent the classes of nilpotent, definite, and monotone tree automata by means of quasi-cascade-products of unary nilpotent and unary definite tree automata in the first two cases, and by means of products of simpler tree automata in the third case.

Introduction

In the sixties, an intensive axiomatic investigation of the algebra of regular languages and some important special language classes was carried out. One of the best results for the axiomatic characterizations of regular languages can be found in [11]. The studies of special languages concerned mainly the classes of nilpotent and definite languages (see [8], [12] and [1], [6], [10], [9], respectively). The concepts of nilpotent languages, nilpotent automata, definite languages, and definite automata, together with the basic results characterizing them, have been generalized to trees. In [14] a nice survey is given of the structural properties of the classes of nilpotent and definite tree automata.

1. Notions and notation

Sets of operational symbols will be denoted by Σ with or without superscripts. If Σ is finite, then it is called a ranked alphabet. For the subset of Σ consisting of all m-ary operational symbols from Σ we shall use the notation Σ_{m} (m ≥ 0). By a Σ-algebra we mean a pair 𝔄 = (A, {σ^{𝔄} | σ ∈ Σ}), where σ^{𝔄} is an m-ary operation on A if σ ∈ Σ_{m}. If there will be no danger of confusion then we omit the superscript 𝔄 in σ^{𝔄} and simply write 𝔄 = (A, Σ). Finally, all algebras considered in this paper will be finite, i.e. A is finite and Σ is a ranked alphabet.

A rank type is a nonvoid set R of nonnegative integers. A set Σ of operational symbols is of rank type R if {m | Σ_{m} ≠ ∅} = R. An algebra 𝔄 = (A, Σ) is of rank type R if Σ is of rank type R. To avoid technical difficulties, we shall suppose that 0 ∉ R for all rank types R considered in this paper. It is also assumed that none of the sets of operational symbols contains any 0-ary symbol.

1991 Mathematics Subject Classification: Primary 68Q70.

Supported by the Hungarian National Foundation for Scientific Research under Grant T 014888 and by the Ministry of Culture and Education of Hungary under Grant FKFP 0704/1977.

Let Ξ be a set of variables. The set T_{Σ}(Ξ) of ΣΞ-trees is defined as follows:

(i) Ξ ⊆ T_{Σ}(Ξ), (ii) σ(p_{1}, …, p_{m}) ∈ T_{Σ}(Ξ) whenever m > 0, σ ∈ Σ_{m} and p_{1}, …, p_{m} ∈ T_{Σ}(Ξ), and (iii) every ΣΞ-tree can be obtained by applying the rules (i) and (ii) a finite

number of times.

In the sequel Ξ will stand for the countable set {ξ_{1}, ξ_{2}, …} and for every m > 0, Ξ_{m} will denote the subset {ξ_{1}, …, ξ_{m}} of Ξ. The subset of T_{Σ}(Ξ_{m}) consisting of all trees in which each ξ_{i} (1 ≤ ξ_{i} ≤ m) occurs exactly once will be denoted by T̂_{Σ}(Ξ_{m}). Moreover, if Σ = Σ_{1} then the elements of T_{Σ}(Ξ_{1}) will be called also words in analogy with classical automata theory.

If p ∈ T_{Σ}(Ξ_{l}) and p_{1}, …, p_{l} ∈ T_{Σ}(Ξ_{m}) are trees, then p(p_{1}, …, p_{l}) ∈ T_{Σ}(Ξ_{m}) is the tree obtained by replacing each occurrence of ξ_{i} (i = 1, …, l) in p by p_{i}. Moreover, if for Σ = Σ_{1} , p ∈ T_{Σ}(Ξ_{1}) can be given in the form p = q(r) (q, r ∈ T_{Σ}(Ξ_{1})) then q is a suffix of p.

Let 𝔄 = (A, Σ) be an algebra and p ∈ T_{Σ}(Ξ_{n}) a tree for a positive integer n. The mapping p^{𝔄}: A^{n} → A is defined in the following way. For an arbitrary a = (a_{1}, …, a_{n}) ∈ A^{n},

(i) if p = x_{i} (1 ≤ i ≤ n), then p^{𝔄}(a) = a_{i}, (ii) if p = σ(p_{1}, …, p_{m}) (σ ∈ Σ_{m}, p_{1}, …, p_{m} ∈ T_{Σ}(Ξ_{n})), then

p^{𝔄}(a) = σ^{𝔄}(p_{1}^{𝔄}(a), …, p_{m}^{𝔄}(a)).

A tree recognizer is a system A = (𝔄, a, A′), where

(i) 𝔄 = (A, Σ) is an algebra, (ii) a ∈ A^{n} is the initial vector for some positive integer n, (iii) A′ ⊆ A is the set of final states.

The forest T (A) recognized by A consists of all trees p ∈ T_{Σ}(Ξ_{n}) for which p(a) ∈ A′.

Classical recognizers are special tree recognizers. Namely, if in the above definition Σ = Σ_{1} and n = 1, then 𝔄 is a finite state recognizer and every finite state recognizer can be obtained this way.

Let R be a rank type and take the algebras 𝔄_{i} = (A_{i}, Σ^{(i)}) (i = 1, …, k > 0) with rank type R, and let

φ = {φ_{m} : (A_{1} × … × A_{k})^{m} × Σ_{m} → Σ_{m}^{(1)} × ⋯ × Σ_{m}^{(k)} | σ ∈ Σ_{m}, m ∈ R}

be a family of mappings, where Σ is an arbitrary ranked alphabet of rank type R. Then by the product of 𝔄_{1}, …, 𝔄_{k} with respect to Σ and φ we mean the algebra 𝔄 = (A, Σ) with A = A_{1} × ⋯ × A_{k} such that for arbitrary σ ∈ Σ_{m} (m ∈ R) and (a_{11}, …, a_{1k}), …, (a_{m1}, …, a_{mk}) ∈ A,

\begin{matrix}σ^{𝔄}((a_{11}, …, a_{1k}), …, & (a_{m1}, …, a_{mk})) \\ = (σ_{1}^{𝔄_{1}}(a_{11}, …, a_{m1}), …, σ_{k}^{𝔄_{k}}(a_{1k}, …, a_{mk})), \end{matrix}

where (σ_{1}, …, σ_{k}) = φ_{m}((a_{11}, …, a_{1k}), …, (a_{m1}, …, a_{mk}), σ) (see [13]).

For this product we use the notation 𝔄 = (𝔄_{1} ×⋯×𝔄_{k})[Σ, φ]. If 𝔄_{1} = ⋯ = 𝔄_{k} = 𝔅 then we speak of a power of 𝔅 and write 𝔄 = (𝔅^{n})[Σ, φ].

Obviously, in the above definition of the product, and in its generalizations to be considered in this paper, φ_{m} can be given in the form

φ_{m}((a_{11}, …, a_{1k}), …, (a_{m1}, …, a_{mk}), σ)
= (φ_{m}^{(1)}((a_{11}, …, a_{1k}), …, (a_{m1}, …, a_{mk}), σ), …,
φ_{m}^{(k)}((a_{11}, …, a_{1k}), …, (a_{m1}, …, a_{mk}), σ)),

where φ_{m}^{(i)}: A_{1} × ⋯ × A_{k} × Σ_{m} → Σ_{m}^{(i)} (i = 1, …, k) are suitable functions. If for each i (1 ≤ i ≤ k), every φ_{m}^{(i)} may depend only on elements from algebras 𝔄_{1}, …, 𝔄_{i−1} , then we speak of a cascade product. In this case sometimes we shall indicate only those arguments of φ_{m}^{(i)} on which it may depend, i.e. we write

φ_{m}^{(i)}(a_{11}, …, a_{1i−1}, …, a_{m1}, …, a_{mi−1}, σ)

for

φ_{m}^{(i)}((a_{11}, …, a_{1k}), …, (a_{m1}, …, a_{mk}), σ).

The concept of the product can be generalized in such a way that the inputs of the component algebras are trees. For this we use the name generalized product.

Let 𝔄_{i} = (A_{i}, Σ_{i}) (i = 1, …, k > 0) be arbitrary algebras, and

\begin{matrix}φ = \{ & φ_{m}: (A_{1} × ⋯ × A_{k})^{m} × Σ_{m} → \\ T_{Σ_{1}}(Ξ_{m}) × ⋯ × T_{Σ_{k}}(Ξ_{m}) | σ ∈ Σ_{m}, m ∈ R\} \end{matrix}

a family of mappings, where Σ is an arbitrary ranked alphabet. Then by the generalized product of 𝔄_{1}, …, 𝔄_{k} with respect to Σ and φ we mean the algebra 𝔄 = (A, Σ) with A = A_{1} × ⋯ × A_{k} such that for arbitrary σ ∈ Σ_{m} (m ∈ R) and (a_{11}, …, a_{1k}), …, (a_{m1}, …, a_{mk}) ∈ A,

\begin{aligned}σ^{𝔄} & ((a_{11}, …, a_{1k}), …, (a_{m1}, …, a_{mk})) \\ & = (p_{1}^{𝔄_{1}}(a_{11}, …, a_{m1}), …, p_{k}^{𝔄_{k}}(a_{1k}, …, a_{mk})), \end{aligned}

where (p_{1}, …, p_{k}) = φ_{m}((a_{11}, …, a_{1k}), …, (a_{m1}, …, a_{mk}), σ).

For the generalized product we shall use the same notation as for the product. Moreover, the generalized power, the generalized cascade product and the generalized cascade power together with their notations are given in a natural way.

It has been shown that a special type of the generalized product, the so called quasi-product is powerful enough to represent algebras. A generalized product 𝔄 = (𝔄_{1} × ⋯ × 𝔄_{k})[Σ, φ] is a quasi-product if in

(p_{1}, …, p_{k}) = φ_{m}((a_{11}, …, a_{1k}), …, (a_{m1}, …, a_{mk}), σ)

every p_{j} (1 ≤ j ≤ k) is of the form σ_{j}(ξ_{j_{1}}, …, ξ_{j_{t_{j}}}) (1 ≤ j_{1}, …, j_{t_{j}} ≤ m). Therefore, the quasi-product is that slight generalization of the product when in the inputs of the component algebras permutations and identifications of variables are allowed.

Again, the quasi-power, the quasi-cascade-product, the quasi-cascade-power, and the corresponding notations are given in an obvious way.

The aim of the structure theory of tree automata is to represent tree recognizers by means of compositions of algebras. Among the representations homomorphism and isomorphism are most frequently used. It has been shown (see [3]) that we can confine ourselves to the homomorphic and isomorphic representations of the underlying algebras of recognizers.

Let composition mean any of the products introduced in this paper. Moreover, let 𝒦_{1} and 𝒦_{2} be two classes of algebras. We say that 𝒦_{1} is homomorphically (isomorphically) complete for 𝒦_{2} with respect to the composition if every algebra from 𝒦_{2} can be given as a homomorphic (isomorphic) image of a subalgebra of a composition of algebras from 𝒦_{1} .

Finally, we introduce some operators on classes of algebras. If 𝒦 is a class of algebras, then

– S(𝒦 ) is the class of all subalgebras of algebras from 𝒦 ,

– H(𝒦 ) is the class of all homomorphic images of algebras from 𝒦 ,

– Q(𝒦 ) is the class of all quasi-cascade-products of algebras from 𝒦 . For notions and notations not defined here, see [5].

2. Nilpotent automata

A unary algebra 𝔄 = (A, Σ) is said to be nilpotent if there are an element a ∈ A, the absorbent element of 𝔄, and a nonnegative integer k such that p(b) = a for all b ∈ A and p ∈ T_{Σ}(Ξ_{1}) with h(p) ≥ k. Moreover, an automaton A = (𝔄, a_{0}, A′) is nilpotent if 𝔄 is nilpotent. Finally, a language T ⊆ T_{Σ}(Ξ_{1}) is nilpotent if T = T (A) for a nilpotent automaton A.

The following result gives a characterization of nilpotent automata by means of Boolean operations.

Theorem 1. A language is nilpotent if and only if it can be obtained from the empty language and one-element languages by forming union and complementation.

There is also a set theoretic characterization of nilpotent languages.

Theorem 2. A language T is nilpotent if and only if T or the complement of T is finite.

Finally, we recall a semigroup theoretic characterization of nilpotent languages.

Theorem 3. A language is nilpotent if and only if its syntactic semigroup is nilpotent.

The concept of nilpotent automata has been generalized to tree automata in a natural way (see [4]).

A Σ-algebra 𝔄 = (A, Σ) is nilpotent if there are an a ∈ A and a nonnegative integer k such that p(a) = a for all p ∈ T_{Σ}(Ξ_{n}), n > 0, and a ∈ A^{n}, whenever h(p) ≥ k. Moreover, a tree automaton A = (𝔄, a, A′) is nilpotent if 𝔄 is nilpotent. Finally, a tree language T ⊆ T_{Σ}(Ξ_{n}) is nilpotent if T = T (A) for a nilpotent tree automaton A.

A result analogous to Theorem 2 can be easily obtained for tree automata. Here we give a structural characterization of the class of nilpotent algebras by means of quasi-cascade-products of unary algebras. For this, let 𝒩_{1} denote the class of all nilpotent unary algebras.

Theorem 4. A Σ-algebra 𝔄 = (A, Σ) is nilpotent if and only if

𝔄 ∈ H(S(Q(𝒩_{1}))).

Proof. It is easy to see that any quasi-product of nilpotent algebras is nilpotent. Moreover, the formation of subalgebras and homomorphic images preserves nilpotency. Therefore, the conditions of Theorem 4 are sufficient.

To prove the necessity, take a nilpotent Σ-algebra 𝔄 = (A, Σ) with n elements. The case n = 1 being trivial, let n > 1. We may assume that A = {1, …, n}. Moreover, since A is finite, we may suppose that σ^{𝔄}(i_{1}, …, i_{m}) ≥ i_{1}, …, i_{m} for all σ ∈ Σ_{m}, m > 0, and i_{1}, …, i_{m} ∈ A. (Observe, that i ≤ p(i_{1}, …, i_{j−1}, i, i_{j+1}, …, i_{m}) (i_{1}, …, i_{j−1}, i, i_{j+1}, …, i_{m} ∈ A, m > 0, 1 ≤ i ≤ m, p ∈ T̂_{Σ}(Ξ_{m})) is a partial ordering on A.) Thus, n is the absorbent element of 𝔄. Take a (unary) algebra 𝔅 = (B, \overline{Σ}) from 𝒩_{1} with B = \{1, …, n\} such that for every pair (i, j) satisfying 1 ≤ i < j ≤ n there is a σ^{(i,j)} ∈ \overline{Σ} such that σ^{(i,j)}(i) = j. Furthermore, suppose that there is a symbol σ^{(n)} ∈ \overline{Σ} for which σ^{(n)}(i) = n for all i (= 1, …, n). Let us define the quasi-power ℭ = (C, Σ) = (𝔅^{n})[Σ, φ] in the following way. First of all, for each i (1 ≤ i ≤ n) let c_{i} = (c_{i1}, …, c_{in}) be the element of C for which

c_{ij} = \{ \begin{matrix}n, & if 1 ≤ j < i, \\ i, & if j = i, …, n. \end{matrix}

Denote by C′ the set of all such elements c_{i} (i = 1, …, n). Now for all m > 0, σ ∈ Σ_{m}, and c_{i_{1}}, …, c_{i_{m}} ∈ C′, let φ_{m}^{(1)}(σ) = σ^{(n)}(ξ_{1}). Moreover, if 1 < j ≤ n, then φ_{m}^{(j)}(c_{i_{1}}, …, c_{i_{m}}, σ) is given as follows:

φ_{m}^{(j)}(c_{i_{1}}, …, c_{i_{m}}, σ) = \{ \begin{matrix}σ^{(n)}(ξ_{1}), & if σ^{𝔄}(c_{i_{1}j−1}, …, c_{i_{m}j−1}) = u and j < u, \\ σ^{c_{i_{1}j−1},u}(ξ_{1}), & if σ^{𝔄}(c_{i_{1}j−1}, …, c_{i_{m}j−1}) = u and j ≥ u. \end{matrix}

In all other cases φ is given arbitrarily in accordance with the definition of the quasi-cascade-product. It is obvious that ℭ is a quasi-cascade-power of 𝔅.

We show that if σ^{𝔄}(i_{1}, …, i_{m}) = u, then we have for σ^{ℭ}(c_{i_{1}}, …, c_{i_{m}}) = c = (c_{1}, …, c_{n})

c_{j} = \{ \begin{matrix}n, & if 1 ≤ j < u, \\ u, & if u ≤ j ≤ n. \end{matrix}

Clearly, u > 1. If u = n and max(i_{1}, …, i_{m}) = n then c_{1} = ⋯ = c_{n} = n obviously holds. If u = n and max(i_{1}, …, i_{m}) = i_{t} < n (1 ≤ t ≤ m), then (I) c_{1} = ⋯ = c_{i_{t}} = n since c_{i_{t}1} = ⋯ = c_{i_{t}i_{t}−1} = n whenever i_{t} > 1; thus,

φ_{m}^{(j)}(c_{i_{1}}, …, c_{i_{m}}, σ) = σ^{(n)}(ξ_{1}) for all j = 1, …, i_{t}. (II) c_{i_{t}+1} = ⋯ = c_{n−1} = n since for every t (i_{t} ≤ t < n−1), c_{i_{1}t} = i_{1}, …, c_{i_{m}t} =

i_{m}, σ^{𝔄}(i_{1}, …, i_{m}) = n; thus, φ_{m}^{(j)}(c_{i_{1}}, …, c_{i_{m}}, σ) = σ^{(n)}(ξ_{1}) for all j (i_{t} < j < n).

(III) c_{n} = n since c_{i_{1}n−1} = i_{1}, …, c_{i_{m}n−1} = i_{m}, σ^{𝔄}(i_{1}, …, i_{m}) = n; thus, φ_{n}(c_{i_{1}}, …, c_{i_{m}}, σ) = σ^{(i_{1},n)}(ξ_{1}). Next assume that u < n. Again, let max(i_{1}, …, i_{m}) = i_{t}. Obviously, i_{t} < u.

Then

(i) c_{1} = ⋯ = c_{i_{t}} = n since if i_{t} > 1 then c_{i_{t}1} = ⋯ = c_{i_{t}i_{t}−1} = n; thus, φ_{m}^{(j)}(c_{i_{1}}, …, c_{i_{m}}, σ) = σ^{(n)}(ξ_{1}) for all j = 1, …, n.

(ii) c_{i_{t}+1} = ⋯ = c_{u−1} = n since for every r (i_{t} ≤ r < u−1), c_{i_{1}r} = i_{1}, …, c_{i_{m}r} = i_{m}, σ^{𝔄}(i_{1}, …, i_{m}) = u; thus, φ_{m}^{(j)}(c_{i_{1}}, …, c_{i_{m}}, σ) = σ^{(n)}(ξ_{1}) for all j (v < j < u).

(iii) c_{u} = ⋯ = c_{n} = u since for every r (u − 1 ≤ r ≤ n), c_{i_{1}r} = i_{1}, …, c_{i_{m}r} = i_{m}, σ^{𝔄}(i_{1}, …, i_{m}) = u; thus, φ_{m}^{(j)}(c_{i_{1}}, …, c_{i_{m}}, σ) = σ^{(i_{1},u)}(ξ_{1}) for all j = u, …, n. Thus, we have proved that C′ forms a subalgebra of ℭ which is isomorphic

to 𝔄 under the mapping τ: C′ → A given by τ(c_{i}) = i (i = 1, …, n).

From the proof of the necessity of Theorem 4 we obtain

Corollary 1. Every nilpotent algebra can be represented isomorphically by a quasi-cascade-product of unary nilpotent algebras.

3. Definite automata

A unary algebra 𝔄 = (A, Σ) is definite if there is a nonnegative integer k such that for arbitrary p ∈ T_{Σ}(Ξ_{1}) with h(p) ≥ k and a, b ∈ A we have p(a) = p(b). Moreover, an automaton A = (𝔄, a_{0}, A′) is definite if 𝔄 is definite. Finally, a language T ⊆ T_{Σ}(Ξ_{1}) is definite if there is a definite automaton A with T = T (A).

The following result holds.

Theorem 5. A language T ⊆ T_{Σ}(Ξ_{1}) is definite if and only if there is an integer k ≥ 0 such that for arbitrary two words p, q ∈ T_{Σ}(X_{1}) with h(p), h(q) ≥ k and the same suffix of length k we have p ∈ T ⇔ q ∈ T.

Definite automata and definite languages have been generalized to trees (see [7]). Before giving the definition of definite tree automata and definite tree languages, we recall the concept of the cut-off of a tree at a given height.

For every nonnegative integer k, take the binary relations ∼_{k} on T_{Σ}(Ξ_{n}) given in the following way:

(i) If k = 0, then p ∼_{0} q for all p, q ∈ T_{Σ}(Ξ_{n}). (ii) Suppose that ∼_{k} has been defined. Then for all p, q ∈ T_{Σ}(Ξ_{n}), p ∼_{k+1} q if

and only if there are a σ ∈ Σ_{m}, p_{1}, …, p_{m}, q_{1}, …, q_{m} ∈ T_{Σ}(Ξ_{n}) such that p = σ(p_{1}, …, p_{m}), q = σ(q_{1}, …, q_{m}) and p_{i} ∼_{k} q_{i} for all i = 1, …, k.

It is said that two trees p, q ∈ T_{Σ}(Ξ_{n}) have the same cut-off at height k if p ∼_{k} q.

A Σ-algebra 𝔄 = (A, Σ) is definite if there is a nonnegative integer k such that for arbitrary n > 0, a ∈ A^{n} and p, q ∈ T_{Σ}(Ξ_{n}) with h(p), h(q) ≥ k we have p(a) = q(a), whenever p and q have the same cut-off at height k. Moreover, a tree automaton A = (𝔄, a, A′) is definite if 𝔄 is definite. Finally, a tree language is definite if it can be recognized by a definite tree automaton.

The following result, which is a generalization of Theorem 5 to trees, is from [7].

Theorem 6. A tree language T ⊆ T_{Σ}(Ξ_{n}) is definite if and only if there is an integer k ≥ 0 such that for arbitrary two trees p, q ∈ T_{Σ}(Ξ_{n}) with h(p), h(q) ≥ k and the same cut-off at height k we have p ∈ T ⇔ q ∈ T.

Take a rank type R. Let Σ be a ranked alphabet having two symbols σ_{m}^{1}, σ_{m}^{2} ∈ Σ_{m} for every m ∈ R. Define the Σ-algebra 𝔄_{R} = ({1, 2}, Σ) in the following way: σ_{m}^{i}(i_{1}, …, i_{m}) = i (i = 1, 2) for all m ∈ R and i_{1}, …, i_{m} ∈ {1, 2}. It is easy to see that 𝔄_{R} is definite under k = 1.

In [2] Ésik gives the following structural characterization of definite algebras.

Theorem 7. For an algebra 𝔄 of rank type R the next statements are equivalent.

(i) 𝔄 is definite. (ii) 𝔄 can be embedded isomorphically into a cascade power of 𝔄_{R}. (iii) 𝔄 is a homomorphic image of a subalgebra of a cascade power of 𝔄_{R}.

It is not hard to see that 𝔄_{R} is isomorphic to a quasi-cascade-product of 𝔄_{{1}} with a single factor. Moreover, since the quasi-cascade-product is a special case of the generalized cascade composition, by Corollary 5 in [2], any quasi-cascade-product of definite algebras is definite. Furthermore, subalgebras and homomorphic images preserve definiteness. Finally, the formation of quasi-cascade-products is transitive. Therefore, from Theorem 7 we obtain

Theorem 8. For an algebra 𝔄 the next statements are equivalent.

(i) 𝔄 is definite. (ii) 𝔄 can be embedded isomorphically into a quasi-cascade-power of 𝔄_{{1}}. (iii) 𝔄 is a homomorphic image of a subalgebra of a quasi-cascade-power of 𝔄_{{1}}.

4. Monotone automata

Monotone automata play a distinguished role in the structure theory of finite state automata. At the same time no characterization of languages recognized by monotone automata is known. Here we introduce the concept of monotone algebras and give some structural characterization for them.

An algebra 𝔄 = (A, Σ) is monotone if a partial ordering ≤ can be given on A such that for any m > 0, σ ∈ Σ_{m}, and a_{1}, …, a_{m} ∈ A we have σ(a_{1}, …, a_{m}) ≥ a_{1}, …, a_{m}. Observe, that every nilpotent algebra is monotone. Theorem 9, the proof of which is trivial, shows that monotonicity can be reduced to unary algebras.

Let 𝔄 = (A, Σ) be an algebra. Moreover, let 𝔄̄ = (A, Σ^{(𝔄)}) be the algebra where Σ^{(𝔄)} = Σ_{1}^{(𝔄)} consists of all σ(a_{1}, …, a_{i−1}, ξ_{1}, a_{i+1}, …, a_{m}) (m > 0, 1 ≤ i ≤ m, σ ∈ Σ_{m}, a_{1}, …, a_{i−1}, a_{i+1}, …, a_{m} ∈ A), and for each a ∈ A,

σ̄𝔄̄(a) = σ^{𝔄}(a_{1}, …, a_{i−1}, a, a_{i+1}, …, a_{m})

if σ̄ = σ(a_{1}, …, a_{i−1}, ξ_{i}, a_{i+1}, …, a_{m}). In other words, the operations of \overline{𝔄} are all the elementary translations of 𝔄.

Theorem 9. An algebra 𝔄 = (A, Σ) is monotone if and only if the unary algebra \overline{𝔄} = (A, Σ^{(𝔄)}) is monotone.

We shall need the following result, too.

Lemma 1. Homomorphism preserves monotonicity of algebras.

Proof. Let 𝔄 = (A, Σ) and 𝔅 = (B, Σ) be algebras and τ: A → B a homomorphism of 𝔄 onto 𝔅. Assume that 𝔄 is monotone under the partial ordering ≤. Let us define the relation ϱ_{𝔄} on A by aϱ_{𝔄}p^{\overline{𝔄}}(a) (a ∈ A, p ∈ T_{Σ^{(𝔄)}}(Ξ_{1})). It is clear that ϱ_{𝔄} is reflexive and transitive. Moreover, ϱ_{𝔄} ⊆≤. Therefore, ϱ_{𝔄} is a partial ordering and \overline{𝔄} is monotone under ϱ_{𝔄}. Assume that the corresponding binary relation ϱ_{𝔅} is not a partial ordering on B. Then there are an element b ∈ B and two words p̄, q̄ ∈ T_{Σ^{(𝔄)}}(Ξ_{1}) such that q̄^{\overline{𝔅}}(b) ≠ b and (p̄(q̄))^{\overline{𝔅}}(b) = b. Let p̄(ξ_{1}) = p(b_{11}, …, b_{1m−1}, ξ_{1}) and q̄(ξ_{1}) = q(b_{21}, …, b_{2n−1}, ξ_{1}) (p ∈ T̂_{Σ}(Ξ_{m}), q ∈ T̂_{Σ}(Ξ_{n}), b_{11}, …, b_{1m−1}, b_{21}, …, b_{2n−1} ∈ B). Let a_{11}, …, a_{1m−1}, a_{21}, …, a_{2n−1} be counter images of b_{11}, …, b_{1m−1}, b_{21}, …, b_{2n−1} , respectively. Moreover, let \overline{\overline{p}} (ξ_{1}) = p(a_{11}, …, a_{1m−1}, ξ_{1}) and \overline{\overline{q}} (ξ_{1}) = q(a_{21}, …, a_{2n−1}, ξ_{1}). For an arbitrary tree t(ξ_{1}) ∈ T_{Σ^{(𝔄)}}(Ξ_{1}) let t^{0} = ξ_{1} and t^{i} = t(t^{i−1}(ξ_{1})) if i > 0. Let a be a counter image of b under τ. Since τ is a homomorphism, (\overline{\overline{p}} (\overline{\overline{q}}))^{i}(a) = b for every i(= 0, 1, …). Moreover, due to the finiteness of A, there are integers i and j such that i < j and (\overline{\overline{p}} (\overline{\overline{q}}))^{i}(a) = (\overline{\overline{p}} (\overline{\overline{q}}))^{j}(a). Furthermore, since q̄(b) ≠ b, \overline{\overline{q}} ((\overline{\overline{p}} (\overline{\overline{q}}))^{i})(a) ≠ (\overline{\overline{p}} (\overline{\overline{q}}))^{i}(a). Therefore, ϱ_{𝔄} is not a partial ordering on A, which is a contradiction. Thus, we have obtained that ϱ_{𝔅} is a partial ordering on B and \overline{𝔅} is a monotone unary algebra under ϱ_{𝔅} which, by Theorem 9, implies that 𝔅 is a monotone algebra.

Let R be a rank type and let Σ be a ranked alphabet of rank type R. An algebra 𝔄 = (A, Σ) with A = {1, 2} is a two-state full monotone algebra of rank type R if for all integers m ∈ R and mappings τ: A^{m} → A with τ(a_{1}, …, a_{m}) ≥ a_{1}, …, a_{m} (a_{1}, …, a_{m} ∈ A), there is a σ ∈ Σ_{m} such that σ^{𝔄} = τ.

We have

Theorem 10. An algebra 𝔄 = (A, Σ) of rank type R is monotone if and only if it can be given as a homomorphic image of a subalgebra of a cascade power of a two-state full monotone algebra of rank type R.

Proof. It is obvious that products and subalgebras of monotone algebras are monotone. Moreover, by Lemma 1, homomorphism preserves monotonicity.

Conversely, let 𝔄 = (A, Σ) be a monotone algebra of rank type R under a partial ordering ≤. Since A is finite, we may assume that ≤ is a linear ordering. For the sake of simplicity, suppose that A = {1, …, n} and ≤ is the natural ordering on A. Let 𝔅 = ({1, 2}, Σ′) be a two-state full monotone algebra of rank type R. If n = 2 then 𝔄 is obviously isomorphic to a cascade power of 𝔅 with a single factor. Assume that n > 2. We shall show that there is an algebra 𝔄′ = (A′, Σ) with n − 1 states 1, …, n − 1 such that 𝔄′ is monotone under the natural ordering on A′ and 𝔄 is a homomorphic image of a subalgebra of a cascade product ℭ = (C, Σ) = (𝔄′ × 𝔅)[Σ, φ]. For arbitrary m ∈ R, σ ∈ Σ_{m}, and i_{1}, …, i_{m} ∈ A′, let

σ^{𝔄′}(i_{1}, …, i_{m}) = \{ \begin{matrix}σ^{𝔄}(i_{1}, …, i_{m}), & if σ^{𝔄}(i_{1}, …, i_{m}) < n, \\ n − 1 & otherwise. \end{matrix}

For every m ∈ R, let σ′_{m1} ∈ Σ′_{m} be the symbol satisfying σ′_{m1}^{𝔅}(1, …, 1) = 1. Moreover, σ′_{m2} ∈ Σ′_{m} will denote a symbol such that σ′_{m2}^{𝔅}(i_{1}, …, i_{m}) = 2 for arbitrary i_{1}, …, i_{m} ∈ {1, 2}. Now we are ready to define the feed-back function φ of ℭ. For every σ ∈ Σ_{m}, let φ_{m}^{(1)}(σ) = σ. Furthermore, for all σ ∈ Σ_{m} and i_{1}, …, i_{m} ∈ {1, …, n − 1}, let

φ_{m}^{(2)}(i_{1}, …, i_{m}, σ) = \{ \begin{matrix}σ_{m1}, & if σ(i_{1}, …, i_{m}) < n, \\ σ_{m2} & otherwise. \end{matrix}

Denote by C′ the subset {(1, 1), …, (n − 1, 1), (n − 1, 2)} of C. It is not hard to show that C′ forms a subalgebra of ℭ and the mapping τ: C′ → A given by

τ((i, j)) = \{ \begin{matrix}i, & if j = 1, \\ n, & if j = 2 \end{matrix}

((i, j) ∈ C′) is an isomorphism. Since the formation of the cascade product is transitive, this ends the proof of Theorem 10.

From the proof of Theorem 10 we obtain

Corollary 2. An algebra of rank type R is monotone if and only if it is isomorphic to a subalgebra of a cascade power of a two-state full monotone algebra of rank type R.

Let 𝔄 = (A, Σ′) be the algebra with A = {1, 2} and Σ = Σ_{1} = {σ_{1}, σ_{2}}, where σ_{1}(1) = 1, σ_{1}(2) = 2 and σ_{2}(1) = σ_{2}(2) = 2. The algebra 𝔄 is a twostate full monotone algebra of rank type R = {1}. This, by Theorem 10, means that every unary monotone algebra can be given as a homomorphic image of a subalgebra of a cascade power of 𝔄. We shall give a two-state monotone algebra which cannot be represented homomorphically by a quasi-cascade-power of 𝔄. Therefore, since the formation of the quasi-cascade-product is transitive, this will imply that not every monotone algebra can be given as a homomorphic image of a subalgebra of a quasi-cascade-product of unary monotone algebras.

Consider the algebra 𝔅 = (B, Σ), where B = {1, 2}, Σ = Σ_{2} = {σ}, σ(1, 1) = 1 and σ(1, 2) = σ(2, 1) = σ(2, 2) = 2. This 𝔅 is a monotone algebra.

Take a quasi-cascade-power ℭ = (C, Σ) = (𝔄^{n})[Σ, φ]. Assume that a subalgebra ℭ′ = (C′, Σ) of ℭ can be mapped homomorphically onto 𝔅 under a mapping τ: C′ → B. Let N denote the set of all elements c from C′ for which τ(c) = 1 and σ(c, c) = c. Then N is nonvoid since ℭ′ is monotone and σ^{𝔅}(1, 1) = 1. Furthermore, let N_{2} be the set of all counter images of 2 under τ. Finally, let i (1 ≤ i ≤ n) denote the maximal index for which there is a pair (a, b),

a = (j_{11}, …, j_{1i−1}, j_{1i}, j_{1i+1}, …, j_{1n}) ∈ N and

b = (j_{21}, …, j_{2i−1}, j_{2i}, j_{2i+1}, …, j_{2n}) ∈ N_{2} ,

such that j_{11} = j_{21}, …, j_{1i−1} = j_{2i−1} and j_{1i} ≠ j_{2i}. Let us distinguish the following two cases.

(1) j_{1i} = 1 and j_{2i} = 2. Then φ_{2}^{(i)}(j_{11}, …, j_{1i−1}, j_{11}, …, j_{1i−1}, σ) = σ_{1}(ξ_{1}) or σ_{1}(ξ_{2}) since σ(a, a) = a. In the first case the ith component of σ(a, b) is 1 and σ(a, b) ∈ N_{2} . This contradicts either the maximality of i, or the assumption that τ is a homomorphism if i = n. In the second case, taking σ(b, a), we arrive at the same conclusion.

(2) j_{1i} = 2 and j_{2i} = 1. Now for φ_{2}^{(i)}(j_{11}, …, j_{1i−1}, j_{11}, …, j_{1i−1}, σ) we may have all four cases: φ_{2}^{(i)}(j_{11}, …, j_{1i−1}, j_{11}, …, j_{1i−1}, σ) = σ_{1}(ξ_{1}), or σ_{1}(ξ_{2}), or σ_{2}(ξ_{1}), or σ_{2}(ξ_{2}). Taking σ(a, b) in the first case and σ(b, a) in the remaining three cases, we have the same contradiction as previously.

Let ℳ_{1} denote the class of all monotone unary algebras and ℳ the class of all monotone algebras. We can summarize the above result in

Theorem 11. ℳ_{1} is not homomorphically complete for ℳ with respect to the quasi-cascade-product.

Finally, we remark that ℳ and H(S(Q(ℳ_{1}))) are incomparable.

References

[1] Brzozowski, J.A.: Canonical regular expressions and minimal state graphs for definite events. - In: Proc. Symp. Math. Theory of Automata, Brooklyn, 1962, 529–562.

[2] Ésik, Z.: Definite tree automata and their cascade compositions. - Publ. Math. 48, 1996, 243–261.

[3] Gécseg, F.: On homomorphic representations by products of tree automata. - In: Results and Trends in Theoretical Computer Science, Proceedings of a symposium held in Graz in 1994, Lecture Notes in Comput. Sci. 812, Springer-Verlag, 131–139.

[4] Gécseg, F., and B. Imreh: On a special class of tree automata. - In: 2nd Conf. on Automata, Languages and Programming Systems, Salgótarján, 1988, 141–152.

[5] Gécseg, F., and M. Steinby: Tree Automata. - Akadémiai Kiadó, Budapest, 1984.

[6] Ginzburg, A.: About some properties of definite, reverse-definite events, and related automata. - IEEE Trans. Electronic. Comput. 15, 1966, 806–810.

[7] Heuter, U.: Definite tree languages. - EATCS Bulletin 35, 1988, 137–142.

[8] Kaphengst, H.: Axiomatizable classes of automata. - Voprosy teoretičeskoĭ kibernetiki, Kiev, 1965, 6–30 (Russian).

[9] Paz, A., and B. Peleg: Ultimate-definite and symmetric definite events and automata. - J. Assoc. Comput. Mach. 12, 1965, 399–410.

336 Ferenc Gécseg

[10] Perles, M., M.O. Rabin, and E. Shamir: The theory of definite automata. - IEEE Trans. Electronic Comput. 12, 1963, 233–243.

[11] Salomaa, A.: Two complete axiom systems for the algebra of regular events. - J. Assoc. Comput. Mach. 13, 1966, 158–169.

[12] S̆evrin, L.N.: On some classes of abstract automata. - Uspekhi Mat. Nauk 17:6, 1962, 219 (Russian).

[13] Steinby, M.: On the structure and realization of tree automata. - In: 2^{e} Colloque sur les arbres en algèbre et en programmation, Lille, 1977, 235–248.

[14] Steinby, M.: A theory of tree language varieties. - In: Tree Automata and Languages, Elsevier Science Publishers, 1992, 57–81.

Received 11 August 1998