Kudryavtsev V.B., Rosenberg I.G. Structural Theory of Automata, Semigroups, and Universal Algebra
Подождите немного. Документ загружается.
Epigroups 377
[82] M. P. Sch¨utzenberger, Sur le produit de concat´enation non ambigu, Semigroup Forum
13 (1976), 47–76.
[83] R. Schwabauer, A note on commutative semigroups, Proc.Amer.Math.Soc.20 (1969),
503–504.
[84]
ˇ
S. Schwarz, Contribution to the theory of torsion semigroups, Czechosl. Math. J. 3
(1953), 7–21. (Russian.)
[85] J. T. Sedlock, Green’s relations on periodic semigroups, Czechosl. Math. J. 19 (1969),
318–323.
[86] L. N. Shevrin, To the general theory of semigroups, Mat. Sb. 53 (3) (1961), 367–385.
(Russian.)
[87] L. N. Shevrin, Nilsemigroups with certain finiteness conditions, Mat. Sb. 55 (4) (1961),
473–480. (Russian.)
[88] L. N. Shevrin, On semigroups in which all subsemigroups are nilpotent, Sib. Mat. Zh.
2 (1961), 936–942. (Russian.)
[89] L. N. Shevrin, Certain finiteness conditions in the theory of semigroups, Izv. Acad. Sci.
USSR. Ser. Mat. 29 (1965), 553–566. (Russian.)
[90] L. N. Shevrin, Semigroups of finite breadth, Theory of Semigroups and Its Applications
(Saratov) 1 (1965), 325–351. (Russian.)
[91] L. N. Shevrin, ed., The Sverdlovsk Notebook: Unsolved Problems in the Theory of
Semigroups, Sverdlovsk, Ural State University, 1969; 2nd ed., 1979; 3rd ed., 1989.
(Russian; English translation of the 1st ed.: Semigroup Forum 4 (1972), 274–280.)
[92] L. N. Shevrin, A supplement to the paper “Semigroups of finite breadth”, Theory of
Semigroups and Its Applications (Saratov) 2 (1970), 94–96. (Russian.)
[93] L. N. Shevrin, A general theorem on semigroups with some finiteness conditions, Mat.
Zametki 15 (1974), 925–935. (Russian.)
[94] L. N. Shevrin, To the theory of periodic semigroups, Izv. VUZ. Matem. 5 (1974), 205–
216. (Russian.)
[95] L. N. Shevrin, On the decomposition of a quasiperiodic semigroup into a band of
archimedean semigroups, XIV All-Union Algebra Conf. Abstracts of Reports. Part 1,
Novosibirsk, 1977, 104–105. (Russian.)
[96] L. N. Shevrin, Quasiperiodic semigroups possessing a partition into unipotent semi-
groups, XVI All-Union Algebra Conf. Abstracts of Reports. Part 1, Leningrad, 1981,
177–178. (Russian.)
[97] L. N. Shevrin, Quasiperiodic semigroups that are decomposable into a band of
archimedean semigroups, XVI All-Union Algebra Conf. Abstracts of Reports. Part 1,
Leningrad, 1981, 188. (Russian.)
378 L. N. Shevrin
[98] L. N. Shevrin, On the decomposition of quasiperiodic semigroups into a band, XVII
All-Union Algebra Conf. Abstracts of Reports. Part 2, Minsk, 1983, 267–268. (Russian.)
[99] L. N. Shevrin, Finitely assembled semigroups, III All-Union Symp. on Theory of Semi-
groups. Abstracts of Reports, Sverdlovsk, 1988, 102. (Russian.)
[100] L. N. Shevrin, Epigroups with certain finiteness conditions, Int. Conf. on Algebra in
Memory of A. I. Mal’tsev. Abstracts of Reports on Theory of Models and Algebraic
Systems, Novosibirsk, 1989, 153. (Russian.)
[101] L. N. Shevrin, Groups whose subgroup lattice has finite dimension, XI All-Union Symp.
on Theory of Groups. Abstracts of Reports, Sverdlovsk, 1989, 132. (Russian.)
[102] L. N. Shevrin, Semigroups, Chapter IV in: General Algebra. Vol. II (L. A. Skornyakov,
ed.), Nauka, Moscow, 1991, 11–191. (Russian.)
[103] L. N. Shevrin, On two longstanding problems concerning nilsemigroups, in: Semigroups
with Applications (J.M.Howie,W.D.Munn,andH.J.Weinert,eds.),WorldScientific,
Singapore, 1992, 222–235.
[104] L. N. Shevrin, To the theory of epigroups. I, II, Mat. Sb. 185 (8) (1994), 129–160;
185 (9) (1994), 153–176. (Russian; English translation: Russ. Acad. Sci. Sb. Math. 82
(1995), 485–512; 83 (1995), 133–154.)
[105] L. N. Shevrin and A. Ja. Ovsyannikov, Semigroups and their subsemigroup lattices,
Semigroup Forum 27 (1983), 1–154.
[106] L. N. Shevrin and A. Ja. Ovsyannikov, Semigroups and Their Subsemigroup Lattices,
Ural State University Press, Sverdlovsk, Part 1, 1990; Part 2, 1991. (Russian.)
[107] L. N. Shevrin and A. Ja. Ovsyannikov, Finitely assembled semigroups and ascending
chain condition for subsemigroups, in: Monash Conf. on Semigroup Theory in Honour
of G. B. Preston (T. E. Hall, P. R. Jones, and J. C. Meakin, eds.), World Scientific,
Singapore, 1991, 269–284.
[108] L. N. Shevrin and A. Ja. Ovsyannikov, Semigroups and Their Subsemigroup Lattices,
Kluwer, Dordrecht, 1996. (Revised and enlarged English translation of [106].)
[109] L. N. Shevrin and E. V. Sukhanov, Structural aspects of the theory of semigroup
varieties, Izv. VUZ. Matem. 6 (1989), 3–39. (Russian; English translation: Soviet Math.
Izv. VUZ 33 (6) (1989), 1–34.)
[110] L. N. Shevrin and M. V. Volkov, Identities of semigroups, Izv. VUZ. Matem. 11 (1985),
3–47. (Russian; English translation: Soviet Math. Izv. VUZ 29 (11) (1985), 1–64.)
[111] V. P. Shunkov, On locally finite groups with the maximal condition for abelian sub-
groups, Algebra i Logika 9 (1970), 579–615. (Russian.)
[112] A. N. Silkin, On almost nilpotent nilsemigroups, manuscript, Ural State University,
1993. (Russian.)
Epigroups 379
[113] A. V. Tishchenko, A remark on semigroup varieties of finite index, Izv. VUZ. Matem.
7 (1990), 79–83. (Russian; English translation: Soviet Math. Izv. VUZ 34 (7) (1990),
92–96.)
[114] A. V. Tishchenko and M. V. Volkov, A characterization of semigroup varieties of finite
index in the language of “forbidden divisors”, Izv. VUZ. Matem. 1 (1995), 91–99.
(Russian; English translation: Russ. Math. Izv. VUZ 39 (1) (1995), 84–92.)
[115] E. G. Tretyakova, On quasiperiodic semigroups, manuscript, Ural State University,
1982. (Russian.)
[116] E. G. Tretyakova, On the free two-generated Clifford semigroup, Int. Conf. on Algebra
in Memory of A. I. Shirshov. Barnaul, 1991. Abstracts of Reports on Logic, Universal
Algebras, and Applied Algebra, Novosibirsk, 1991, 145. (Russian.)
[117] P. G. Trotter, Free completely regular semigroups, Glasgow Math. J. 25 (1984), 241–
254.
[118] B. M. Vernikov, Semimodular and arguesian varieties of semigroups: forbidden subva-
rieties, Proc. Ural State Univ. 22 (Matem., Mechan.) (4) (2002), 16–42. (Russian.)
[119] B. M. Vernikov and M. V. Volkov, Semimodular and arguesian varieties of semigroups:
a completion of description, Proc. Ural State Univ. 30 (Matem., Mechan.) (6) (2004),
5–36. (Russian.)
[120] M. V. Volkov, Semigroup varieties with modular subvariety lattices. I, II, III, Izv.
VUZ. Matem. (6) (1989), 51–60; (7) (1992), 3–8; (8) (1992), 21–29. (Russian; English
translation: Soviet Math. Izv. VUZ 33 (6) (1989), 48–58; Russ. Math. Izv. VUZ 36 (7)
(1992), 1–6; 36 (8) (1992), 18–25.)
[121] M. V. Volkov, Semigroup varieties with modular subvariety lattices, Dokl. Russ. Akad.
Sci. 326 (1992), 409–413. (Russian; English translation: Russ. Acad. Sci. Dokl. Math.
46 (1993), 274–278.)
[122] M. V. Volkov, Identities in the Lattice of Semigroup Varieties, Dr. Sci. dissertation,
Ural State University, Ekaterinburg, 1994. (Russian.)
[123] M. V. Volkov, Covers in the lattices of semigroup varieties and pseudovarieties, in:
Semigroups, Automata and Languages (J.Almeida,G.M.S.Gomes,andP.V.Silva,
eds.), World Scientific, Singapore, 1996, 263–280.
[124] M. V. Volkov, “Forbidden divisor” characterizations of epigroups with certain properties
of group elements, RIMS Kokyuroku 1166 (Algebraic Systems, Formal Languages and
Computations) (2000), 226–234.
[125] M. V. Volkov, Semimodular and arguesian varieties of semigroups: identities, Proc.
Ural State Univ. 22 (Matem., Mechan.) (4) (2002), 43–61. (Russian.)
[126] M. V. Volkov and T. A. Ershova, The lattice of varieties of semigroups with completely
regular square, in: Monash Conf. on Semigroup Theory in Honour of G. B. Preston
(T. E. Hall, P. R. Jones, and J. C. Meakin, eds.), World Scientific, Singapore, 1991,
306–322.
380 L. N. Shevrin
[127] M. V. Volkov and M. V. Sapir, HFB property and structure of semigroups, Contrib.
General Algebra 6 (1988), 303–310.
[128] M. Yamada, A remark on periodic semigroups, Bull. Shimane Univ. 9 (1959), 1–5.
[129] I. Yu. Zhil’tsov, On epigroup identities, Dokl. Russ. Acad. Sci. 375 (2000), 10–12.
(Russian; English translation: Russ. Acad. Sci. Dokl. Math. 62 (2000), 322–324.)
Algebraic classifications of regular tree languages
Magnus STEINBY
Department of Mathematics
and
Turku Centre for Computer Science
University of Turku
FIN-20014 Turku
Finland
Abstract
We review several algebraic formalisms used for characterizing families of regular tree
languages. A theory based on syntactic algebras and varieties of congruences is presented
in detail, including the Variety Theorem that establishes the correspondences between
varieties of tree languages, varieties of finite algebras and varieties of congruences on the
finitely generated term algebras. Several examples of varieties of tree languages are given.
Also generalizations of this theory as well as some alternative approaches are considered.
1 Introduction
In 1976 Samuel Eilenberg [18] presented his fundamental Variety Theorem that establishes
a bijective correspondence between varieties of finite monoids and certain families of regular
languages that he called ∗-varieties, or alternatively, between varieties of finite semigroups
and so-called +-varieties consisting of regular languages that do not include the empty word.
The variety theorem was preceded, and inspired, by some remarkable results about certain
individual families of regular languages. First of all, M. P. Sch¨utzenberger [77] had shown
in 1965 that a regular language is star-free exactly in case its syntactic monoid is aperiodic,
that is to say, all of its subgroups are trivial. This theorem gave a decision method for
an important family of languages that arises in many seemingly independent ways. In the
early 1970’s several other families of regular languages had been similarly characterized.
By describing exactly the families of regular languages that can be characterized this way
by syntactic monoids or syntactic semigroups, the variety theorem has provided a general
framework for the classification of regular languages that has retained its place till this day.
Of course, there have also been some important amendments to the variety theory itself, such
as Th´erien’s varieties of congruences [86, 87] and Pin’s theory of positive varieties [64]. For
the theory of string language varieties the references [2, 18, 37, 45, 63, 64] are recommended.
Algebraic classifications of regular string languages are almost exclusively based on semi-
group theory via syntactic monoids or semigroups (although a classification corresponding to
varieties of finite unary algebras is also possible, cf. [83, 57, 58, 59]). It appears clear that
syntactic monoids or semigroups are not equally well suited for describing properties of tree
languages. In fact, we shall see that many natural families of regular tree languages cannot
381
V. B. Kudryavtsev and I. G. Rosenberg (eds.),
Structural Theory of Automata, Semigroups, and Universal Algebra, 381–432.
© 2005 Springer. Printed in the Netherlands.
382 M. Steinby
be characterized by these syntactic invariants, and that there are more promising approaches.
In [78, 80] and [1] the syntactic algebra of a subset of any algebra is defined in such a way
that the syntactic algebra of a string language L over an alphabet X becomes its syntactic
monoid when L is viewed as a subset of the free monoid X
∗
. Similarly, if L does not contain
the empty word, then its syntactic algebra as a subset of the free semigroup X
+
is its usual
syntactic semigroup. For a tree language T , defined as a set of terms over a finite set Σ of
operation symbols, i.e., a ranked alphabet, and a finite set X of variables, the syntactic alge-
bra is a Σ-algebra that is finite exactly in case T is a regular tree language. Using syntactic
algebras it is possible to prove a general variety theorem that establishes a correspondence
between certain families of recognizable subsets (as defined in [52]) of finitely generated free
algebras over a given variety V of Σ-algebras and varieties of finite Σ-algebras. For the vari-
eties of monoids and semigroups, the two cases of Eilenberg’s variety theorem are obtained.
On the other hand, if V is taken to be the class of all Σ-algebras, the free algebras are term
algebras and we obtain a variety theorem that establishes a bijection between varieties of
tree languages and varieties of finite Σ-algebras. It turns out that a considerable part of the
known families of special regular tree languages are such varieties of tree languages.
As shown in [1] and [80], the variety theorem can be completed with varieties of congru-
ences also for tree languages. The theory can also be generalized in various ways. Firstly,
in [84] a variety theory that does not assume a fixed ranked alphabet is presented. Thus we
obtain generalized varieties of tree languages that include regular tree languages over any pair
of alphabets Σ and X. On the other hand, in [73] it is shown how the theory can be formu-
lated for many-sorted tree languages. Then there is naturally the above mentioned general
formulations of [1] and [78] in which tree languages are replaced by recognizable subsets of
free algebras over a given variety. Moreover, there are several alternative approaches, a fact
that once again shows that generalizations from strings to trees are not always obvious or
unique. The natural idea of defining syntactic monoids and syntactic semigroups for tree lan-
guages was realized by Thomas [88, 89] who also characterized non-counting tree languages
by their syntactic monoids. However, we shall see that syntactic monoids or semigroups
are of limited use in the case of tree languages. In [22]
´
Esik proposes another alternative
framework in which tree languages are classified by their syntactic algebraic theories—here
the ‘algebraic theories’ are the special categories introduced by Lawvere (1963; cf. [20] or [22]
for the reference). In Wilke’s [92] approach the syntactic invariant used is the syntactic tree
algebra of a tree language. This is a 3-sorted algebraic structure that in some sense embodies
the syntactic algebra as well as the syntactic monoid, or the syntactic semigroup, of the tree
language. The theory differs from those mention before in that trees are not defined directly
as terms but they are represented by terms over an ‘external’ 3-sorted alphabet. The type of
the syntactic tree algebra does not depend on the label alphabet. Instead, the label alphabet
servesasageneratingsetofthefreetreealgebrainthesamewayasthealphabetsofstring
languages generate the free monoids. However, the formalism is restricted to binary trees.
The theory of finite tree automata and regular tree languages can be formulated as an
algebraic generalization of the theory of finite automata and regular languages in such a way
that Universal Algebra becomes the natural mathematical framework for it. In Section 2
we recall some basic algebraic notions and establish the corresponding notation to be used.
Section 3 is then a brief introduction to finite automata, regular languages, and Eilenberg’s
variety theory. It should facilitate the understanding of the corresponding tree theory and
also put the subject matter of this paper into a proper perspective. In Section 4 it is shown
Algebraic classifications of regular tree languages 383
how trees are defined as terms. The next two sections introduce the basic notions of the
theory of finite tree automata and regular tree languages. In Section 5 tree recognizers are
defined as finite algebras equipped with initial state assignments and sets of final states, and
then we present some algebraic characterizations of the tree languages recognized by them,
the regular tree languages. Section 6 introduces several operations on tree languages and
notes the closure properties of the family of regular tree languages under them.
Sections 7 to 12 form the core part of the paper. The presentation is based to a great
extent on reference [80], but it has been updated and extended in many ways. On the other
hand, some technical proofs are omitted. Section 7 introduces varieties of tree languages,the
families of regular tree languages to which the variety theory applies. In Section 8 syntactic
congruences and syntactic algebras are considered. This can be done for subsets of arbitrary
algebras, not just tree languages, and then the results become immediately available in many
other similar theories. In Section 9 we consider varieties of finite algebras, also called pseudo-
varieties. These have been studied quite extensively in Universal Algebra independently of
tree languages, and some references to such work are given. Varieties of finite congruences
are introduced in Section 10. These are certain systems of filters of the congruence lattices
of finitely generated term algebras that are very convenient for defining varieties of tree lan-
guages. In Section 11 all these ingredients are brought together to yield the Variety Theorem
that establishes bijective correspondences between varieties of tree languages, varieties of
finite algebras and varieties of congruences. In Section 12 we consider several examples of
varieties of tree languages. Most of these are defined through the corresponding varieties of
congruences, and in some cases also the corresponding variety of finite algebras can be given.
Many of these families have also been studied in connection with the problem of inferring
tree languages from samples (cf. [43] and [46], for example).
The next two sections are devoted to various generalizations and alternative approaches.
Hence, in Section 13 we consider varieties of recognizable subsets of [78] and [1], the theory
of many-sorted varieties developed in [73], and the theory of generalized varieties of tree
languages (GVTLs) of [84]. We also mention the theory of positive varieties of tree languages
recently put forward in [60]. Section 14 begins with a discussion of syntactic monoids of tree
languages and a couple of examples of their use, but we will also note the limitations of the
approach. In particular, we note a recent important result by Salehi [71] that characterizes
the GVTLs that can be defined by syntactic monoids or syntactic semigroups. Then we note
the syntactic theory approach of [22], mentioned already above, the related work on syntactic
pre-clones by
´
Esik and Weil [23], as well as the tree algebras of [92].
In the last section, Section 15, we consider tree languages accepted by deterministic
top-down tree recognizers, called DT-recognizable tree languages for short. These form a
proper subfamily of the family of all regular tree languages [47]. It is not a variety of tree
languages, but its Boolean closure is (as noted in [38, 39]). However, most of the section is
devoted to the syntactic path monoids and syntactic path semigroups introduced by G´ecseg
and Steinby [30]. These are obtained from the string languages that describe the labelled
paths leading from the root to a leaf with a given label in a tree belonging to the given tree
language—there is such a language for each leaf symbol. It seems possible that syntactic
path monoids or semigroups are suitable for characterizing families of DT-recognizable tree
languages because DT-recognizable tree languages are completely determined by their path
languages (cf. [12, 90, 28, 39, 29]).
The references are naturally an essential part of a paper like this, and hopefully all the
most important works are mentioned.
384 M. Steinby
2 Algebraic Preliminaries
Let us begin with some general notation. First of all, the symbol := is sometimes used in
definitions. Thus we write A := B to indicate that A is defined to be equal to B. The basic
set theoretical symbols ∩, ∪, ⊆, ⊂,... have their usual meanings. The power set of a set U
is written as ℘U . A family F⊆℘U of subsets of U is a field of sets on U if (1) ∅,U ∈F,
and (2) S ∩T,S ∪ T,S − T ∈Fwhenever S, T ∈F.TheBoolean closure of a set S⊆℘U
of subsets of U is the least field of sets F on U such that S⊆F.ABoolean subalgebra of a
field of sets F⊆℘U is any subfamily B⊆Fof F that also forms a field of sets on U.
Let θ ⊆ A ×A be a relation on a set A.Thefactthat(a, b) ∈ θ,forsomea, b ∈ A,isoften
expressed by writing aθb.Theconverse of θ is the relation θ
−1
= {(b, a) | (a, b) ∈ θ} on A.
The product of two relations θ and ρ on A is the relation θ ◦ρ = {(a, c) | (∃b ∈ A) a θ b, b ρ c}
on A.Thediagonal relation {(a, a) | a ∈ A} and the universal relation A × A are denoted
by ∆
A
and ∇
A
, respectively. A relation θ ⊆ A × A is an equivalence relation,orsimplyan
equivalence,onA if ∆
A
⊆ θ, θ
−1
⊆ θ and θ ◦θ ⊆ θ. The set of all equivalences on A is denoted
by Eq(A). The restriction of an equivalence θ ∈ Eq(A) to a subset B ⊆ A is the equivalence
θ
B
:= θ ∩(B ×B)onB.Forθ ∈ Eq(A), the quotient set A/θ is the set {a/θ | a ∈ A},where
a/θ = {b ∈ A | aθb} is the θ-class of a ∈ A.IfA/θ is finite, θ is said to be of finite index,or
simply to be finite. An equivalence θ ∈ Eq(A)issaidtosaturate a subset H of A if H is the
union of some θ-classes.
A mapping ϕ : A → B may also be viewed as a special relation between A and B.Often
we write aϕ for the image ϕ(a)ofanelementa ∈ A. This notation is used especially when
ϕ is a homomorphism. Furthermore, for any H ⊆ A and any K ⊆ B,wewriteHϕ for
ϕ(H):
={aϕ | a ∈ H} and Kϕ
−1
for ϕ
−1
(K):={a ∈ A | aϕ ∈ K}.Ifθ ∈ Eq(B)isan
equivalence on B,thenϕ ◦ θ ◦ ϕ
−1
is the equivalence {(a
1
,a
2
) ∈ A × A | a
1
ϕθa
2
ϕ} on A.
All lattice theory needed in the theories to be considered, can be found in any standard
text on universal algebra, such as [9] or [32], for example. Let us just recall some notions to
be used here. Partial orders will be called simply orders. Hence an ordered set is pair (A, ≤)
consisting of a non-empty set A and a relation ≤ on A that is reflexive, antisymmetric and
transitive. A lattice is an ordered set (A, ≤) such that any two elements a, b ∈ A have a least
upper bound, the join a ∨ b, and a greatest lower bound, the meet a ∧ b.Acomplete lattice
is an ordered set (A, ≤) such that the least upper bound sup H and the greatest lower bound
inf H exist for every H ⊆ A. It is well known that an ordered set is a complete lattice if all
greatest lower bounds exist.
Some of the ordered sets to be considered here are algebraic lattices of the following special
kind. Let S⊆℘U be a set of subsets of a universe U.Then(S, ⊆) is an algebraic lattice if
C ∈Sfor all C⊆S,and
D∈Sfor every directed D⊆S; D is directed if for any two
sets X, Y ∈D,thereisasetZ ∈Dsuch that X, Y ⊆ Z. Of course, any algebraic lattice is a
complete lattice.
Finally, let us recall that a filter of a lattice (A, ≤)
is a non-empty subset F of A such
that (1) a ≤ b and a ∈ F imply b ∈ F ,and(2)a ∧ b ∈ F whenever a, b ∈ F .Thefilter
generated by a non-empty subset H ⊆ A, i.e., the least filter [H) containing H, can easily be
shown to be the set {a ∈ A | (∃n>0) (∃b
1
,...,b
n
∈ H) b
1
∧ ...∧ b
n
≤ a}.
Algebraic classifications of regular tree languages 385
The tree automata to be considered here are essentially finite algebras of finite type.
Therefore we recall some basic notions of universal algebra. For systematic introductions to
the subject we refer the reader to any of the books [2, 9, 10, 32, 91], for example.
Let Σ be a set of operation symbols. Hence each symbol in Σ has a unique non-negative
integer arity.Foreachm ≥ 0, Σ
m
denotes the set of m-ary symbols in Σ. A Σ-algebra A
consists of a non-empty set A and a Σ-indexed family of operations f
A
on A such that if
f ∈ Σ
m
(m>0), then f
A
: A
m
→ A is an m-ary operation, and any c ∈ Σ
0
is realized as a
constant c
A
∈ A.WewriteA =(A, Σ), and call A finite if A is a finite set. A one-element
Σ-algebra is said to be trivial.
AΣ-algebraB =(B,Σ) is a subalgebra of a Σ-algebra A =(A, Σ) if B ⊆ A and every
operation f
B
of B is the restriction to B of the corresponding operation f
A
.Inparticular,
c
B
= c
A
for every c ∈ Σ
0
. This also means that B is a closed subset of A, i.e., f
A
(b
1
,...,b
m
) ∈
B whenever m>0, f ∈ Σ
m
and b
1
,...,b
m
∈ B,andc
A
∈ B for every c ∈ Σ
0
. Since there
is a natural bijection between the subalgebras and the non-empty closed subsets of A,non-
empty closed subsets are also called subalgebras. Let Sub(A) be the set of all closed subsets
of A. The intersection of any set of closed subsets is again closed. Hence, any subset H of
A is contained in a unique minimal closed subset H that, when non-empty, is called the
subalgebra generated by H. Obviously, H = ∅ if H = ∅,and∅ = ∅ exactly in case Σ
0
= ∅.
A mapping ϕ : A → B is a homomorphism from A =(A, Σ) to B =(B,Σ), expressed
by writing ϕ : A→B,iff
A
(a
1
,...,a
m
)ϕ = f
B
(a
1
ϕ,...,a
m
ϕ) for all m>0, f ∈ Σ
m
and
a
1
,...,a
m
∈ A,andc
A
ϕ = c
B
for every c ∈ Σ
0
. A homomorphism is called an epimorphism
if it is surjective, a monomorphism if it is injective, and an isomorphism if it is bijective. The
algebras A and B are isomorphic, A
∼
=
B in symbols, if there is an isomorphism ϕ : A→B.
If there is an epimorphism ϕ : A→B,thenB is said to be an (epimorphic) image of A.
Let A and B be Σ-algebras. If A is an image of some subalgebra of B,wewriteA/B
and say that A is covered by B,orthatA divides B. It is clear that for any Σ-algebras A,
B and C,(1)A/Aand (2) A/Band B/Cimply A/C.Moreover,ifA and B are
finite, then (3) A/Band B/Aif and only if A
∼
=
B.Ofcourse,A/Bwhenever A is
isomorphic to a subalgebra of B or an image of B. Hence the /-relation may be used as a
common generalization of the subalgebra and image relations.
A congruence on A =(A, Σ) is an equivalence relation θ ⊆ A×A suc
h that for any m>0,
f ∈ Σ
m
and a
1
,...,a
m
,b
1
,...,b
m
∈ A,
a
1
θb
1
,...,a
m
θb
m
⇒ f
A
(a
1
,...,a
m
) θf
A
(b
1
,...,b
m
).
Let Con(A) denote the set of all congruences on A =(A, Σ). It includes at least the diagonal
relation ∆
A
and the universal relation ∇
A
. For any θ ∈ Con(A), the quotient algebra A/θ =
(A/θ, Σ) is defined by setting
f
A/θ
(a
1
/θ,...,a
m
/θ)=f
A
(a
1
,...,a
m
)/θ
for all m>0,f ∈ Σ
m
and a
1
,...,a
m
∈ A,andc
A/θ
= c
A
/θ for each c ∈ Σ
0
. The operations
of A/θ are well-defined precisely because θ ∈ Con(A), and the natural mapping
θ
: A → A/θ, a → a/θ,
is an epimorphism from A onto A/θ; it is called the natural homomorphism. Futhermore, the
kernel ker ϕ = {(a, a
) ∈ A ×A | aϕ = a
ϕ} of any homomorphism ϕ : A→Bis a congruence
on A.Moreover,ifϕ is an epimorphism, then A/ ker ϕ
∼
=
B.
386 M. Steinby
Let us recall that a right congruence on a semigroup S is an equivalence θ on S such that,
for any a, b, c ∈ S, aθb implies ac θ bc. Left congruences are defined similarly, and it is clear
that an equivalence on a semigroup is a congruence if and only if it is both a left and a right
congruence.
A mapping p : A → A is an elementary translation of an algebra A =(A, Σ) if
p(ξ)=f
A
(a
1
,...,a
i−1
,ξ,a
i+1
,...,a
m
),
for some m>0, f ∈ Σ
m
,1≤ i ≤ m and a
1
,...,a
i−1
,a
i+1
,...,a
m
∈ A (and where ξ is a
variable ranging over A). Let ETr(A) denote the set of all elementary translations of A.The
set Tr(A)ofalltranslations of A is the smallest set of unary operations on A that contains
the identity map 1
A
: A → A, a → a, and all elementary translations, and is closed under
composition. The following useful fact is easy to verify.
2.1 Lemma Any congruence θ on a Σ-algebra A =(A, Σ) is invariant with respect to every
translation p ∈ Tr(A) of A, i.e., aθb implies p(a) θp(b). In addition, any equivalence on A
invariant with respect to all elementary translations of A, is a congruence on A.
The direct product
i∈I
A
i
=(
i∈I
A
i
, Σ) of an indexed family (A
i
| i ∈ I)ofΣ-algebras
A
i
=(A
i
, Σ) is defined by setting for every j ∈ I,
f
i∈I
A
i
(a
1
,...,a
m
)(j)=f
A
j
(a
1
(j),...a
m
(j)),
for any m>0, f ∈ Σ
m
, a
1
,...,a
m
∈
i∈I
A
i
,andc
i∈I
A
i
(j)=c
A
j
for every c ∈ Σ
0
; recall
that an element of
i∈I
A
i
is a mapping a : I →
i∈I
A
i
such that a(i) ∈ A
i
for every
i ∈ I.Foreachj ∈ I,thej
th
projection π
j
:
i∈I
A
i
→ A
j
,a→ a(j), is easily seen to be
an epimorphism from
i∈I
A
i
onto A
j
. A subalgebra B =(B,Σ) of
i∈I
A
i
is a subdirect
product of the algebras A
i
=(A
i
, Σ) (i ∈ I)ifBπ
j
= A
j
for every j ∈ I, and such a subdirect
product is proper if no π
j
is injective, that is to say the restriction of π
j
to B does not
define an isomorphism between B and A
j
. A monomorphism ϕ : A→
i∈I
A
i
is a (proper )
subdirect decomposition of A =(A, Σ) if Aϕ is a (proper) subdirect product. An algebra is
subdirectly irreducible if it has no proper subdirect decomposition. It is well-known that a
non-trivial algebra A =(A, Σ) is subdirectly irreducible if and only if it has a unique minimal
non-diagonal congruence, that is to say, if and only if
{θ ∈ Con(A) | θ ⊃ ∆
A
}⊃∆
A
.
As usual, we write A
1
×···×A
n
for
i∈I
A
i
when I = {1,...,n} is finite, and for n =0
this product is taken to be a trivial Σ-algebra (that is unique up to isomorphism).
For any class K of Σ-algebras,
(1) S(K) is the class of all algebras isomorphic to a subalgebra of some algebra in K,
(2) H(K) is the class of all images of members of K,and
(3) P(K) is the class of all algebras isomorphic to the direct product of members of K.
AclassK of Σ-algebras is a variety if S(K), H(K), P(K) ⊆ K. The intersection of all
varieties of Σ-algebras containing a given class K of Σ-algebras, the variety generated by K,
is denoted by V(K). It is well known that V(K)=HSP(K) (= H(S(P(K)))). Moreover, any
variety is generated by its subdirectly irreducible members.
If Σ is a set of operation symbols and X a set of symbols disjoint from Σ, then the set
T
Σ
(X)ofΣ-terms with variables in X is the smallest set T such that