PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 64 (78), 1998, 165–182

THE LATTICE OF SUBAUTOMATA OF AN AUTOMATON: A SURVEY

M. Ćirić, S. Bogdanović and T. Petković

Communicated by Žarko Mijajlović

Abstract. We the main results concerning the properties of the lattice of subautomata of an automaton. We characterize certain significant types of elements and the center of that lattice and describe its direct sum decompositions. We also show how the properties of this lattice can be used in studying of direct sum decompositions of an automaton, and finally, we treat the problem of representation of lattices as lattices of subautomata of certain types of automata.

1. Introduction

From its very beginning, the theory of automata, especially the algebraic one, was based on numerous algebraic ideas and methods. There are two main reasons for this. The first is the fact that automata without outputs, and hence the automata without outputs belonging to arbitrary automata, can be treated as algebras whose all fundamental operations are unary, that is as unary algebras. Of course, the opposite statement also holds, that is any unary algebra can be treated as an automaton. This makes possible to investigate automata from the aspect of Universal algebra and to use its ideas, methods and results. On the other hand, many investigations in the theory of automata have their fundamentals in the theory of semigroups. Relationships between automata and semigroups, which one realizes through input, output and transition semigroups of automata, were shown oneself to be very useful in many investigations in the theory of automata and the theory of formal languages.

The third algebraic approach to automata, that we present here, is not much used in Theory of automata, although it has been widely used in other algebraic theories. This is the lattice-theoretical approach to studying algebras, which includes studying of lattices of subalgebras, lattices of congruences, lattices of varieties, representations of abstract lattices by such lattices and so on. In this paper we will deal with the lattices of subautomata of automata (for the results concerning lattices of congruences of automata we refer to the Saliĭ’s book [41]).

AMS Subject Classification (1991): 68Q70, 08A60, 08A70, 06A23 Supported by Grant 04M03B of RFNS through Math. Inst. SANU

In Section 2 treat about some fundamental concepts of lattice theory, and automata theory. In Section 3 we present certain basic properties of the lattice of subautomata of an automaton: we describe its completely join and meet irreducible elements, its atoms and dual atoms etc. Section 4 deals with the center of the lattice of subautomata. We show that it consists of filters of an automaton, that it is a complete atomic Boolean algebra, and we give two algorithms for finding its atoms. The next section, Section 5, presents the connections which exist between the lattice of subautomata of an automaton and its direct sum decompositions. Two central places of the whole paper are Theorem 5.3, which describes the lattice of all direct sum decompositions of an automaton through the Boolean algebra of its filters, and Theorem 5.4, which says that every automaton can be represented as a direct sum of direct sum indecomposable automata and that the summands in such a decomposition are the atoms of the Boolean algebra of the filters of the given automaton. We also give various characterizations of automata decomposable into a direct sum of strongly connected automata. In Section 6 we collect the results that give some relationships between the lattice of subautomata of an automaton and the lattice of positive quasi-orders on it, and in Section 7 we give a connection between direct sum decompositions of an automaton and decompositions of its lattice of subautomata into a direct product. In the last section, Section 8, we present several theorems that give representations of certain lattices through the lattices of subautomata of automata.

Some of the results presented in Section 3 were also given in the Saliĭ’s book [41]. In Sections 4–7 we present the results of the authors published in [14] and [17]. The results given in Section 8 are mainly the results of Johnson and Seifert from [31], and they are taken from the book of Jónsson [32].

2. Preliminaries

In this section we deal with some important concepts of lattice theory and automata theory that will be used in the paper.

Throughout the paper, ℕ will denote the set of all positive integers, the notion of poset will be used as a synonym for the notion “partially ordered set” and L will stand for a complete lattice. The zero and the unity of L will be denoted by 0 and 1, respectively.

A sublattice K of L is called a 0-sublattice (resp. a 1-sublattice) of L if 0 ∈ K (resp. 1 ∈ K), and it is a 0,1-sublattice of L if both 0 ∈ K and 1 ∈ K. A subset K of L is called a complete meet-subsemilattice (resp. join-subsemilattice) of L if it contains the meet (resp. the join) of each its non-empty subset, and it is a complete sublattice of L if it is both complete meet- and join-subsemilattice of L. The set of all complete 0,1-sublattices of L, partially ordered by the set inclusion, is also a complete lattice, and it is denoted by CS(L). A non-empty subset K of L is defined to be directed if any finite subset of K has a upper bound in K. A non-empty subset K of L is join-dense in L if any element of L is the join of some subset of K. A subset K of L will be called an order ideal of L if for all a, b ∈ L, b ∈ K and a ≤ b implies a ∈ K. Dually we define dual order ideals.

An element a ∈ L is called an atom of L, if 0 < a and there exists no x ∈ L such that 0 < x < a. An element a ∈ L is called completely join irreducible if a ≠ 0 and for every subset K of L, a = ⋁ K implies a ∈ K. Dually we define completely meet irreducible elements of L. The set of all completely join irreducible elements of L will be denoted by CJI(L), and the set of all completely meet irreducible elements of L will be denoted by CMI(L).

A mapping φ of L into itself is called extensive, if a ≤ aφ, for any a ∈ L, isotone, if for all a, b ∈ L, a ≤ b implies aφ ≤ bφ, and idempotent, if φ^{2} = φ, i.e. if (aφ)φ = aφ, for each a ∈ L. An extensive, isotone and idempotent mapping of L into itself is called a closure operator on L. An element a ∈ L is called closed (with respect to φ) if aφ = a. The set of all closed elements with respect to a closure operator φ on L is a closure system on L, where by a closure system in L we mean any complete meet-subsemilattice of L containing the unity of L. As it is well known (see [39] and [1]), any closure system on L determines a unique closure operator on L, i.e. there is a bijective correspondence between closure operators on L and closure systems in L. In the case L = P (U), where P (U) denotes the Boolean algebra of all subsets of a non-empty set U, closure systems in L are also called closure systems on U. They are also known as Moore families or intersection structures on U.

There are two important special types of closure operators and closure systems. As it is well known, any closure operator on L preserves all meets in L, but in the general case it does not preserve the joins in L. If a closure operator φ on L preserves the joins of directed subsets of L. i.e. if (⋁_{i∈I} a_{i})φ = ⋁_{i∈I}(a_{i}φ), for each directed subset {a_{i} | i ∈ I} of L, then it is called an algebraic closure operator on L, and if it preserves the joins of all non-empty subsets of L, i.e. if (⋁_{i∈I} a_{i})φ = ⋁_{i∈I}(a_{i}φ), for each non-empty subset {a_{i} | i ∈ I} of L, then it is called a complete closure operator on L. Similarly, a closure system C in L is called an algebraic closure system if it contains the join of any its directed subset, whereas it is called a complete closure system if it contains the join of any its non-empty subset. The bijective correspondence mentioned above gives also bijective correspondences between algebraic closure operators and systems, and between complete closure operators and systems. As it is well known, algebraic closure operators and algebraic closure systems play a crucial role in the representation of lattices as lattices of subalgebras of algebras and lattices of congruences on algebras (see, for example, [2], [28], [26] and [32]).

A subset K of a complete Boolean algebra B is called a complete Boolean subalgebra of B if it is both a Boolean subalgebra and a complete sublattice of B. The set of all complete Boolean subalgebras of L, partially ordered by set inclusion, is a complete lattice, and it is denoted by CB(B). A complete Boolean algebra B is called atomic if any non-zero element of B is the join of some family of atoms of B, i.e., if the set of all atoms of B is join-dense in B. As it is well known (see [44]), a Boolean algebra is a complete atomic Boolean algebra if and only if it can be represented as the Boolean algebra of subsets of some set.

Let B be a Boolean algebra. For a subset L of B, L′ will denote the set of complements of elements of L, that is L′ = {a′ | a ∈ L}. We see that the mapping a ↦ a′ is a dual order isomorphism of the poset L onto the poset L′, so L is a sublattice of B if and only if L′ is a sublattice, and if B is a complete Boolean algebra, then L is a complete sublattice of B if and only if L′ is a complete sublattice of B. In both of these cases L and L′ are dually isomorphic as lattices, and we will say that L and L′ are conjugated sublattices of B. For a ∈ L, a′ will be called the dual of a. If L = L′, then we say that L is a self-conjugated sublattice of B. Clearly, self-conjugated sublattices of B are exactly its Boolean subalgebras.

Let a non-empty set U and a closure system L on U be given. For a non-empty H ⊆ U, the intersection of all elements of L containing H, denoted by L(H), is the smallest element of L containing H, and it is called the element of L generated by H. For a ∈ U, L(a) is called the principal element of L generated by a. The set of all principal elements of L is called the principal part of L. It is known that for a complete sublattice L of P (U), the principal part of L coincides to the set CJI(L) of all completely join irreducible elements of L.

Finally, we introduce the notations for some important concrete lattices. Let U be a non-empty set. Recall that P (U) denotes the Boolean algebra of all subsets of a non-empty set U. By a quasi-order on U we mean any reflexive and transitive binary relation on U. The set of all quasi-orders on U, partially ordered by the usual ordering of binary relations, is a complete lattice that is denoted by Q(U) and called the lattice of quasi-orders on U. The lattice of equivalence relations on U, denoted by E(U), is a complete sublattice of Q(U). The lattice of partitions of U is defined as the dual lattice of E(U), and it is denoted by Part (U). Let A be an algebra of an arbitrary (fixed) type. The lattice of congruences on A, denoted by Con (A), is a complete sublattice of E(A). The lattice of all subalgebras of A is denoted by Sub(A).

For undefined notions and notations from lattice theory and universal algebra we refer to the books: Birkhoff [1], Burris and Sankappanavar [7], Crawley and Dilworth [19], Grätzer [26], [27], Jónsson [32] and Saliĭ [41].

Next we introduce several notions and notations concerning automata. In what follows, X is always an alphabet, but not necessarily finite. The set of all (finite) words over X, including the empty word e, is denoted by X^{∗}. With the catenation of words as the operation and the empty word as the unit element, X^{∗} is the free monoid over X. By an automaton we mean a system A = (A, X) where A is a non-empty set of states, not necessarily finite, X is its input alphabet and to each symbol x ∈ X an unary operation x^{A} on A is assigned. For any a ∈ A and x ∈ X, we write ax^{A}, or just ax, for x^{A}(a). For any word u = x_{1}x_{2} ⋯ x_{n} ∈ X^{∗}, the mapping u^{A} : A → A is defined as the composition of the mappings x_{1}^{A}, x_{2}^{A},…, x_{n}^{A}, that is to say, au^{A} = ax_{1}^{A}x_{1}^{A} ⋯ x_{n}^{A}, for each a ∈ A. In particular, e^{A} is the identity mapping on A. In order to simplify the notations, if A is known from the context, we shall write simply au instead of au^{A}, and we shall use the same letter A to denote an automaton and its set of states. Therefore, automata are defined here as algebras having only unary fundamental operations, so the notions such as a congruence, subautomaton, generating set etc., will have their usual algebraic meanings. Viewed from the aspect of automata theory, the automaton defined above behaves in the following way: under the action of an input symbol x ∈ X the automaton A goes from the state a into the state ax, and under the action of an input word u = x_{1}x_{2} ⋯ x_{n} ∈ X^{∗}, considered as a sequence of fundamental input symbols, the automaton A goes from the state a into the state au, through the sequence of states ax_{1}, ax_{1}x_{2},…, ax_{1}x_{2} ⋯ x_{n−1}. In fact, automata defined in that manner are exactly automata without outputs, as they were called in the book of Gécseg and Peák [21]. Automata with a one-element input alphabet are called autonomous automata.

For undefined notions and notations concerning automata we refer to the books: Burris and Sankappanavar [7], Gécseg and Peák [21], Howie [29], Lallement [33], Madarász and Crvenković [37], and Saliĭ [41].

3. Basic properties of the lattice of subautomata

In this section we deal with the fundamental properties of the lattices of subautomata and dual subautomata of an automaton and we describe their principal elements, completely join and meet irreducible elements and atoms. Except Theorem 3.7, all other results presented here are new.

Let an automaton A be given. For a subset H of A we say that it is a subautomaton of A if for a ∈ A and u ∈ X^{∗}, from a ∈ H it follows that au ∈ H. If we consider automata as unary algebras, then this definition is exactly the definition of subalgebras of A. The set of all subautomata of A is denoted by Sub(A).

On the other hand, a subset H of A is called a dual subautomaton of A if for a ∈ A and u ∈ X^{∗}, from au ∈ H it follows a ∈ H. The set of all dual subautomata of A is denoted by DSub(A). The empty subset of A is defined to be both a subautomaton and a dual subautomaton of A. Of course, the whole A has the same property.

The place of Sub(A) and DSub(A) inside the Boolean algebra P (A) is determined by the following theorem:

Theorem 3.1. For an arbitrary automaton A, Sub(A) and DSub(A) are complete 0,1-sublattices of P (A).

Moreover, Sub(A) and DSub(A) are conjugated sublattices of P (A).

The property of lattices of subautomata that they are complete sublattices of corresponding Boolean algebras of subsets, is a very rare property among other algebras. Namely, it is known that the lattice of subalgebras of an algebra is always a complete meet-subsemilattice of the corresponding Boolean algebra of subsets, but often it is not a complete join-subsemilattice of this Boolean algebra.

The second part of Theorem 3.1 asserts that dual subautomata of an automaton A are exactly the set-theoretical complements of subautomata of A. For a subautomaton B of A, the dual subautomaton B′ (the set-theoretical complement of B in A) is called the dual of B, and vice versa. This fact justifies the name “dual subautomaton” that we use here.

For the concept that we call here “dual subautomaton”, the authors used in [14] and [17] the name “consistent subset”. This name traces its origin to the concept of a consistent subset of a semigroup, introduced by P. Dubreil in [20], 1941. This concept was since generalized to the case of an arbitrary universal algebra, and in the book of V. M. Glushkov, G. E. Ceĭtlin and E. L. Yushchenko [24] we meet it under the name “isolated subset”. The notion that we call here “dual subautomaton” is simply a projection of this general notion to the case of automata, considered as unary algebras.

Let us consider again an automaton A. For a ∈ A we define:

\begin{aligned}S(a) & = \{b ∈ A | (∃u ∈ X^{∗}) b = au\} = \{au | u ∈ X^{∗}\}, \\ D(a) & = \{b ∈ A | (∃u ∈ X^{∗}) a = bu\}. \end{aligned}

These sets have the following property:

Theorem 3.2. Let a be a state of an automaton A. Then (a) S(a) is the principal element of Sub(A) generated by a;

(b) D(a) is the principal element of DSub(A) generated by a.

For a subset P of an automaton A set

\begin{aligned}S(P) & = ⋃_{a∈P} S(a) = \{b ∈ A | (∃a ∈ P)(∃u ∈ X^{∗}) b = au\}, \\ D(P) & = ⋃_{a∈P} D(a) = \{b ∈ A | (∃a ∈ P)(∃u ∈ X^{∗}) a = bu\}. \end{aligned}

Then S(P) is called a subautomaton of A generated by P, and D(P) is called a dual subautomaton of A generated by P. For a ∈ A, S(a) is called a principal subautomaton of A generated by a, and D(a) is called a principal dual subautomaton of A generated by a. Principal subautomata and dual subautomata have the following significant property.

Theorem 3.3. Let A be an arbitrary automaton. Then

(a) Completely join irreducible elements of Sub(A) are exactly the principal subautomata of A;

(b) Completely meet irreducible elements of Sub(A) are exactly the duals of principal dual subautomata of A.

Except the subautomata and dual subautomata, in the theory of automata we are also interested in the following kind of sets: A subset H of an automaton A is called strongly connected if for each pair a, b ∈ H there exists u ∈ X^{∗} such that au = b. The set of all strongly connected subsets of A is denoted by Scs(A). Before we describe some basic properties of this set, we present the following theorem that gives yet an other interesting relationship between principal subautomata and principal dual subautomata of an automaton.

Theorem 3.4. Let a and b be two states of an automaton A. Then

S(a) = S(b) ⇔ D(a) = D(b).

In view of this theorem we define an equivalence relation γ on an automaton A in two ways:

a γ b ⇔ S(a) = S(b)  and  a γ b ⇔ D(a) = D(b).

For a ∈ A, by G_{a} we denote the γ-class of A containing a. The γ-classes of A can be characterized as follows:

Theorem 3.5. Lee A be an automaton and a ∈ A. Then G_{a} = S(a) ∩ D(a).

Using the equivalence relation defined above we give the following theorem:

Theorem 3.6. Let A be an automaton. Then Scs(A) is an order ideal of P (A).

Furthermore, Scs(A) is the set-theoretical union of principal ideals of P (A) generated by γ-classes of A.

Strongly connected subsets are very useful when we want to characterize the atoms and the dual atoms of lattices of subautomata. This will be done by the next two theorems. The first one is taken from the Saliĭ’s book [41].

Theorem 3.7. (Saliĭ [41]) Let A be an automaton. The atoms of Sub(A) are exactly the strongly connected subautomata of A.

By another theorem we give an answer to a question asked by Saliĭ in [41] (Question II 2.2).

Theorem 3.8. Given an automaton A. The dual atoms of Sub(A) are exactly the duals of strongly connected dual subautomata of A.

The atoms and dual atoms of the lattice of subautomata can be also characterized in the following way:

Theorem 3.9. The following conditions for a subautomaton B of an automaton A are equivalent:

(i) B is an atom in Sub(A); (ii) B = S(a), for any a ∈ B; (iii) B = G_{a}, for some a ∈ A.

Theorem 3.10. The following conditions for a subautomaton B of an automaton A are equivalent:

(i) B is a dual atom in Sub(A); (ii) B′ = D(a), for any a ∈ B′; (iii) B′ = G_{a}, for some a ∈ A.

4. The center of the lattice of subautomata

In the beginning of this section we give some additional definitions. An element a of a lattice L is called neutral if

(a ∧ x) ∨ (x ∧ y) ∨ (y ∧ a) = (a ∨ x) ∧ (x ∨ y) ∧ (y ∨ a),

for all x, y ∈ L, or equivalently, if for arbitrary x, y ∈ L the sublattice of L generated by x, y and a is distributive. If L is a lattice with a zero 0 and a unity 1, the set of all neutral complemented elements of L is called a center of L, and it is denoted by C(L). It is known that, 0, 1 ∈ C(L), C(L) is a sublattice of L and a Boolean algebra. In the case when L is a distributive lattice, then C(L) consists simply of all complemented elements of L. For such lattices, the authors used in [14] and [17] the name “Boolean part” instead of the name “center”. Moreover, if L is a 0,1-sublattice of some Boolean algebra, then C(L) = L ∩ L′.

For many lattices, much information about them can be obtained from certain properties of their centers, especially in the case when the center is a complete sublattice of the given lattice. In this section we consider the center of the lattice of subautomata of an automaton.

The results that will be presented are taken from the paper [14] by Ćirić and Bogdanović. In order to characterize the center of the lattice Sub(A) of subautomata of an automaton A, they introduced the following notion: A subset H of A is said to be a filter of A if it is both a subautomaton and a dual automaton of A, that is if for a ∈ A, u ∈ X^{∗}, au ∈ H if and only if a ∈ H. The set of all filters of A is denoted by F (A). Hence, F (A) = Sub(A) ∩ DSub(A).

The first theorem that we quote here characterizes F (A):

Theorem 4.1. (Ćirić and Bogdanović [14]) Let A be an automaton. Then F (A) is the center of Sub(A), it is a complete sublattice of Sub(A) and a complete atomic Boolean algebra.

The same authors stated in [14] the question: What are the atoms of F (A)? In order to give an answer to this question, they investigated the principal elements of F (A). Namely, F (A) is a complete 0,1-sublattice of Sub(A), and hence a complete 0,1-sublattice of P (A), so for any a ∈ A we can speak about the principal element of F (A) generated by a, which is called the principal filter of A generated by a, and is denoted by F (a). Ćirić and Bogdanović obtained in [14] the following:

Theorem 4.2. (Ćirić and Bogdanović [14]) Let A be an automaton. The atoms of F (A) are exactly the principal filters of A.

Note that this theorem is a consequence of the fact that an arbitrary complete Boolean subalgebra of P (U), for a non-empty set U, is atomic and its atoms are exactly its principal elements.

Ćirić and Bogdanović gave two algorithms for finding the atoms in F (A). The first one is given by the following theorem:

Theorem 4.3. (Ćirić and Bogdanović [14]) Let A be an automaton, a ∈ A, and let the sequences {D_{n}(a)}_{n∈ℕ} and {S_{n}(a)}_{n∈ℕ} of subsets of A be defined by:

D_{1}(a) = D(S(a)), D_{n+1}(a) = D(S(D_{n}(a))), for n ∈ ℕ.
S_{1}(a) = S(D(a)), S_{n+1}(a) = S(D(S_{n}(a))), for n ∈ ℕ.

Then {D_{n}(a)}_{n∈ℕ} and {S_{n}(a)}_{n∈ℕ} are increasing sequences of sets and

F (a) = ⋃_{n∈ℕ} D_{n}(a) = ⋃_{n∈ℕ} S_{n}(a).

Clearly, {D_{n}}_{n∈ℕ} is a sequence of dual subautomata of A, whereas {S_{n}}_{n∈ℕ} is a sequence of subautomata of A. Note that the theorem above can be also derived from a more general result of Tamura concerning the joins of algebraic closure operators on complete lattices (he called them join-conservative closure operators), given in [43] (see also [17] and [16]).

When we work with finite automata, the sequences defined above of sets are also finite, as the following theorem shows.

Theorem 4.4. (Ćirić and Bogdanović [14]) Let A be a finite automaton. Then there exists

m = min{k ∈ ℕ | (∀a ∈ A) D_{k}(a) = D_{k+1}(a)},
n = min{k ∈ ℕ | (∀a ∈ A) S_{k}(a) = S_{k+1}(a)},

for which also holds m, n ≤ |A| and F (a) = D_{m}(a) = S_{n}(a), for any a ∈ A.

5. Direct sum decompositions of automata

An automaton A is a direct sum of its subautomata A_{α}, α ∈ Y, in notation A = ∑_{α∈Y} A_{α}, if

A = ⋃_{α∈Y} A_{α}  and  A_{α} ∩ A_{β} = ∅, for α ≠ β.

The equivalence relation on A whose classes are different A_{α}, α ∈ Y, is a congruence on A and is called a direct sum congruence on A, the related partition of A is called a direct sum decomposition of A, and the automata A_{α}, α ∈ Y, are called direct summands of A. Note that a congruence ϱ on A is a direct sum congruence on A if and only if A/ϱ is a discrete automaton, where by a discrete automaton we mean an automaton for which au = a, for each state a and each input word u ∈ X^{∗}. An automaton A is called direct sum indecomposable if the universal relation ∇ on A is a unique direct sum congruence on A.

Direct sum decompositions are one of the most important types of decompositions of automata. They were first defined and studied by Huzino in [30], 1958, who proved that any automaton whose transition monoid is a group can be decomposed into a direct sum of strongly connected automata. A more general result was obtained by Glushkov in [23], 1961, who proved that any invertible automaton is also a direct sum of strongly connected automata. Thierrin, who called these automata locally transitive, proved in [45] that the converse of this assertion also holds. These results of Glushkov and Thierrin will be given in Theorem 5.5. Some other characterizations of these automata were given by Gécseg and Thierrin in [22], 1987.

Ćirić and Bogdanović observed in [14] that it is possible to build a general theory of direct sum decompositions of automata in which lattices of subautomata play a crucial role. They considered the poset of all direct sum decompositions of an automaton A inside the lattice Part (A) of all partitions of A. They first proved the following:

Theorem 5.1. (Ćirić and Bogdanović [14]) The set of all direct sum congruences of an automaton A is a principal dual ideal of the lattice E(A) of all equivalence relations on A.

They also showed how the smallest direct sum congruence on an automaton (which generates this principal dual ideal) can be constructed.

Let us observe that the class of all discrete automata is a variety of automata (in the Birkhoff sense), when one considers automata (without outputs) as unary algebras. In a recent papers [10] and [6], the first two authors proved that an algebraic class C of algebras of a given type F is a variety if and only if the set Con_{C} (A) of all C-congruences on A is a principal dual ideal of the congruence lattice Con (A), for any algebra A of type F. Here by a C-congruence on A we mean a congruence on A whose related factor algebra belongs to C. Applying this result to automata and the variety of discrete automata we obtain that for any automaton A, the set of all direct sum congruences on A is a principal dual ideal of Con (A).

As a dual of the above theorem one obtains the following:

Theorem 5.2. (Ćirić and Bogdanović [14]) The set of all direct sum decompositions of an automaton A is a principal ideal of the partition lattice Part (A).

Hence, direct sum decompositions of an arbitrary automaton form a complete lattice, and this lattice was characterized in the following way:

Theorem 5.3. (Ćirić and Bogdanović [14]) The lattice of direct sum decompositions of an automaton A is isomorphic to the lattice of complete Boolean subalgebras of F (A).

If K is an arbitrary complete Boolean subalgebra of F (A), and hence an atomic Boolean algebra, then the summands in the direct sum decomposition of A which corresponds to K are exactly the atoms of K. Considering the case K = F (A), one obtains the following:

Theorem 5.4. (Ćirić and Bogdanović [14]) Any automaton A can be represented as a direct sum of direct sum indecomposable automata.

This decomposition is the greatest direct sum decomposition of A and its summands are the principal filters of A.

It may seem that the indecomposability of the summands in the greatest direct sum decomposition of an automaton A is a natural consequence of the atomicity of F (A). But, this is not true. Bogdanović and Ćirić investigated in a similar way in [3] the so-called right zero sum decompositions of semigroups with zero. They used the center of the lattice of left ideals of a semigroup, which is also a complete atomic Boolean algebra. But, an example was given that there are semigroups with zero whose summands in the greatest right zero sum decomposition can be further decomposed into a right sum of semigroups.

In Section 3 we defined an automaton A to be strongly connected if for each pair a, b ∈ A there exists u ∈ X^{∗} such that au = b. These automata were introduced by Moore in [40], and they can also be defined by any of the following conditions:

(1) (∀a ∈ A) S(a) = A; (2) (∀a ∈ A) D(a) = A; (3) γ = ∇ on A. In some other sources such automata were called transitive automata (for example, by Gécseg and Thierrin in [22] and Lallement in [33]) or simple automata (by Glushkov in [23]). But, we use the name “strongly connected” which is the most frequent.

Following the terminology of Gécseg and Thierrin [22], an automaton A is called locally transitive if for all a ∈ A and u ∈ X^{∗} there exists v ∈ X^{∗} such that auv = a. Glushkov in [23], called these automata invertible. The next theorem gives some interesting properties of such automata:

Theorem 5.5. The following conditions on an automaton A are equivalent:

(i) A is a locally transitive automaton; (ii) A is a direct sum of strongly connected automata; (iii) γ is a direct sum congruence on A; (iv) Sub(A) ⊆ DSub(A);

(v) DSub(A) ⊆ Sub(A); (vi) S(a) = C(a), for any a ∈ A; (vii) Sub(A) is a Boolean algebra; (viii) Sub(A) is an atomistic lattice; (ix) Sub(A) is a dually atomistic lattice.

The implication (i) ⇒ (ii) was obtained by Glushkov in [23] (see also Huzino [30]), and the equivalence of (i) and (ii) was proved by Thierrin in [45] (see also Gécseg and Thierrin [22]). The equivalence of the conditions (ii)–(vii) was established by Ćirić and Bogdanović in [14], and the equivalence of (iii), (viii) and (ix) is a consequence of Theorems 3.9 and 3.10.

The next theorem can be viewed as a consequence of the previous one:

Theorem 5.6. (V. N. Salii [41]) An automaton A is strongly connected if and only if Sub(A) is a two-element Boolean algebra.

6. The lattice of positive quasi-orders

Positive quasi-orders were first defined and studied by Schein in [42], 1965, in the theory of semigroups, and they proved to be very useful in many investigations in this area. Ćirić, Bogdanović and Petković extended in [18] this notion to an arbitrary universal algebra, and making a specialization of this general notion to automata, the same authors defined in [17] positive quasi-orders on automata, as follows: A quasi-order ξ on an automaton A is called positive if a ξ au, for each a ∈ A and each u ∈ X^{∗}.

Ćirić, Bogdanović and Petković introduced also in [18] the notion of a division relation on an universal algebra, generalizing in a natural way the notion of a division relation on a semigroup, and in [17] they applied this definition to automata, so that they gave the following definition: The division relation | on an automaton A is defined by: a | b ⇔ (∃u ∈ X^{∗}) b = au. The division relation is an example of a positive quasi-order on an automaton. Furthermore, the following holds:

Theorem 6.1. (Ćirić, Bogdanović and Petković [17]) The set Q^{p}(A) of all positive quasi-orders on an automaton A is the principal dual ideal generated by the division relation on A of the lattice Q(A) of quasi-orders on A.

Let a quasi-order ξ be given on a non-empty set U. For a ∈ U, the sets aξ = {b ∈ U | a ξ b} and ξa = {b ∈ U | b ξ a} are called a left coset and a right coset of U determined by a, respectively. Similarly, for a non-empty H ⊆ U, the sets

Hξ = ⋃_{a∈H} aξ  and  ξH = ⋃_{a∈H} ξa

are called a left coset and a right coset of U determined by H. Bogdanović and Ćirić investigated in [4,5,8,9,11,12,13,15] positive quasi-orders on semigroups from the aspect of properties of their left and right cosets, and this proved to be very useful when semilattice decompositions and lattices of ideals of semigroups were studied. From the same aspect, positive quasi-orders on automata were studied by Ćirić, Bogdanović and Petković in [17]. They established the following connection between positive quasi-orders, subautomata and dual subautomata:

Theorem 6.2. (Ćirić, Bogdanović and Petković [17]) The following conditions for a quasi-order ξ on an automaton A are equivalent:

(i) ξ is positive; (ii) (∀a ∈ A)(∀u ∈ X^{∗}) (au)ξ ⊆ aξ; (iii) (∀a ∈ A)(∀u ∈ X^{∗}) ξa ⊆ ξ(au); (iv) aξ is a subautomaton of A, for each a ∈ A;

(v) ξa is a dual subautomaton of A, for each a ∈ A.

As was observed by Bogdanović and Ćirić in [4], any quasi-order ξ on a non-empty set U determines two complete 0,1-sublattices ξΛ and ξΠ of P (U) as follows:

ξΛ = {H ∈ P (U) | Hξ = H}  and  ξΠ = {H ∈ P (U) | ξH = H},

and the mappings Λ : ξ ↦ ξΛ and Π : ξ ↦ ξΠ are dual isomorphisms of Q(U) onto the lattice CS(P (U)) of all complete 0,1-sublattices of P (U). Moreover, for any quasi-order ξ on U, ξΛ and ξΠ are conjugated sublattices of P (U). These facts, together with Theorem 6.2, give the following two theorems:

Theorem 6.3. (Ćirić, Bogdanović and Petković [17]) The lattice Q^{p}(A) of positive quasi-orders on an automaton A is dually isomorphic to the lattice CS(Sub(A)) of all complete 0,1-sublattices of Sub(A).

Theorem 6.4. (Ćirić, Bogdanović and Petković [17]) The lattice Q^{p}(A) of positive quasi-orders on an automaton A is dually isomorphic to the lattice CS(DSub(A)) of all complete 0,1-sublattices of DSub(A).

Of course, dual isomorphisms from the above two theorems can be chosen to be the restrictions of Λ and Π on Q^{p}(A), respectively. For a positive quasi-order ξ on an automaton A, the principal elements of the lattices ξΛ and ξΠ are the left cosets aξ, a ∈ A, and the right cosets ξa, a ∈ A, respectively.

It is interesting to note that positive equivalence relations on an automaton A are exactly the direct sum congruences on A, that is D(A) = E(A) ∩ Q^{p}(A), where D(A) denotes the set of all direct sum congruences on A. In view of Theorem 6.1, D(A) is a complete sublattice of Q^{p}(A). Moreover, the following holds:

Theorem 6.5. (Ćirić, Bogdanović and Petković [17]) For an arbitrary automaton A, the restrictions of mappings Λ and Π to D(A) are dual isomorphisms of D(A) onto the lattice CB( F (A)) of all complete Boolean subalgebras of F (A).

Using this result the authors gave in [17] another proof of Theorem 5.3. In the same paper they also studied the operator D : ξ ↦ ξD on Q^{p}(A) which to any ξ ∈ Q^{p}(A) associates the smallest direct sum congruence on A containing ξ, denoted by ξD. This is a closure operator on Q^{p}(A) and the set of all D-closed elements of Q^{p}(A) is exactly D(A). The authors gave various characterizations of the operator D and studied the relationships between D, the mapping Λ and the mapping C : L ↦ C(L) of CS( Sub(A)) onto CB( F (A)), which to any complete 0,1-sublattice L of Sub(A) associates its center C(L). They proved the following.

Theorem 6.6. (Ćirić, Bogdanović and Petković [17]) For an arbitrary automaton A, the following diagram commutes:

Q^{p}(A) ⟶^{D} D(A)
Λ↓  ↓^{Λ}
CS(Sub(A)) ⟶^{C} CB(F (A))

In other words, for each ξ ∈ Q^{p}(A), (ξD)Λ is the center of ξΛ.

7. Direct product decompositions of the lattice of subautomata

It is known that direct product decompositions of certain kinds of lattices have very close ties with the properties of their centers. This topic was studied by Maeda in [38], Libkin in [34,35], Libkin and Muchnik in [36], Bogdanović and Ćirić in [3], Ćirić, Bogdanović and Kovačević in [16] and others. This approach was also used by Ćirić and Bogdanović in [14] where direct product decompositions of lattices of subautomata were investigated. Using the connections of these lattices and their centers with direct sum decompositions of automata, these authors proved the following:

Theorem 7.1. (Ćirić and Bogdanović [14]) The lattice Sub(A) of subautomata of an automaton A is a direct product of lattices L_{α}, α ∈ Y, if and only if A is a direct sum of automata A_{α}, α ∈ Y, and L_{α} ≅ Sub (A_{α}), for each α ∈ Y.

Note that Theorem 7.1 can be derived from a more general result of Ćirić, Bogdanović and Kovačević given in [16] concerning direct product decompositions of lattices which are distributive, algebraic and dually algebraic.

On the other hand, using the fact that any subautomaton has a greatest direct sum decomposition, the following was obtained:

Theorem 7.2. (Ćirić and Bogdanović [14]) Let A be an arbitrary automaton. Then the lattice Sub(A) can be represented as a direct product of directly indecomposable lattices, Sub(A) ≅ ∏_{α∈Y} Sub(A_{α}), where A = ∑_{α∈Y} A_{α} is a representation of A as a direct sum of direct sum indecomposable automata.

Finally, a relationship between the direct product indecomposability of the lattice of subautomata and the direct sum indecomposability of an automaton was given by the next theorem. Before we state this theorem, we give the following definition: For a non-empty set U, we define a relation ≬ on P (U) by: H ≬ G ⇔ H ∩ G ≠ ∅.

Theorem 7.3. (Ćirić and Bogdanović [14]) The following conditions on an automaton A are equivalent:

(i) Sub(A) is a direct product indecomposable lattice; (ii) A is a direct sum indecomposable automaton; (iii) A has no proper filters; (iv) F (A) is a two-element Boolean algebra;

(v) for all a, b ∈ A there exists a sequence c_{1}, c_{2},…, c_{n} ∈ A such that

S(a) ≬ S(c_{1}) ≬ S(c_{2}) ≬ ⋯ ≬ S(c_{n}) ≬ S(b);

(vi) for all a, b ∈ A there exists a sequence c_{1}, c_{2},…, c_{n} ∈ A such that

D(a) ≬ D(c_{1}) ≬ D(c_{2}) ≬ ⋯ ≬ D(c_{n}) ≬ D(b).

8. Representation theorems

The Representation of lattices by lattices of subalgebras is one of the most attractive problems of Lattice Theory and Universal Algebra. As was shown by Johnson and Seifert in [31], Jónsson in [32] and others, representations by lattices of subautomata are one of the most important kinds of representations. Such representations will be treated in this section.

There are two general kinds of the representation problem:

Abstract representation problem: Let L be a complete lattice. Under what conditions L is isomorphic to a subalgebra lattice of some algebra of a given type?

Concrete representation problem: Let L be a closure system on a non-empty set U. Under what conditions L is a system of subalgebras of some algebra of a given type with the base set U?

As was proved by Birkhoff and Frink in [2], a lattice L can be represented as a lattice of subalgebras of some algebra if and only if it is algebraic, and similarly, a closure system L on a non-empty set U can be represented as the system of subalgebras of some algebra with carrier U if and only if it is algebraic. However, some additional conditions are required for lattices and closure systems to be represented as subautomata lattices and systems of subautomata of some automaton, as it is shown in the further text.

We first consider the abstract representation problem.

For a cardinal k, any automaton whose input alphabet has this cardinality is called a k-automaton.

Theorem 8.1. (Johnson and Seifert [31]) Let k be an infinite cardinal. An algebraic lattice L is isomorphic to the lattice of subautomata of some k-automaton if and only if the following conditions are satisfied:

(a) L is distributive;

(b) CJI(L) is join-dense in L;

(c) principal ideals of CJI(L) have cardinality at most k.

Recall that one considers CJI(L) as a poset, so we use the notion “principal ideals of CJI(L)” when we consider the principal ideals of this poset.

Theorem 8.2. (Johnson and Seifert [31]) Let k be a cardinal such that 2 ≤ k ≤ ℵ_{0}. An algebraic lattice L is isomorphic to the lattice of subautomata of some k-automaton if and only if the following conditions are satisfied:

(a) L is distributive;

(b) CJI(L) is join-dense in L;

(c) the principal ideals of CJI(L) are countable.

Theorem 8.3. (Johnson and Seifert [31]) An algebraic lattice L is isomorphic to the lattice of subautomata of some autonomous automaton if and only if the following conditions are satisfied:

(a) L is distributive;

(b) CJI(L) is join-dense in L;

(c) each principal ideal of CJI(L) form a finite or countable strictly decreasing sequence.

Applied to finite lattices, the above results give the following:

Theorem 8.4. (Saliĭ [41]) A finite lattice is isomorphic to the lattice of subautomata of some finite automaton if and only if it is distributive.

Theorem 8.5. (Saliĭ [41]) A finite distributive lattice is isomorphic to the lattice of subautomata of some finite autonomous automaton if and only if each principal ideal of CJI(L) is a chain.

Now we go to the concrete representation problem for the representation of closure systems by systems of subautomata:

Theorem 8.6. (Gould [25]) A closure system L on a non-empty set U is the system of subautomata of some automaton if and only if L is complete.

In fact, the above theorem is a consequence of a more general result proved in the cited paper.

Theorem 8.7. (Johnson and Seifert [31]) Let k be an infinite cardinal. A closure system L on a non-empty set U is the system of subautomata of some k-automaton if and only if L is complete and the principal elements of L have cardinality at most k.

Theorem 8.8. (Johnson and Seifert [31]) A closure system L on a non-empty set U is the system of subautomata of some autonomous automaton if and only if L is complete and for each a ∈ U one of the following conditions holds:

(a) L(a) is finite and L(b) = L(a), for any b ∈ L(a);

(b) for each b ∈ L(a) there exists a finite sequence a = c_{0}, c_{1},…, c_{n} = b such that L(c_{k}) = L(c_{k−1}) \ {c_{k−1}}, for 1 ≤ k ≤ n.

In the above theorem L(a) denotes the principal element of L generated by a ∈ U.

For proofs of the above theorems see also Jónsson [32].

The section will be finished by a representation theorem for complete atomic Boolean algebras by Boolean algebras of filters of automata:

Theorem 8.9. (Ćirić and Bogdanović [14]) Any complete atomic Boolean algebra can be represented as the Boolean algebra of filters of some automaton.

References

[1] G. Birkhoff, Lattice Theory, 3rd edition, 3rd printing, Coll. Publ. XXV, Amer. Math. Soc., Providence, R. I., 1979.

[2] G. Birkhoff and O. Frink, Representations of lattices by sets, Trans. Amer. Math. Soc. 64 (1948), 299–316.

[3] S. Bogdanović and M. Ćirić, Decompositions of semigroups with zero, Publ. Inst. Math. (Beograd) 57(71) (1995), 111–123.

[4] S. Bogdanović and M. Ćirić, Positive quasi-orders with the common multiple property on a semigroup, Proc. Math. Conf. in Priština 1994, Lj. Kočinac, Ed., Priština, 1995, pp. 1–6.

[5] S. Bogdanović and M. Ćirić, Quasi-orders and semilattice decompositions of semigroups (A survey), Monograph of Kunming Semigroup Conference ’95, Springer-Verlag (to appear).

[6] S. Bogdanović and M. Ćirić, A note on congruences on algebras, Proc. 2nd Math. Conf. in Priština 1996, Lj. D. Kočinac ed., 1997, pp. 67–72.

[7] S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, Springer-Verlag, 1983.

[8] M. Ćirić and S. Bogdanović, Theory of greatest decompositions of semigroups (A survey), Filomat (Niš) 9:3 (1995), 385–426.

[9] M. Ćirić and S. Bogdanović, Semilattice decompositions of semigroups, Semigroup Forum 52 (1996), 119–132.

[10] M. Ćirić and S. Bogdanović, Posets of ℭ-congruences, Algebra Universalis 36 (1996), 423–424.

[11] M. Ćirić and S. Bogdanović, Ordinal sums of semigroups, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 7 (1996), 30–33.

[12] M. Ćirić and S. Bogdanović, The lattice of positive quasi-orders on a semigroup, Israel J. Math. 98 (1997), 157–166.

[13] M. Ćirić and S. Bogdanović, The lattice of positive quasi-orders on a semigroup II, Facta Univ. (Niš), Ser. Math. Inform. 9 (1994), 7–17.

[14] M. Ćirić and S. Bogdanović, Lattices of subautomata and direct sum decompositions of automata, Algebra Colloquium 6:1 (1999), 71–88.

[15] M. Ćirić and S. Bogdanović, Quasi-semilattice decompositions of semigroups with zero (to appear).

[16] M. Ćirić, S. Bogdanović and J. Kovačević, Direct sum decompositions of quasi-ordered sets and their applications, Filomat (Niš) 12 (1998) (to appear).

[17] M. Ćirić, S. Bogdanović and T. Petković, The lattice of positive quasi-orders on an automaton, Facta Univ. (Niš), Ser. Math. Inform. 11 (1996), 143–156.

[18] M. Ćirić, S. Bogdanović and T. Petković, Sums and limits of generalized direct families of algebras (to appear).

[19] P. Crawley and R. P. Dilworth, Algebraic Theory of Lattices, Prentice-Hall, Englewood Cliffs, 1973.

[20] P. Dubreil, Contribution à la théorie des demigroupes, Mém. Acad. Sci. Inst. France (2) 63 (1941), no. 3.

[21] F. Gécseg and I. Peák, Algebraic Theory of Automata, Akadémiai Kiadó, Budapest, 1972.

[22] F. Gécseg and G. Thierrin, Characterizations of locally transitive semiautomata, Papers on Automata and languages IX, K. Marx Univ. of Economics, Dept. of Math., Budapest 87–2 (1987), 1–8.

[23] V. M. Glushkov, Abstract theory of automata, Uspehi matem. nauk 16:5 (101) (1961), 3–62. (in Russian)

[24] V. M. Glushkov, G. E. Ceĭtlin and E. L. Yushchenko, Algebra. Languages. Programming, Naukova dumka, Kiev, 1978. (in Russian)

[25] M. Gould, Multiplicity type and subalgebra structure in universal algebras, Pacific J. Math. 26 (1968), 469–485.

[26] G. Grätzer, Universal Algebra, Van Nostrand, Princeton, 1968.

[27] G. Grätzer, General Lattice Theory, Akademie-Verlag, Berlin, 1978.

[28] G. Grätzer and E. T. Schmidt, Characterizations of congruence lattices of abstract algebras, Acta. Sci. Math. (Szeged) 24 (1963), 34–59.

[29] J. M. Howie, Automata and Languages, Clarendon Press, Oxford, 1991.

[30] S. Huzino, On some sequential machines and experiments, Mem. Fac. Sci. Kyushu Univ. Ser. A 12 (1958), 136–158.

[31] J. Johnson and R. L. Seifert, A survey of multi-unary algebras, Mimeographed seminar notes, U. C. Berkeley, 1967, pp. 26.

[32] B. Jónsson, Topics in Universal Algebra, Lect. Notes in Math. 250, Springer-Verlag, Berlin, 1972.

[33] G. Lallement, Semigroups and Combinatorial Applications, Willey Interscience, New York, 1979.

[34] L. Libkin, Direct product decompositions of lattices, closures and relation schemes, Discrete Mathematics 112 (1993), 119–138.

[35] L. Libkin, Direct decompositions of atomistic algebraic lattices, Algebra Universalis 33 (1995), 127–135.

[36] L. Libkin and I. Muchnik, The lattice of subsemilattices of a semilattice, Algebra Universalis 31 (1994), 252–255.

[37] R. Sz. Madarász and S. Crvenković, Introduction to theory of automata and formal languages, Univ. of Novi Sad, Novi Sad, 1995. (in Serbian)

[38] S. Maeda, Infinite distributivity in complete lattices, Mem. Ehime Univ. Sect II Ser. A 5 (1966), no. 3, 11–13.

[39] E. H. Moore, Introduction to a Form of General Analysis, Coll. Publ. II, Amer. Math. Soc., New Haven, 1910.

[40] E. F. Moore, Gedanken-experiments on sequential machines, Automata studies (C. E. Shannon and J. McCarthy, eds), Princeton, 1956, pp. 129–153.

[41] V. N. Saliĭ, Universal Algebra and Automata, Saratov Univ., Saratov, 1988. (in Russian)

[42] B. M. Schein, On certain classes of semigroups of binary relations, Sibir. Mat. Zhurn. 6 (1965), 616–635. (in Russian)

[43] T. Tamura, The theory of operations on binary relations, Trans. Amer. Math. Soc. 120 (1965), 343–358.

[44] A. Tarski, Sur les classes closes par rapport à certaines opérations élémentaires, Fund. Math. 16 (1929), 181–305.

[45] G. Thierrin, Decompositions of locally transitive semiautomata, Utilitas Math. 2 (1972), 25– 32.

M.Ćirić, Filozofski fakultet, 18000 Niš, Yugoslavia, mciric@archimed.filfak.ni.ac.yu S. Bogdanović, Ekonomski fakultet, 18000 Niš, Yugoslavia, sbogdan@archimed.filfak.ni.ac.yu T. Petković, Filozofski fakultet, 18000 Niš, Yugoslavia, tanjapet@archimed.filfak.ni.ac.yu

(Received 25 04 1998; Revised 25 11 1998)