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

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

154 P. M. Idziak

The research reported here was motivated by a desire to know which locally ﬁnite varieties

have few and very few models, respectively. Although we have not managed to solve these

problems in the most general setting we have obtained such a characterization for a very

broad class of varieties including most known and well-studied types of algebras, such as

groups, rings, modules, lattices. In those cases we are in the realm of congruence modular

varieties where we have a better than triply exponential upper bound for G-spectra of ﬁnitely

generated subvarieties.

2.7 Theorem (J. Berman and P. Idziak [2]) If V is a ﬁnitely generated, congruence mod-

ular variety, then G

(k) is at most doubly exponential.

The proofs of the results give a deep insight into the structure of locally ﬁnite varieties

with few and very few models. The analysis relies heavily on two major developments of

the late 70’s and early 80’s. One of them is modular commutator theory. The theory had

been introduced by J. D. H. Smith [30] for congruence permutable varieties. It was further

developed by J. Hagemann and Ch. Herrmann [15], H. P. Gumm [14] and R. Freese and

R. McKenzie [13]. The book of Freese and McKenzie contains several important results

and techniques that are extremely useful when studying congruence modular varieties. A

binary operation on congruences that simultaneously generalizes the concept of a commutator

[H, K] of two normal subgroups H, K of a group as well as the ideal multiplication in rings is

deﬁned. The theory shows how some information about algebras or varieties can be recovered

from congruence lattices endowed with this binary operation. Moreover the concept of the

commutator allows us to speak about a solvable, nilpotent or Abelian congruence (or algebra)

as well as about the center of an algebra or the centralizer of a congruence relation.

The second big development in universal algebra that we use is tame congruence theory,

which was created and described in D. Hobby and R. McKenzie [19]. Tame congruence theory

is a tool for studying the local structure of ﬁnite algebras. Instead of considering the whole

algebra and all of its operations at once, tame congruence theory allows us to localize to small

subsets on which the structure is much simpler to understand and to handle. According to

this theory there are only ﬁve possible ways a ﬁnite algebra can behave locally. The local

behavior must be one of the following:

1 a ﬁnite set with a group action on it;

2 a ﬁnite vector space over a ﬁnite ﬁeld;

3 a two element Boolean algebra;

4 a two element lattice;

5 a two element semilattice.

Now, if from our point of view a local behavior of an algebra is ‘bad’ then we can often show

that the algebra itself behaves ‘badly’. For example, since the varieties of distributive lattices

or semilattices have many models (see Example 2.4) then one can argue that in any locally

ﬁnite variety with few models structures of type 4 or 5 cannot occur.

On the other hand it is not true that if the local behavior is ‘good’ then the global one

is, as well. Several kinds of interactions between these small sets can produce fairly messy

Counting ﬁnite algebras 155

global behavior. Such interactions often contribute to produce many models. Also the relative

‘geographical layout’ of those small sets can result in unpredictable phenomena.

The main results of the work in this area are stated in the following theorems. The ﬁrst

one gives a full characterization of locally ﬁnite varieties omitting type 1 with polynomially

many models:

2.8 Theorem (P. Idziak and R. McKenzie [20]) A locally ﬁnite variety omitting type 1

has very few models if and only if it is an aﬃne variety over a ring of ﬁnite representation

type.

Very recently this characterization was extended to all locally ﬁnite varieties:

2.9 Theorem (P.Idziak, R. McKenzie, and M. Valeriote [21]) A locally ﬁnite vari-

ety has very few models if and only if it decomposes into a varietal product of an aﬃne

variety over a ring of ﬁnite representation type, and a sequence of strongly Abelian varieties

equivalent to matrix powers of varieties of G-sets, with constants, for various ﬁnite groups

The work on characterizing locally ﬁnite varieties with at most singly exponentially many

models is still in progress. However, for the case of ﬁnitely generated varieties, omitting

type 1, the following characterization (with more than a 100-page proof) was obtained:

2.10 Theorem (J. Berman and P. Idziak [2]) Let V be a ﬁnitely generated variety omit-

ting type 1.ThenV has few models if and only if the following conditions hold:

(1) V is congruence permutable;

(2) for any ﬁnite subdirectly irreducible algebra A in V with monolith µ and its centralizer

ν =(0:µ) we have:

(a) ν is the solvable radical of A;

(b) ν is comparable to all congruences of A;

(d) the quotient A/ν is either trivial or simple non-Abelian;

(3) the variety N of all nilpotent algebras in V has a ﬁnitely generated clone and N itself

is generated by ﬁnitely many ﬁnite algebras each being of prime power order;

(4) for any ﬁnite simple non-Abelian algebra S in V the ring R

(connected with the

Abelian part of subdirectly irreducible algebras A in V with the quotient A/ν isomor-

phic to S) is of ﬁnite representation type.

The necessity of the conditions in the above theorems was shown by detecting more than

two dozens diﬀerent ways in which ‘bad’ local behavior can occur in an algebra A.Ineach

such situation we are able to produce many non-isomorphic k-generated algebras in the variety

generated by A. After detecting all those instances of ‘bad’ local behavior we formulate global

algebraic conditions that forbid such undesirable behavior. More surprisingly we are able to

show the list of conditions we obtain is actually complete, at least for ﬁnitely generated

156 P. M. Idziak

varieties, i.e., these conditions taken together are suﬃcient for a variety to have few (or very

few) models.

The conditions given in Theorems 2.8 and 2.9 are very simple and easily stated. The

conditions involved in the second characterization (Theorem 2.10) are more complicated,

although they also have a natural algebraic meaning. In both cases we know that the bound

for the number of algebras implies a very transparent and manageable structure. For example,

when specializing our results to groups we get the following:

• every ﬁnitely generated variety of groups has at most doubly exponentially many mod-

els;

• a ﬁnitely generated variety of groups has few models if and only if it is nilpotent;

• a ﬁnitely generated variety of groups has very few models if and only if it is Abelian.

while for commutative rings with unit our characterization reduces to:

• every ﬁnitely generated variety of rings has at most doubly exponentially many models;

• a ﬁnitely generated variety of commutative rings with unit has few models if and only

if the Jacobson radical in the generating ring squares to 0;

• no nontrivial variety of rings with unit has very few models.

Also, from Theorem 2.9 one can infer an earlier result of M. Bilski [3] on semigroup

varieties with very few models. Once more, it conﬁrms nice structure theory for varieties

with polynomially many models:

A locally ﬁnite variety V of semigroups has polynomially bounded G-spectrum if

and only if V is the variety with zero multiplication (satisﬁes the identity xy ≈ uv)

or there is an m such that V is a subvariety of the join L∨R∨A

,whereL is the

variety of left-zero semigroups (satisfying the identity xy ≈ x), R is the variety

of right-zero semigroups (satisfying the identity xy ≈ y) and A

is the variety of

Abelian groups of exponent m treated as semigroups (i.e., satisﬁes the identities

≈ y

and x

m+1

≈ x).

The work on this project started in the fall of 1996 during the semester on Algebraic

Model Theory at the Fields Institute in Toronto.

Since then several researchers have also worked on the topic. Here are the results on

G-spectra I wish to report:

• J. Berman and P. Idziak [2] most of the material described in this talk. It introduces and

motivates the notion of generative complexity, provides many examples and contains a

proof of Theorem 2.10.

• J. Berman and P. Idziak [1] described G-spectra of all Post varieties, i.e., varieties

generated by a single two-element algebra.

• M. Bilski [3] characterized ﬁnitely generated varieties of semigroups with very few mod-

els.

Counting ﬁnite algebras 157

• P. Idziak and R. McKenzie [20] succeeded in characterizing locally ﬁnite varieties omit-

ting type 1 with very few models.

• P. Idziak, R. McKenzie, and M. Valeriote [21] extended the above characterization of

varieties with very few models to all locally ﬁnite varieties.

• R. McKenzie [24] produced several examples of locally ﬁnite varieties with arbitrarily

large free spectra and G-spectra.

References

[1] J. Berman and P. M. Idziak, Counting ﬁnite algebras in the Post varieties, International

Journal of Algebra and Computation 10 (2000), 323–337.

[2] J. Berman and P. M. Idziak, Generative complexity in algebra, manuscript, 2002.

[3] M. Bilski, Generative complexity in semigroups varieties, Journal of Pure and Applied

Algebra 165 (2001), 137–149.

[4] S. Burris, Spectrally determined ﬁrst-order limit laws, in: Logic and Random Struc-

tures (R. Boppana and J. Lynch, eds.), DIMACS Series in Discrete Mathematics and

Theoretical Computer Science 33, Amer. Math. Soc., 1997, 33–52.

[5] S. Burris, Number theoretic density and logical limit laws. Mathematical Surveys and

Monographs 86. American Mathematical Society, Providence, RI, 2001.

[6] S. Burris and K. Compton, Fine spectra and limit laws. I. First order laws, Canad. J.

Math. 49 (1997), 468–498.

[7] S. Burris, K. Compton, A. Odlyzko, and B. Richmond, Fine spectra and limit laws. II.

First-order 0-1 laws, Canad. J. Math. 49 (1997), 641–652.

[8] S. Burris and P. Idziak, A directly representable variety has a discrete ﬁrst-order law,

International J. of Algebra and Computation 6 (1996), 269–276.

[9] D. Clark and P. Krauss, Plain para primal algebras, Algebra Universalis 11 (1980),

365–388.

[10] K. Compton, personal communication.

[11] A. Ehrenfeucht, On the theories categorical in power, Fundamenta Mathematicae 44

(1957), 241–248.

[12] R. Fagin, Generalized ﬁrst-order spectra and polynomial-time recognizable sets, in: Com-

plexity and Computation, SIAM-AMS Proceedings (R.Karp, ed.), 7 (1974), 43–73.

[13] R. Freese and R. McKenzie, Commutator Theory for Congruence Modular Varieties,

London Math. Soc. Lecture Notes 125, Cambridge Univ. Press, Cambridge, 1987.

[14] H. P. Gumm, Geometrical methods in congruence modular varieties, Memoirs Amer.

Math. Soc. 289 (1983).

158 P. M. Idziak

[15] J. Hagemann and C. Herrmann, A concrete ideal multiplication for algebraic systems and

its relation to congruence distributivity, Archive der Mathematik 32 (1979), 234–245.

[16] B. Hart, E. Hrushovski, and M. Laskowski, The uncountable spectra of countable theo-

ries, Annals of Mathematics 152 (2000), 207–257.

[17] B. Hart, S. Starchenko and M. Valeriote, Vaught’s conjecture for varieties, Trans. Amer.

Math. Soc 342 (1994), 173–196.

[18] B. Hart and M. Valeriote, A structure theorem for strongly abelian varieties with few

models, Journal of Symbolic Logic, 56 (1991), 832–852

[19] D. Hobby and R. McKenzie, The Structure of Finite Algebras, Contemporary Mathe-

matics 76, Amer. Math. Soc., Providence, RI, 1988.

[20] P. Idziak and R. McKenzie, Varieties with very few models, Fundamenta Mathematicae,

170 (2001), 53–68.

[21] P. Idziak, R. McKenzie, and M. Valeriote, The structure of locally ﬁnite varieties with

polynomially many models, manuscript 2003.

[22] P. Idziak and J. Tyszkiewicz, Monadic second order probabilities in algebra. Directly

representable varieties and groups, in: Logic and Random Structures (R. Boppana and

J. Lynch, eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer

Science 33, Amer. Math. Soc., 1997, 79–107.

[23] J. F. Lynch, Probabilities of ﬁrst-order sentences about unary functions, Trans. Amer.

Math. Soc. 287 (1985), 543–568.

[24] R. McKenzie, Locally ﬁnite varieties with large free spectra, Algebra Universalis 47

(2002), 303–318.

[25] R. McKenzie and M. Valeriote, The Structure of Decidable Locally Finite Varieties,

Birkh¨auser, Boston, 1989.

[26] M. Morley, Categoricity in power, Transaction American Mathematical Society 114

(1965), 514–538.

[27] R. W. Quackenbush, Algebras with minimal spectrum, Algebra Universalis 10 (1980),

117–129.

[28] R. W. Quackenbush, Enumeration in classes of ordered structures, in: Ordered Sets

(Banﬀ, Alta., 1981), Reidel, Dordrecht-Boston, MA, 1982, 523–554.

[29] S. Shelah, Classiﬁcation Theory, North Holland, Amsterdam, 1990.

[30] J. D. H. Smith, Mal’cev Varieties, Lecture Notes in Mathematics 554, Springer-Verlag,

Berlin, 1976.

[31] W. Taylor, The ﬁne spectrum of a variety, Algebra Universalis 5 (1975), 263–303.

[32] W. Taylor, Equational logic, in: Universal Algebra (G. Gr¨atzer, ed.), 2nd ed., Springer-

Verlag, New York, 1979, 378–400.

Syntactic semigroups and the ﬁnite basis problem

Marcel JACKSON

Department of Mathematics

La Trobe University

Australia

Abstract

The ﬁnite basis problem for semigroups asks when a given ﬁnite semigroup has a ﬁnite

basis for its identities. This problem is one of the most investigated in variety theory. In

this note we look at some easily established equivalent decision problems.

1 Introduction

We show how one may eﬃciently associate with each semigroup (monoid) S asyntactic

semigroup (monoid)

S such that S has a ﬁnite basis of identities if and only if

S has a

ﬁnite basis of identities. Using this and a result of Sapir [14] we obtain a language theoretic

equivalent to the ﬁnite basis problem for semigroups and monoids. While our techniques are

completely elementary, the results may provide a useful alternative approach to the ﬁnite

basis problem for ﬁnite semigroups.

1.1 Syntactic semigroups and monoids

In this section we gather togethor some basic facts concerning syntactic semigroups and

monoids. For a more complete treatment, the reader should consult a book such as [6].

Recall that if S is a monoid, and W is a subset of S, then the syntactic congruence ∼

of W

in S is given by (a, b) ∈∼

if for every c, d ∈ S ∪{1}, cad ∈ W ⇔ cbd ∈ W . (This congruence

is the largest congruence for which W is a union of congruence classes.) In the case where S

is a free semigroup (monoid), the quotient by the syntactic congruence of a subset L is called

the syntactic semigroup (syntactic monoid)ofL, and we denote this by Syn(L)(orSyn

(L),

respectively). A language is regular (accepted by a ﬁnite state automaton) if and only if its

syntactic semigroup (or monoid) is ﬁnite.

We will say that a subset W ⊆ S of a semigroup S is a syntactic subset if the syntactic

congruence of W in S is the diagonal relation. In this case, if ν : A

→ S is a surjective

homomorphism onto S,thenS is isomorphic to the syntactic semigroup of the language

−1

(W ).

If S is a semigroup, then for every s ∈ S, we may take the syntactic congruence of the

singleton {s}; the semigroup S/∼

{s}

is syntactic, and for distinct elements s, t ∈ S there is

an r ∈ S for which s/∼

{r}

= t/∼

{r}

(choosing r to be either s or t suﬃces). Hence there

is a subdirect embedding ν of S into the direct product



s∈S

S/∼

{s}

deﬁned by ν(s):x →

159

V. B. Kudryavtsev and I. G. Rosenberg (eds.),

Structural Theory of Automata, Semigroups, and Universal Algebra, 159–167.

160 M. Jackson

x/∼

{s}

. WenotethatonecanconstructS/∼

{s}

from S in polynomial time: to decide x ∼

{s}

one must calculate uxv and uyv for each u, v ∈ S

. Using a multi-tape Turing machine, we

may encode S by listing the rows of its Cayley table; let n denote the number of squares this

occupies (clearly n ≥|S|

and also n ∈ O(|S|

log

(|S|)) since each element can be encoded

as a binary string of length at most log

(|S|)). Calculating uxv and uyv takes O(n)steps,

while there are O(|S|

)pairsu, v to consider. We direct the reader to [7] for details on these

notions and more information on problems of computational complexity.

For a language W and a word w we deﬁne w

−1

W := {u ∈ W : wu ∈ W } and Ww

−1

{u ∈ W : uw ∈ W }.NowletL be a class of regular languages. For a ﬁnite alphabet A we

denote by L(A)thesetofallmembersofL whose alphabet is A.WesaythatL is a +-variety

of languages if for every ﬁnite alphabet A the following properties hold: L(A) is closed under

taking ﬁnite unions, intersections and complementation; for every letter a ∈ A and every

W ∈L(A)wehavea

−1

W ∈Land Wa

−1

∈L, and for every pair of ﬁnite alphabets A, B

and every homomorphism ν : A

→ B

we have L ∈L(B) implies ν

−1

(L) ∈L(A). If we

replace free semigroups in this deﬁnition by free monoids, the corresponding notion is that

of a ∗-variety.

There is a natural correspondence between +-varieties of regular languages and pseudova-

rieties (classes closed under ﬁnite direct products, subalgebras and homomorphic images) of

ﬁnite semigroups. With each +-variety of regular languages L, we may associate the semi-

group pseudovariety generated by the syntactic semigroups of the languages in L.Conversely

with each pseudovariety of ﬁnite semigroups V we may associate the class of regular languages

whose syntactic semigroups are in V. This class of languages turns out to be a +-variety of

languages and the two correspondences we have described are mutually inverse bijections

between the lattice of semigroup pseudovarieties and the lattice of +-varieties of regular lan-

guages (this is the so-called Eilenberg correspondence [6]). Monoid and ∗-variety versions of

this correspondence are given in the obvious way.

1.2 The ﬁnite basis problem

An identity of a semigroup is an expression u ≈ v where u and v are semigroup words.

A semigroup satisﬁes the identity u ≈ v (in variables A, say) if for every homomorphism

θ : A

→ S, the equality θ(u)=θ(v) holds (written S |= u ≈ v). The set of identities of

S over some ﬁxed countably inﬁnite alphabet is denoted Id(S). The class of all semigroups

satisfying the identities of S is called the variety generated by S. Equivalently, the variety

of S is the class of all homomorphic images of subalgebras of direct powers of S. (Similar

notions hold for general algebras.) We will denote the variety of an algebra S by V(S), and the

ﬁnite members of V(S)byV

ﬁn

(S). When S is ﬁnite, V

ﬁn

(S) coincides with the pseudovariety

generated by S. We will also write S  T when Id(S)=Id(T).

If S is a semigroup without an identity element, then we let S

denote the monoid obtained

by adjoining an identity element. Otherwise we let S

simply denote S. A dual deﬁnition for

zero elements 0 gives S

. The following elementary lemma is useful because we will frequently

be moving between monoids and of semigroups.

1.1 Lemma Let S be a monoid and T a semigroup such that T is contained in the semigroup

variety generated by S.ThenT

is contained in the monoid variety of S.

Proof Let S and T be as in the statement of the lemma. Then, working within the type

The ﬁnite basis problem 161

2,wehaveT ∈ HSP(S). Therefore there are semigroups T

, T

such that T

∈ P(S),

∈ S(T

)andT ∈ H(T

). Clearly, T

is a monoid that is also contained in the monoid

variety of S.IfT

contains the identity element, e say, of T

then T (a quotient of T

)isa

monoid that is contained in the monoid variety of S and we are done.

Now assume that e ∈ T

and let T



denote the submonoid of T

obtained by adjoining

the element e to T

.NotethatT

may already be a monoid, but with an element other than

e acting as the identity, whence T



need not be isomorphic to T

. Without loss of generality

we may assume that there is a congruence θ such that T

/θ = T.

If T has an identity element 1, then choose f ∈ T

such that f/θ = 1, and extend θ to

a congruence θ



on T



by adjoining to θ the pair (e, e) and also the pairs (e, x)and(x, e)if

(f,x)and(x, f)areinθ

.ThisgivesT



/θ



∼

/θ = T, showing T ∈ V(S)asamonoid.

Otherwise, if T has no identity element, then we may extend θ to a congruence on T



by adjoining the pair (e, e). The resulting quotient is isomorphic to T

and again lies in the

monoid variety of S. 2

An equational deduction of an identity p ≈ q from a set of identities Σ, is a sequence of

identities p ≡ p

≈ p

≈···≈p

≡ q such that for each i<nthere is an identity u

≈ v

∈ Σ

or v

≈ u

∈ Σ and a semigroup substitution θ

such that p

i+1

is obtained from p

by replacing

asubwordθ

)withθ

). In this case we write Σ % p ≈ q.Ifn = 1 we will interpret the

deﬁnition of an equational deduction as saying that Σ % p ≈ p.

A basis for the identities of a semigroup S is a subset Σ of Id(S) such that Σ % Id(S).

In 1964, Oates and Powell [10] showed that if G is a ﬁnite group, then G has a ﬁnite basis

of identities. However in 1966 Perkins (see [11]) showed that the semigroup B

given by the

following matrices under matrix multiplication has no ﬁnite identity basis:

























In the subsequent years a great many other examples have shown that the ﬁnite basis prob-

lem—determining which ﬁnite semigroups admit a ﬁnite basis of identities—is very com-

plicated. For general algebras this problem has been shown to be undecidable [8], but for

semigroups the complexity of the problem remains open. For further details we direct the

reader to the most recent survey of this area by Volkov [15].

The following lemma gives some well known equivalents of the ﬁnite basis property. We

omit the proof, but note that the equivalence of (2) and (3) follows from Birkhoﬀ’s complete-

ness theorem for equational logic (which says that Σ % p ≈ q if and only if whenever some

algebra A satisﬁes all of Σ, then also A |= p ≈ q), while the equivalence of (1) and (2) is

another theorem of Birkhoﬀ.

1.2 Lemma (Birkhoﬀ [2]; see also [3]) Let S be a ﬁnite algebra of ﬁnite signature. The

following are equivalent:

(1) Id(S) is ﬁnitely based;

(2) there is an positive integer n such that the n-variable identities in Id(S) are a basis for

Id(S);

(3) there is a positive integer n such that for all algebras A, we have A ∈ V(S) if and only

if all n-generated subalgebras of A are in V(S).

162 M. Jackson

We are going to show that the ﬁnite basis problem for ﬁnite semigroups is equivalent to its

restriction to ﬁnite syntactic semigroups. The idea is easy, so we prove it in an even more

general setting.

The notion of a syntactic congruence can be extended to general algebras by deﬁning

the syntactic congruence ∼

of a subset W of an algebra S as the largest congruence θ for

which W is a union of θ-classes (for further details see [1] for example). A syntactic algebra

is an algebra with a syntactic subset—a subset whose syntactic congruence is the diagonal

relation.

2.1 Proposition If S is an algebra with a one element subalgebra then there is a syntactic

algebra

S such that S 

S.IfS is ﬁnite, then

S is ﬁnite.

Proof Let {e} be a one element subuniverse of S.Foreacht ∈ S \{e},letS

denote S/∼

{t}

As in Section 1.1, S subdirectly embeds into



t∈S\{e}

, and so we have S 



t∈S\{e}

.For

s, t ∈ S \{e},lets

∈



t∈S\{e}

be deﬁned by s

(r)=e/∼

{r}

if r = t and s/∼

{r}

otherwise.

Let W be {s

: s ∈ S},letT be any subalgebra of



t∈S\{e}

containing {s

: s, t ∈ S},and

let

S denote T/∼

.Now

S ∈ V(S) so to complete the proof it will suﬃce to show that each

embeds into

S.Nowforeacht ∈ S \{e}, the subalgebra of T on {s

: s ∈ S} is isomorphic

to S

and {s

: s ∈ S}∩W = {s

}, a syntactic subset of {s

: s ∈ S}. Hence the restriction

of ∼

on T to {s

: s ∈ S} is trivial. Therefore S

embeds into

S, as required. 2

Algebras satisfying the conditions of this proposition are reasonably common—every

monoid, ring, lattice and ﬁnite semigroup has a one-element subalgebra. We note that Propo-

sition 2.1 would follow trivially if the class of syntactic algebras was closed under the taking

of direct products (as is suggested by [6, Proposition VII.1.5]); however a 2-element left zero

semigroup is syntactic, while its square is not.

Unfortunately, the construction in Proposition 2.1 is not very eﬃcient—it seems possible

that

S could have size close to |S|

|S|

. To gain greater eﬃciency, we now restrict our attention

to semigroups.

2.2 Lemma If S is a semigroup with zero element then one can construct a syntactic semi-

group

S equationally equivalent to S in polynomial time.

Proof We are going to follow the proof of Proposition 2.1. We can ﬁx the zero element 0 of

S as the one element subalgebra and then the elements {s

: s, t ∈ S} in



t∈S\{0}

actually

form a subsemigroup, which we choose as T.

Now T has fewer than |S|

elements and can clearly be constructed in polynomial time

from the family {S

: t ∈ S \{0}};infactT is isomorphic to the so-called 0-direct join of

: t ∈ S \{e}}, formed by amalgamating these semigroups at 0 and then setting any

undeﬁned products to equal 0. As each of the |S|−1 semigroups of the form S

can be

constructed from S in polynomial time (see Section 1.1) it follows that

S can be constructed

in polynomial time from S. 2

For each t ∈ S \{0},letA

be an alphabet (with A

∩A

= ∅ for s = t)andν

: A

→ S

a surjective morphism so that S

is the syntactic semigroup of some (regular) subset L

⊆ A

with ν

)={t/∼

{t}

}. One can see from the proof of Lemma 2.2 that

S is (isomorphic to)

Syntactic equivalents

The ﬁnite basis problem 163

the syntactic semigroup of the disjoint union of the languages L

inthefreesemigroupover

the disjoint union of the alphabets A

The proof of Lemma 2.2 does not quite hold for monoids because 0 is not a one element

submonoid and because the subsemigroup on {s

: s, t ∈ S \{0}} is not a submonoid (except

when |S| = 2). However, the submonoid of



t∈S\{0}

generated by {s

: s, t ∈ S \{0}}

is simply {s

: s, t ∈ S \{0}} ∪ {1} (where 1 is the identity element). Choosing this as T

and calculating

S as before, we ﬁnd that each of the S

are monoids that embed into

S as

semigroups and hence are in the semigroup variety of the monoid

S. By Lemma 1.1, they

are in the monoid variety of

S as well. This is clearly still a polynomial time construction

and hence Lemma 2.2 holds for monoids as well. In fact we do not need monoids with zero

to state this result. First consider the following lemma.

2.3 Lemma If S is a semigroup whose variety contains the variety of semilattices then S 

Proof If S = S

we are done, so assume that S does not contain a zero element. Certainly

S lies within the variety of S

. Conversely, as the variety of S contains the two element

semilattice 2 (with universe {0, 1}), it also contains S × 2. The semigroup S

is isomorphic

to the Rees quotient of S × 2 by the ideal {(x, 0) : x ∈ S}. 2

2.4 Lemma Every ﬁnite monoid S is equationally equivalent to the syntactic monoid of

some regular language that can be constructed from S in polynomial time.

Proof By considering the one-generated submonoids of S it can be seen that the monoid

variety of S fails to contain the variety of semilattice monoids if and only if S is a ﬁnite group.

If S is a group then the syntactic congruence of any singleton subset of S is the diagonal

relation and so S is the syntactic monoid of a regular language and we are done.

Now say that the monoid variety of S contains the variety of semilattice monoids. Then

by Lemma 2.3 it can be generated by a monoid with zero element. A syntactic monoid

generating the same variety is then given by the argument following Lemma 2.2. 2

In [15], the question is asked as to whether or not the ﬁnite basis problem for syntactic

semigroups is decidable (that is, algorithmically solvable). It is clear from Proposition 2.1

that this problem is equivalent to the general ﬁnite basis problem, but in fact we can use

Lemma 2.2 to show that these problems are polynomially equivalent.

We ﬁrst need the following result from [9].

2.5 Lemma (Mel’nik [9]) AsemigroupS is ﬁnitely based if and only if S

is ﬁnitely based.

Proof If V(S) contains the variety of semilattices then by Lemma 2.3 we have S  S

.So

we may assume throughout that V(S) does not contain the variety of semilattices.

Let us say that an identity u ≈ v is homotypical if the variables in u are the same as

those in v (this is also called regular ). The identities of 2 areexactlytheclassofhomotypical

semigroup identities and so it follows that S satisﬁes some non-homotypical identity. In

this case S

generates the smallest variety containing V(S) that is deﬁnable by homotypical

identities. Following [9], it can be shown that S has a basis of the form Σ∪(x

)

≈ x

for some m ∈ N and where Σ is a collection of homotypical identities. It is shown in [9] that

one can ﬁnd a basis for S

by adjoining to Σ a ﬁnite set of homotypical identities. Thus if S