Profinite semigroups and applications in Computer Science Jorge Almeida Departamento Matem´atica, CMUP Faculdade de Ciˆencias, Universidade do Porto Porto, Portugal http://www.fc.up.pt/cmup/jalmeida/ October, 2011 ´Ustav matematiky a statistiky Pˇr´ırodovˇedeck´a fakulta Masarykova univerzita 1 / 113 Abstract Finite semigroups appear naturally in Computer Science, namely as syntactic semigroups of regular languages, transition semigroups of finite automata, or as finite recognizing devices on their own. Eilenberg’s correspondence theorem gives a general framework for the classification of regular languages through algebraic properties of their syntactic semigroups. Here is the resulting typical problem on the algebraic side: a recursively enumerable set R of finite semigroups is given and one wishes to decide whether a given finite semigroup is a homomorphic image of a subsemigroup of a finite product of members of R. Since such a problem is often undecidable, special techniques have been devised to handle special cases. Relatively free profinite semigroups turn out to be quite useful in this context. They play the role of free algebras in Universal Algebra, capturing in their algebraic-topological/metric structure combinatorial properties of the corresponding classes of languages. The aim of this short course is to introduce reltively free profinite semigroups and to explore two topics in which there have been significant recent developments, namely the separation of a given word from a given regular language by a regular language of a special type (for instance, a group language), and connections with symbolic dynamics. Tentative syllabus and preliminary references: 1. Relatively free profinite semigroups. (1 lecture) Reference: [1] J. Almeida, Profinite semigroups and applications, in ”Structural Theory of Automata, Semigroups, and Universal Algebra”, V. B. Kudryavtsev and I. G. Rosenberg (eds.), Proceedings of the NATO Advanced Study Institute on Structural Theory of Automata, Semigroups and Universal Algebra (Montr´eal, Qu´ebec, Canada, 7-18 July 2003), Springer, New York, 2005, pp. 1-45. 2. 2. Separating words and regular languages. (2 lectures) Reference: [2] S. Margolis, M. Sapir, and P. Weil, Closed subgroups in pro-V topologies and the extension problem for inverse automata, Int. J. Algebra and Comput. 11 (2001) 405-455. 3. Relatifely free profinite semigroups and Symbolic Dynamics. (2 lectures) Reference: [1] (see above). 2 / 113 Part I Relatively free profinite semigroups 3 / 113 Outline Language recognition devices Eilenberg’s correspondence Decidable pseudovarieties Metrics associated with pseudovarieties Pro-V semigroups Reiterman’s Theorem Examples of relatively free profinite semigroups Pseudowords as operations Implicit signatures 4 / 113 A regular language is a subset of the free monoid A∗ on an alphabet A admitting a regular expression, i.e., a formal expression describing it in terms of the empty set ∅ and the letters a ∈ A using the following operations: (K, L) → K ∪ L (union) (K, L) → KL (concatenation) L → L∗ (Kleene star) The syntactic congruence of the language L ⊆ A∗ is the binary relation σL on A∗ defined by: u σL v if ∀ x, y ∈ A∗ (xuy ∈ L ⇔ xvy ∈ L). The syntactic monoid M(L) of the language L ⊆ A∗ is the quotient monoid A∗/σL. 5 / 113 Theorem 1.1 The following conditions are equivalent for a language L over a finite alphabet A: (1) L is regular; (2) L is recognized by some finite automaton; (3) L is recognized by some finite complete deterministic automaton; (4) the syntactic monoid A∗/σL on A∗ is finite; (5) L is recognized by some homomorphism ϕ : A∗ → M into a finite monoid, in the sense that L = ϕ−1ϕL. Corollary 1.2 The set Reg(A∗) of all regular languages over the alphabet A is a Boolean subalgebra of the Boolean algebra of all subsets of A∗. 6 / 113 Example: (restricted) Dyck languages Regular expression: L1 = (ab)∗ Minimal (incomplete) automaton: 0 1 a bTransition monoid (M(L1)): 0 1 a 1 b - 0 ab 0 ba - 1 0 - a b ab ba 0 a 0 ab 0 a 0 b ba 0 b 0 0 ab a 0 ab 0 0 ba 0 b 0 ba 0 0 0 0 0 0 0 Presentation: a, b; aba = a, bab = b, a2 = b2 = 0 . One may then compute Green’s relations, which are summarized in the following eggbox picture: • same row: elements generate the same right ideal (R) • same column: elements generate the same left ideal (L) • elements above are factors of elements below (≥J ) • ∗ e marks an idempotent (e2 = e) • the“eggboxes”are the J -classes (J = ≥J ∩ ≤J ) • D = R ◦ L = L ◦ R • in a finite monoid, D = J *0 a *ab *ba b *1 7 / 113 Regular expression: L2 = (a(ab)∗ b)∗ Minimal (incomplete) automaton: 0 1 2 a b a b Presentation of syntactic monoid M(L2): a, b; aba = a, bab = b, a2 b2 a2 = a2 , b2 a2 b2 = b2 , ab2 a = ba2 b, a3 = b3 = 0 Eggbox picture: *0 aa aab *aabb baa *abba abb *bbaa bba bb a *ab *ba b *1 8 / 113 Dyck language: L∞ = n≥0 Ln, where L0 = {1}, Ln+1 = (aLnb)∗. Recognition by infinite automaton: 0 1 2 · · · n n + 1 · · · a b a b a b a b a b a b Syntactic monoid: M(L∞) = a, b; ab = 1 . Eggbox picture: ∗ 1 a a2 · · · an an+1 · · · b ∗ ba ba2 · · · ban ban+1 · · · b2 b2 a ∗ b2 a2 · · · b2 an b2 an+1 · · · ... ... ... ... ... ... bn bn a bn a2 · · · ∗ bn an bn an+1 · · · bn+1 bn+1 a bn+1 a2 · · · bn+1 an ∗ bn+1 an+1 · · · ... ... ... ... ... ... 9 / 113 Exercise 1.3 Consider the transition semigroup S of the following infinite automaton: 2 4 c ÐÐ 6 c ÐÐ 8 c ÐÐ · · · c ~~ 1 a yy b GG 3 a yy b GG 5 a yy b GG 7 a yy b GG · · · 1. Note that, in S, aca is a factor of a but a is not regular. 2. Verify that S admits the following presentation: a, b, c; baca = a, bacb = b2 ac = b, cbac = c, a2 = ab = bc = c2 = 0 . 3. Show that S has two J -classes, one of which is reduced to zero. 4. Show that the non-trivial J -class of S consists of two infinite D-classes, one of which is regular and a bicyclic monoid, while the other is not regular and has only one L-class. All H-classes of S are trivial. 10 / 113 Outline Language recognition devices Eilenberg’s correspondence Decidable pseudovarieties Metrics associated with pseudovarieties Pro-V semigroups Reiterman’s Theorem Examples of relatively free profinite semigroups Pseudowords as operations Implicit signatures 11 / 113 A variety of languages is a correspondence V associating with each finitely generated free monoid A∗ a set V(A∗) of languages over the finite alphabet A such that the following conditions hold: 1. V(A∗ ) is a Boolean subalgebra of Reg(A∗ ); 2. if L ∈ V(A∗ ) and a ∈ A, then the following languages also belong to V(A∗ ): a−1 L = {w ∈ A∗ : aw ∈ L} La−1 = {w ∈ A∗ : wa ∈ L}; 3. if ϕ : A∗ → B∗ is a homomorphism and L ∈ V(B∗ ), then ϕ−1 (L) ∈ V(A∗ ). A pseudovariety of monoids is a nonempty class V of finite monoids which is closed under taking homomorphic images, submonoids, and finite direct products. 12 / 113 Theorem 2.1 (Eilenberg [Eil76]) The complete lattices of varieties of languages and of pseudovarieties of monoids are isomorphic. More precisely, the following correspondences are mutually inverse isomorphisms between the two lattices: to a variety V of languages, associate the pseudovariety V generated by all syntactic monoids M(L) with L ∈ V(A∗) for some finite alphabet A; to a pseudovariety V, associate the variety of languages V such that, for each finite alphabet A, V(A∗) consists of the languages L ⊆ A∗ such that M(L) ∈ V. 13 / 113 Thus, problems about varieties of languages admit a translation into problems about pseudovarieties of monoids. For instance, to determine if a language L ⊆ A∗ belongs to smallest variety of languages containing two given varieties of languages V and W is equivalent to determine if M(L) belongs to the pseudovariety join V ∨ W. Typically, we are given a recursively enumerable set R of finite monoids and we want to determine an algorithm to decide whether a given finite monoid M belongs to the pseudovariety V(R) generated by R. 14 / 113 Mutatis mutandis, we have languages L ⊆ A+ without the empty word 1; syntactic congruence σL of L over A+: u σL v if ∀ x, y ∈ A∗ (xuy ∈ L ⇔ xvy ∈ L). syntactic semigroup A+/σL; varieties of languages without the empty word; pseudovarieties of semigroups; Eilenberg’s correspondence in this setting. 15 / 113 Examples of pseudovarieties: S: all finite semigroups I: all singleton (trivial) semigroups G: all finite groups Gp: all finite p-groups A: all finite aperiodic semigroups Com: all finite commutative semigroups J: all finite J -trivial semigroups R: all finite R-trivial semigroups L: all finite L-trivial semigroups Sl: all finite semilattices RZ: all finite right-zero semigroups B: all finite bands N: all finite nilpotent semigroups K: all finite semigroups in which idempotents are left zeros D: all finite semigroups in which idempotents are right zeros 16 / 113 Important examples of instances of Eilenberg’s correspondence A language L ⊆ A+ is said to be star free if it admits an expression in terms of the languages {a} (a ∈ A) using only the operations: ∪ , A+ \ , and concatenation. Theorem 2.2 ([Sch65]) A language over a finite alphabet is star free if and only if its syntactic semigroup is finite and aperiodic. 17 / 113 A language L ⊆ A∗ is piecewise testable if it is a Boolean combination of languages of the form A∗a1A∗a2A∗ · · · anA∗, with the ai ∈ A. Theorem 2.3 ([Sim75]) A language over a finite alphabet is piecewise testable if and only if its syntactic semigroup is finite and J -trivial. A language L ⊆ A∗ is locally testable if it is a Boolean combination of languages of the forms A∗u, A∗vA∗, and wA∗, where u, v, w ∈ A+. Theorem 2.4 ([BS73, MP71]) A language L over a finite alphabet is locally testable if and only if its syntactic semigroup S is finite and a local semilattice (i.e., eSe is a semilattice for every idempotent e ∈ S). 18 / 113 Outline Language recognition devices Eilenberg’s correspondence Decidable pseudovarieties Metrics associated with pseudovarieties Pro-V semigroups Reiterman’s Theorem Examples of relatively free profinite semigroups Pseudowords as operations Implicit signatures 19 / 113 Definition 3.1 We say that a pseudovariety V is decidable if there is an algorithm which, given a finite semigroup S as input, produces as output, in finite time, YES or NO according to whether or not S ∈ V. The semigroup S may be given in various ways: extensively, meaning the complete list of its elements together with its multiplication table; as the transformation semigroup on a finite set Q generated by a finite set A of transformations of Q ; → transition semigroup of a finite automaton (Q, A, δ, I, F); by means of a presentation. Different ways of describing S may lead to different complexity results, when such an algorithm exists. 20 / 113 Of course, not all pseudovarieties are decidable. For instance, if P is a non-recursive set of primes, then the pseudovariety AbP, generated by all groups Z/pZ with p ∈ P, contains a group Z/qZ of prime order q if and only if q ∈ P. Since there are non-recursive sets of primes P, there are pseudovarieties of the form AbP which are not decidable. Question 3.2 (Very imprecise!!) Are all“natural”pseudovarieties decidable? 21 / 113 There are many ways to construct new pseudovarieties from known ones, that is by applying operators to pseudovarieties. We proceed to introduce some natural operators. Definition 3.3 Given a pseudovariety V, consider the classes of all finite semigroups S such that, respectively: LV: eSe ∈ V for every idempotent e ∈ S; EV: E(S) ∈ V, where E(S) is the subsemigroup generated by the set E(S) of all idempotents of S; DV: the regular J -classes of S (are subsemigroups which) belong to V; V: the subgroups of S belong to V; 22 / 113 Let S be a finite semigroup and let D be one of its regular D-classes. Let ∼ be the equivalence relation on the set of group elements of D generated by the identification of elements which are either R or L-equivalent. A block of D is the Rees quotient of the subsemigroup of S generated by a ∼-class modulo the ideal consisting of the elements which do not lie in D. * * * * * * * * * * * * * * * * 1 2 3 4 5 6 * * * * * * * * 1 3 6 2 4 5 The blocks of S are the blocks of its regular D-classes. Definition 3.4 For a pseudovariety V, let BV be the class of all finite semigroups whose blocks lie in V. 23 / 113 Proposition 3.5 For a pseudovariety V, the classes BV, DV, EV, LV, V are pseudovarieties. Moreover, if V is decidable then so are those pseudovarieties. Proof. We consider only the case of LV, leaving all other cases as exercises. If ϕ : S → T is an onto homomorphism, with S ∈ S, and f ∈ E(T), then ∃e ∈ ϕ−1 (f ) ∩ E(S) and ϕ|eSe : eSe → fTf is an onto homomorphism ∴ LV is closed under taking homomorphic images. If S ≤ T and e ∈ E(S), then eSe ≤ eTe ∴ LV is closed under taking subsemigroups. If S, T are semigroups, e ∈ E(S), and f ∈ E(T), then (e, f )(S × T)(e, f ) eSe × fTf ∴ LV is closed under taking finite direct products. Given a finite semigroup, one can compute its set of idempotents E(S) and, for each e ∈ E(S), the monoid eSe. Provided V is decidable, one can then effectively check whether eSe ∈ V. Hence one can effectively check whether S ∈ LV. 24 / 113 But, the most interesting operators are defined not in structural terms but rather by describing generators: the resulting pseudovariety is given as the smallest pseudovariety containing certain semigroups which are constructed from those in the argument pseudovarieties. Definition 3.6 We say that a semigroup S divides a semigroup T, or that S is a divisor of T, and we write S T, if S is a homomorphic image of a subsemigroup of T. Proposition 3.7 Let C be a class of finite semigroups. Then the smallest pseudovariety V(C) containing C consists of all divisors of products of the form S1 × · · · × Sn with S1, . . . , Sn ∈ C. In particular, if C is closed under finite direct product, then V(C) consists of all divisors of elements of C. 25 / 113 Let S and T be semigroups and let ϕ : T1 → End S be a homomorphism of monoids, with endomorphisms acting on the left. For s ∈ S and t ∈ T1, let ts = ϕ(t)(s). The semidirect product S ∗ϕ T is the set S × T under the multiplication (s1, t1) · (s2, t2) = (s1 t1 s2, t1t2). Definition 3.8 The semidirect product V ∗ W of the pseudovarieties V and W is the smallest pseudovariety containing all semidirect products S ∗ T with S ∈ V and T ∈ W. Proposition 3.9 The pseudovariety V ∗ W consists of all divisors of semidirect products of the form S ∗ T with S ∈ V and T ∈ W. Proposition 3.10 The semidirect product of pseudovarieties is associative. 26 / 113 Definition 3.11 The Mal’cev product V m W of two pseudovarieties V and W is the smallest pseudovariety containing all finite semigroups S for which there exists a homomorphism ϕ : S → T such that T ∈ W and ϕ−1(e) ∈ V for all e ∈ E(T). Given two semigroups S and T, a relational morphism S → T is a relation µ : S → T with domain S such that µ is a subsemigroup of S × T. Proposition 3.12 The pseudovariety V m W consists of all finite semigroups S such that there is a relational morphism µ : S → T such that T ∈ W and µ−1(e) ∈ V for all e ∈ E(T). 27 / 113 For a semigroup S, denote by P(S) the semigroup of subsets of S under the product operation X · Y = {xy : x ∈ X, y ∈ Y }. Note that the empty set ∅ is a zero and P (S) = P(S) \ {∅} is a subsemigroup. Definition 3.13 For a pseudovariety V, denote by PV: the pseudovariety generated by all semigroups of the form P(S), with S ∈ V; P V: the pseudovariety generated by all semigroups of the form P (S), with S ∈ V. Proposition 3.14 The pseudovariety PV consists of all divisors of semigroups of the form P(S) with S ∈ V. Similar statement for P . 28 / 113 Some examples of results on finite semigroups formulated in terms of these operators: 1. J = N m Sl 2. DA = LI m Sl, DS = LG m Sl 3. R = Sl ∗ J [Sti73] 4. G ∨ Com = ZE (the pseudovariety of all finite semigroups in which idempotents are central) [Alm95] 5. ESl = Sl ∗ G = Sl m G = Inv (the pseudovariety generated by all finite inverse semigroups) [MP87, Ash87, Pin95], ER = R ∗ G [Eil76], EDS = DS ∗ G [AE03] 6. PG = J ∗ G = J m G = EJ = BG [MP84, HR91, Ash91, HMPR91, Pin95], PJ = PV(Y ) [PS85, Alm95] where Y = Synt(a∗bc∗) 7. S = n≥0(A ∗ G)n ∗ A [KR65] 29 / 113 S = n≥0 (A ∗ G)n ∗ A The (Krohn-Rhodes) hierarchy (A ∗ G)n ∗ A n≥0 is strict. The smallest n such that a given finite semigroup S belongs to (A ∗ G)n ∗ A is called the complexity of S, denoted c(S). Let Tn denote the full transformation semigroup of an n-element set It is known that c(Tn) = n − 1 [Eil76] and so certainly c(S) ≤ |S| (since S → TS1 ). Note 3.15 To know an algorithm to compute the complexity function is equivalent to know algorithms to decide the membership problem for each pseudovariety in the Krohn-Rhodes hierarchy. 30 / 113 This brings us to the following basic question: Question 3.16 For the operators which were defined above in terms of generators, do they preserve decidability? Theorem 3.17 (Albert, Baldinger & Rhodes’1992 [ABR92]) There exists a finite set Σ of identities such that Com ∨ [[Σ]] is undecidable. Let C2,1 = a; a2 = 0 1. Theorem 3.18 (Auinger & Steinberg’2003 [AS03]) There exists a decidable pseudovariety of groups U such that the following pseudovarieties are all undecidable: Sl ∗ U (= Sl m U), V(C2,1) ∨ U, PU (= P U). 31 / 113 The pseudovariety U is defined to be U = p∈A Gp ∗ (Gf (p) ∩ Com) ∨ p∈D (Gp ∩ Com) where: A and B constitute a computable partition of the set of primes into two infinite sets; f : A → B is an injective recursive function whose range C = f (A) is recursively enumerable but not recursive; D = B \ C is not recursively enumerable. Exercise 3.19 Show that U is decidable. 32 / 113 Outline Language recognition devices Eilenberg’s correspondence Decidable pseudovarieties Metrics associated with pseudovarieties Pro-V semigroups Reiterman’s Theorem Examples of relatively free profinite semigroups Pseudowords as operations Implicit signatures 33 / 113 Let V be a pseudovariety of semigroups. For two words u, v ∈ A+, and T ∈ V, let T |= u = v if, for every homomorphism ϕ : A+ → T, ϕ(u) = ϕ(v), rV(u, v) = min{|S| : S ∈ V and S |= u = v}, dV(u, v) = 2−rV(u,v) where we take min ∅ = ∞ and 2−∞ = 0. Note 4.1 The following hold for u, v, w, t ∈ A+ and a positive integer n: (1) rV(u, v) ≥ n if and only if, for every S ∈ V with |S| < n, S |= u = v; (2) dV(u, v) ≤ 2−n if and only if, for every S ∈ V with |S| < n, S |= u = v; (3) dV(u, v) = 0 if and only if, for every S ∈ V, S |= u = v; (4) min{rV(u, v), rV(v, w)} ≤ rV(u, w); (5) min{rV(u, v), rV(w, z)} ≤ rV(uw, vz). 34 / 113 Definition 4.2 A function d : X × X → R≥0 is said to be a pseudo-ultrametric on the set X if the following properties hold for all u, v, w ∈ X: 1. d(u, u) = 0; 2. d(u, v) = d(v, u); 3. d(u, w) ≤ max{d(u, v), d(v, w)}. We then also say that X is a pseudo-ultrametric space. If instead of Condition 3, the following weaker condition holds 4. d(u, w) ≤ d(u, v) + d(v, w) (triangle inequality). then d is said to be a pseudo-metric on X, and X is said to be a pseudo-metric space. If the following condition holds 5. d(u, v) = 0 if and only if u = v, then we drop the prefix“pseudo”. 35 / 113 A function f : X → Y between two pseudo-metric spaces is said to be uniformly continuous if the following condition holds: ∀ > 0 ∃ δ > 0 ∀ x1, x2 ∈ X d(x1, x2) < δ ⇒ d(f (u), f (v)) < . Proposition 4.3 1. The function dV is a pseudo-ultrametric on A+ . 2. The multiplication is contractive: dV(u1u2, v1v2) ≤ max{dV(u1, v1), dV(u2, v2)}. In particular, the multiplication on A+ is uniformly continuous. For a (pseudo-ultra)metric d, u ∈ X, and a positive real number , consider the open ball B (u) = {v ∈ X : d(u, v) < }. The point u is the center and is the radius of the ball. A metric space that can be covered by a finite number of balls of any given positive radius is said to be totally bounded. 36 / 113 Proposition 4.4 The metric space (A+, dV) is totally bounded. Proof. Let n be a positive integer such that 2−n < . Note that, up to isomorphism, there are only finitely many semigroups of cardinality at most n in V. For such a semigroup Si consider all possible homomorphisms ϕi,j : A+ → Si , let S = i,j Si and ϕ : A+ → S u → (ϕi,j (u))i,j . Then S ∈ V and dV(u, v) < 2−n if and only if ϕ(u) = ϕ(v). For each s ∈ S, choose us ∈ A+ such that ϕ(us) = s. For v ∈ A+ and s = ϕ(v), we have ϕ(v) = ϕ(us), and so v ∈ B (us). We have thus shown that A+ = s∈S B (us). 37 / 113 A sequence (un)n in a (pseudo-ultra)metric space X is said to be a Cauchy sequence if ∀ > 0 ∃ N m, n ≥ N ⇒ d(um, un) < . Note that every convergent sequence is a Cauchy sequence. The space X is complete if every Cauchy sequence in X converges in X. 38 / 113 Theorem 4.5 Let X be a pseudo-(ultra)metric space. Then there exists a complete metric space ˆX and a uniformly continuous function ι : X → ˆX with the following universal property: for every uniformly continuous function f : X → Y into a complete metric space Y , there exists a unique uniformly continuous function ˆf : ˆX → Y such that ˆf ◦ ι = f . X ι GG f 22 ˆX ˆf  Y . X ι  γ 11 ˆX ˆγ CC Z. ˆι kk In particular, if γ : X → Z is another uniformly continuous function into another complete metric space with the above universal property then the induced unique uniformly continuous mappings ˆι : ˆX → Z and ˆγ : Z → ˆX are mutually inverse. The“unique”space ˆX of Theorem 4.5 is called the Hausdorff completion of X. 39 / 113 It may be constructed in the same way that the real numbers are obtained by completion of the rational numbers. Here is a sketch: (a) consider the set C ⊆ XN of all Cauchy sequences of elements of X; (b) note that, for s = (un)n and t(vn)n in C, the sequence of real numbers d(un, vn) n is a Cauchy sequence and, therefore, it converges; its limit is denoted d(s, t); |d(un, vn) − d(um, vm)| ≤ |d(un, vn) − d(un, vm)| + |d(un, vm) − d(um, vm)| ≤ d(un, um) + d(vn, vm) (c) Step (B) defines a pseudo-(ultra)metric on C; (d) for s = (un)n and t(vn)n in C, let s ∼ t if d(s, t) = 0; this is an equivalence relation on C; the class of s is denoted s/∼; (e) let ˆX = C/∼ and put d(s/∼, t/∼) = d(s, t), which can be easily checked to be defined; (f) finally, let ι : X → ˆX map each u ∈ X to the ∼-class of the constant sequence (u)n, and check that this mapping is uniformly continuous and has the appropriate universal property. 40 / 113 Note that ι(X) is dense in ˆX. In particular, we may consider the Hausdorff completion of the pseudo-ultrametric space (A+, dV), which is denoted ΩAV. Since the multiplication of A+ is uniformly continuous with respect to dV, it induces a uniformly continuous multiplication in ΩAV: A+ × A+ µ (mult.) GG ι×ι  A+ ι  ΩAV × ΩAV ˆµ GG ΩAV 41 / 113 We endow each finite semigroup S with the discrete metric: d(s, t) = 0 if s = t 1 otherwise Since ι(A+) is dense in ΩAV, multiplication in ΩAV is associative, and thus ΩAV is naturally a semigroup. From hereon, we write d for dV. The context should leave clear which pseudovariety is involved. 42 / 113 Note that, for S ∈ V, every homomorphism ϕ : A+ → S is uniformly continuous with respect to d. d(u, v) < 2−|S| ⇒ d(ϕ(u), ϕ(v)) = 0. Thus, ϕ induces a unique uniformly continuous mapping ˆϕ : ΩAV → S such that the following diagram commutes: A+ ι GG ϕ 44 ΩAV ˆϕ  S. One can easily check that ˆϕ is a homomorphism: ˆϕ(uv) = lim ϕ(ι(unvn)) = lim ϕ(ι(un))ϕ(ι(vn)) = lim ϕ(ι(un)) · lim ϕ(ι(vn)) = ˆϕ(u) ˆϕ(v). 43 / 113 Given u, v ∈ ΩAV and S ∈ V, we write S |= u = v if, for every homomorphism ϕ : A+ → S (which is determined by ϕ|A), the equality ˆϕ(u) = ˆϕ(v) holds. We call the formal equality u = v a V-pseudoidentity. Note that, if u = lim un, v = lim vn, and S ∈ V, then S |= u = v if and only if S |= un = vn for all sufficiently large n. Given distinct elements u, v ∈ ΩAV, there exists a positive integer m such that d(u, v) ≥ 2−m . Consider sequences of words (un)n and (vn)n such that u = lim ι(un) and v = lim ι(vn). Then, for sufficiently large n, d(u, ι(un)) < 2−m and d(v, ι(vn)) < 2−m . Hence d(un, vn) = d(ι(un), ι(vn)) ≥ 2−m for all sufficiently large n. It follows that every S ∈ V with |S| < m fails the identity un = vn and, therefore, also the pseudoidentity u = v. 44 / 113 Proposition 4.6 For u, v ∈ ΩAV, we have d(u, v) = 2−r(u,v), where r(u, v) = min{|S| : S ∈ V and S |= u = v}. Proof. We have already shown that d(u, v) ≥ 2−m implies r(u, v) ≤ m. The converse, as well as how the equivalence gives the proposition are left as an exercise. 45 / 113 Recall that a metric space is compact if every sequence admits some convergent subsequence. Equivalently, every covering by open subsets contains a finite covering. Proposition 4.7 1. If X is a totally bounded pseudo-metric space, then ˆX is also totally bounded. 2. If X is a totally bounded complete metric space, then X is compact. 46 / 113 Proof. 1. Given > 0, let u1, . . . , um ∈ X be such that X = m i=1 B /2(ui ). Then ˆX = m i=1 B (ι(ui )) since every element of ˆX is at distance at most /2 of some element of ι(X). 2. For each positive integer m, let Fm be a finite subset of X such that X = x∈Fm B2−m (x) and consider an arbitrary sequence (un)n in X. For infinitely many indices n, the un belong to the same B2−1 (x1). Let k1 be the first of these indices. Similarly, among the remaining such indices, there are infinitely many n such that the un belong to the same B2−2 (x2). We let k2 be the first of them. And so on. We thus construct a subsequence (ukn )n with the property that d(ukm , ukn ) ≤ 2− min{m,n}+1 , if p = min{m, n}, then ukm , ukn ∈ B2−p (xp), which yields d(ukm , ukn ) ≤ d(ukm , xp) + d(xp, ukn ) ≤ 2−p + 2−p whence a Cauchy sequence and, therefore, convergent. 47 / 113 Outline Language recognition devices Eilenberg’s correspondence Decidable pseudovarieties Metrics associated with pseudovarieties Pro-V semigroups Reiterman’s Theorem Examples of relatively free profinite semigroups Pseudowords as operations Implicit signatures 48 / 113 By a pro-V semigroup we mean a semigroup S endowed with a metric such that the following properties hold: 1. S is compact; 2. the multiplication is uniformly continuous (metric semigroup); 3. for every pair u, v of distinct elements of S, there is a uniform continuous homomorphism ϕ : S → T into a semigroup from V such that ϕ(u) = ϕ(v) (S residually in V). By a profinite semigroup we mean a pro-S semigroup. 49 / 113 Proposition 5.1 Let S be a pro-V semigroup. Then there is a sequence (Sn)n∈N of semigroups from V and an injective homomorphism ϕ : S → n∈N Sn such that, for each component projection πm : n∈N Sn → Sm, the homomorphism πm ◦ ϕ is uniformly continuous. We may define in n∈N Sn a metric structure by letting d(u, v) = n∈N 2−n dn(πn(u), πn(v)) where dn is the discrete metric on Sn. Then ϕ is uniformly continuous. In particular, the image T of ϕ is closed in n∈N Sn, being a compact subset. 50 / 113 Note that the sequence (Sn)n∈N may be chosen so that there is a finite bound on the number of generators of the Sn if and only if S is finitely generated in the sense that there is a finite subset which generates a dense subsemigroup. On the other hand, if there is no such bound, one can show that S cannot have a countable dense subset, while it is easy to see that a compact metric space always admits a countable dense subset. Proposition 5.2 Every pro-V metric semigroup is finitely generated. 51 / 113 For a finite set A, we say that the pro-V semigroup S is freely generated by A if there is a mapping γ : A → S such that γ(A) generates a dense subsemigroup of S and the following universal property is satisfied, where ϕ : A → T is an aribtrary mapping into a pro-V semigroup T, and ˆϕ is a unique continuous homomorphism: A γ GG ϕ 11 S ˆϕ  T Theorem 5.3 For a pseudovariety of semigroups V and a finite set A, the metric semigroup ΩAV is a pro-V semigroup freely generated by A via the mapping ι|A. 52 / 113 Proof. Let S be a pro-V semigroup and let (Sn)n∈N be a countable family of semigroups from V as given by Proposition 5.1, so that there is an embedding ϕ : S → n∈N Sn with each composite function πn ◦ ϕ : S → Sn uniformly continuous. Given a mapping ψ : A → S, let ψn = πn ◦ ψ. A ι|A GG ψ  ψn 22 ΩAV ˆψn  S πn GG Sn The family ( ˆψn)n∈N induces a homomorphism ˆψ : ΩAV → n∈N Sn. Its image lies in the closed subsemigroup T, whence it lifts to the required continuous homomorphism ΩAV → S. It is uniformly continuous because every continuous mapping from a compact metric space into another metric space is uniformly continuous. 53 / 113 A subset of a metric space is said to be clopen if it is both closed and open. A metric space is said to be zero-dimensional if every open set is a union of clopen subsets. Proposition 5.4 Every pro-V semigroup is zero-dimensional. Proof. Let u be an element of the pro-V semigroup S. It suffices to show that the open ball B (u) contains some clopen set which contains u. For each v ∈ S \ B (u), let ϕv : S → Tv be a uniformly continuous homomorphism into a semigroup from V such that ϕv (u) = ϕv (v). Then Kv = ϕ−1 v ϕv (v) is a clopen set which contains v but not u. In particular, the Kv form a clopen covering of the closed set S \ B (u), from which a finite covering F can be extracted. The union of the clopen sets in F is itself a clopen set K. Note that S \ K is also clopen, contains u, and is contained in B (u). 54 / 113 For a mapping ϕ : S → T, let ker ϕ = {(u, v) : ϕ(u) = ϕ(v)} be the kernel of ϕ. Theorem 5.5 An A-generated profinite semigroup S is a continuous homomorphic image of ΩAV if and only if it is a pro-V semigroup. Corollary 5.6 Let S be a pro-V semigroup and suppose that ϕ : S → T is a continuous homomorphism onto a finite semigroup. Then T ∈ V. 55 / 113 Proof of Theorem 5.5. (⇐) Apply Theorem 5.3. (⇒) Let ϕ : ΩAV → S be an onto continuous homomorphism. We need to show that S is residually in V. Given distinct points s1, s2 ∈ S, since S is residually in S, there is an onto uniformly continuous homomorphism ψ : S → T such that T ∈ S and ψ(s1) = ψ(s2). Note that T is a finite continuous homomorphic image of ΩAV. If we can show that S ∈ V, we will be done. In other words, it suffices to consider the case where S is finite. Since ϕ is continuous and ΩAV is compact, ϕ is uniformly continuous. Hence, there is a positive integer n such that, for all u, v ∈ ΩAV, d(u, v) < 2−n ⇒ ϕ(u) = ϕ(v). In view of Proposition 4.6, it follows that the intersection ρ of the kernels of the uniformly continuous homomorphisms ΩAV → V with V ∈ V and |V | ≤ n is contained in ker ϕ. Hence, ϕ factors through the natural homomorphism ΩAV → ΩAV/ρ. Since ΩAV/ρ belongs to V, so does S. 56 / 113 Lemma 5.7 ([Num57, Hun88]) Let K be a clopen subset of a compact zero-dimensional metric semigroup S. Then there is a continuous homomorphism ϕ : S → T into a finite semigroup T such that K = ϕ−1 ϕ(K). Proof. We may define on S a syntactic congruence of K by u σK v if ∀ x, y ∈ S1 (xuy ∈ K ⇔ xvy ∈ K). It suffices to show that the classes of this congruence are open: then there are only finitely many of them, so that S/σK is a finite semigroup, and the natural mapping S → S/σK is a continuous homomorphism. We show that, if lim un = u, then all but finitely many terms in the sequence are σK -equivalent to u. Arguing by contradiction, otherwise, there is a subsequence consisting of terms which fail this property. We may as well assume that so does the original sequence. For each n there are xn, yn ∈ S1 such that one, but not both, of the products xnunyn and xnuyn lies in K. Again, by taking subsequences we may assume that lim xn = x, lim yn = y (in S1 ), and xnuyn /∈ K. Then xuy = lim xnunyn = lim xnuyn must belong to both K and its complement. 57 / 113 A useful application of Lemma 5.7 is the following result, which completes that of Proposition 5.4. Theorem 5.8 A compact metric semigroup is profinite if and only if it is zero-dimensional. Proof. (⇒) This follows from Proposition 5.4. (⇐) Let S be a compact metric semigroup which is zero-dimensional. We need to show that it is residually in S, that is that, for every pair s, t of distinct points of S, there is a continuous homomorphism ϕ : S → T in to a finite semigroup T such that ϕ(s) = ϕ(t). Since S is a zero-dimensional metric space, there is some clopen subset K such that s ∈ K and t /∈ K. By Lemma 5.7, there is a continuous homomorphism ϕ : S → T into a finite semigroup T such that K = ϕ−1 ϕ(K). In particular, we have ϕ(s) = ϕ(t), as required. 58 / 113 A language L ⊆ A+ is V-recognizable if its syntactic semigroup belongs to V. Theorem 5.9 A language L ⊆ A+ is V-recognizable if and only if the closure K = ι(L) is open in ΩAV and ι−1 (K) = L. The latter condition is superfluous if ι is injective and ι(A+ ) is a discrete subset of ΩAV. Proof. (⇒) Use the universal property of ΩAV (Theorem 5.3). (⇐) By Lemma 5.7, there is a continuous homomorphism ϕ : ΩAV → S such that S ∈ V and K = ϕ−1 ϕ(K). Then ψ = ϕ ◦ ι is a homomorphism A+ → S such that ψ−1 ϕ(K) = ι−1 (K) = L and so L is V-recognizable. Theorem 5.9 implies that, as a topological space, ΩAV is the Stone dual of the Boolean algebra of V-recognizable languages of A+ . 59 / 113 Theorem 5.10 A set S of V-recognizable languages over a finite alphabet A generates the Boolean algebra of all such languages if and only if the clopen sets of the form ι(L) (L ∈ S) suffice to separate points of ΩAV. Proof. (⇒) Let u, v ∈ ΩAV be distinct points. Then = d(u, v) is positive. Since ΩAV is zero-dimensional (Proposition 5.4), there is a clopen subset K containing u and contained in B (u), whence not containing v. By Theorem 5.9, L = ι−1 (K) is V-recognizable. From the hypothesis, it follows that L is a Boolean combination f (L1, . . . , Ln) of languages Li from S. By Theorem 5.9 again, each set ι(Li ) is clopen. Since ι(X1 ∪ X2) = ι(X1) ∪ ι(X2) and ΩAV \ ι(X) = ι(A+ \ X) for V-recognizable languages X, X1, X2 ⊆ A+ , we have K = ι(L) = f (ι(L1), . . . , ι(Ln)). Hence at least one of the sets ι(Li ) must contain exactly one of the points u and v. (⇐) By Theorem 5.9, it suffices to show that the clopen sets of the form ι(L), with L ⊆ A+ V-recognizable, generate the Boolean algebra of all clopen subsets of ΩAV. This is a nice exercise on compactness. 60 / 113 Outline Language recognition devices Eilenberg’s correspondence Decidable pseudovarieties Metrics associated with pseudovarieties Pro-V semigroups Reiterman’s Theorem Examples of relatively free profinite semigroups Pseudowords as operations Implicit signatures 61 / 113 Recall that a V-pseudoidentity is a formal equality u = v with u, v ∈ ΩAV for some finite set A. Recall also that, for S ∈ V, we write S |= u = v if ϕ(u) = ϕ(v) for every continuous homomorphism ϕ : ΩAV → S. In this case, we also say that u = v holds in S. For a set Σ of V-pseudoidentities, let [[Σ]] denote the class of all S ∈ V such that S |= u = v for every pseudoidentity u = v from Σ. For a subpseudovariety W of V, let pW : ΩAV → ΩAW be the natural continuous homomorphism: A ιV GG ιW 33 ΩAV pW:=ˆιW  ΩAW 62 / 113 Lemma 6.1 A pseudoidentity u = v, with u, v ∈ ΩAV, holds in every member of a subpseudovariety W of V if and only if pW(u) = pW(v). Theorem 6.2 ([Rei82]) A subclass W of V is a subpseudovariety if and only if it is of the form [[Σ]] for some set Σ of V-pseudoidentities. Usually, one takes V = S. 63 / 113 Proof of Theorem 6.2. (⇐) This amounts to verifying that the property S |= u = v is preserved under taking homomorphic images, subsemigroups and finite direct products, which follows easily from the definitions. (⇒) Fix a countably infinite set X and let Σ be the set of all pseudoidentities u = v such that u, v ∈ ΩAV for some finite subset A of X and S |= u = v for all S ∈ W. Then U = [[Σ]] is a subpseudovariety of V by the first part of the proof, and it clearly contains W. We claim that U = W. Let S ∈ U and choose an onto continuous homomorphism ϕ : ΩAU → S for some finite subset A of X (cf. Theorem 5.3). Consider the natural continuous homomorphisms pU and pW. By Lemma 6.1 and the choice of Σ, we have ker pW ⊆ ker pU and so there is a factorization pU = ψ ◦ pW for some onto continuous homomorphism ψ : ΩAW → ΩAU. Hence ϕ ◦ ψ : ΩAW → S is an onto continuous homomorphism. Corollary 5.6 then implies that S ∈ W since ΩAW is a pro-W semigroup by Theorem 5.3. ΩAV pU GG pW  ΩAU ϕ  ΩAW ψ `` S 64 / 113 To write pseudoidentities that are not identities, one needs to construct some elements of ΩAS \ A+. Lemma 6.3 Let S be a profinite semigroup, let s be an element of S, and let k ∈ Z. Then the sequence of powers (sn!+k)n≥|k| converges. For k = 0 the limit is an idempotent. Proof. Using Proposition 5.1, it suffices to consider the case where S is finite, which is left as an exercise. The limit lim sn!+k is denoted sω+k. Note that sω+ksω+ = sω+k+ . In particular, sω := sω+0 is an idempotent and sω−k and sω+k are mutual inverses in the maximal subgroup containing the idempotent sω. 65 / 113 Examples I S = [[x = x]] I = [[x = y]] G = [[xω = 1]] Gp =? A = [[xω+1 = xω ]] Com = [[xy = yx]] J = [[(xy)ω = (yx)ω , xω+1 = xω ]] R = [[(xy)ω x = (xy)ω ]] L = [[y(xy)ω = (xy)ω ]] Sl = [[xy = yx, x2 = x]] RZ = [[xy = y]] B = [[x2 = x]] N = [[xω = 0]] K = [[xω y = xω ]] D = [[yxω = xω ]] 66 / 113 Examples II Since there are uncountably many pseudovarieties of the form AbP, where P is a set of primes, and one can show that all of them admit a description of the form [[xy = yx, u = 1]] [Alm95, Corollary 3.7.8], for some u ∈ Ω{x}S, we conclude that Ω{x}S is uncountable. Let P be an infinite set of primes and let p1, p2, . . . be an enumeration of its elements, without repetitions. Let uP be an accumulation point in Ω{x}S of the sequence (xp1···pn )n. AbP = [[xy = yx, uP = 1]]. Does the sequence (xp1···pn )n converge? 67 / 113 Examples III To describe the pseudovariety Gp of all finite p-groups, we use the following result, whose proof is similar to that of Lemma 6.3. Lemma 6.4 Let S be a profinite semigroup and s ∈ S. Then the sequence (spn! )n converges. We let spω = lim spn! . Gp = [[xpω = 1]]. 68 / 113 Examples IV Exercise 6.5 (For those that know some group theory) Find, for each of the following pseudovarieties of groups, a single pseudoidentity defining them: (1) the pseudovariety Gp of all finite groups which have no elements of order p (p being a fixed prime number); (2) the pseudovariety Gnil of all finite nilpotent groups; (3) the pseudovariety Gsol of all finite solvable groups. 69 / 113 Outline Language recognition devices Eilenberg’s correspondence Decidable pseudovarieties Metrics associated with pseudovarieties Pro-V semigroups Reiterman’s Theorem Examples of relatively free profinite semigroups Pseudowords as operations Implicit signatures 70 / 113 N: finite nilpotent semigroups Recall that N = [[xω = 0]] = n≥1[[x1 · · · xn = 0]]. The proof depends on the following key result. Lemma 7.1 Let S be a finite semigroup with n elements. Then, for every choice of elements s1, . . . , sn ∈ S, there exist indices i, j such that 0 ≤ i < j ≤ n and the following equality holds for all k ≥ 1: s1 · · · sn = s1 · · · si (si+1 · · · sj )k sj+1 · · · sn. Proof. Consider the n products pr = s1 · · · sr (r = 1, . . . , n). If they are all distinct, then at least one of them, say pr , is idempotent and we may take i = 0, j = r. Otherwise, there are indices i, j such that 1 ≤ i < j ≤ n and pi = pj , in which case pi = pj = pi si+1 · · · sj = pi (si+1 · · · sj )k . 71 / 113 Let ϕ : A+ → S be a homomorphism into a semigroup S ∈ N, say satisfying x1 · · · xn = 0. Then, all words of length at least n belong to ϕ−1 (0) and for s ∈ S \ {0}, the words in the language L = ϕ−1 (s) have length less than n, and so L is a finite set. Thus, every N-recognizable language is either finite or cofinite. To show that these are precisely the N-recognizable languages, it suffices to show that every singleton language {w} ⊆ A+ is N-recognizable. Let n = |w| be the length of the word w. Consider the semigroup S consisting of the words of A+ of length at most n together with a zero element 0. The product of two words is the word resulting from their concatenation if that word has length at most n and is 0 otherwise.1 Then S satisfies the identity x1 · · · xn = 0, for the natural homomorphism ϕ : A+ → S, that sends each letter to itself, we have ϕ−1 (w) = {w}. 1 This amounts to“killing”the ideal of the semigroup A+ consisting of the words of length greater than n, identifying all the elements in the ideal to a zero. In semigroup theory, such a construction is called a Rees quotient. 72 / 113 Proposition 7.2 A language over a finite alphabet A is N-recognizable if and only if it is finite or its complement in A+ is finite. In view of Theorem 5.9, we deduce the following result: Proposition 7.3 Let V be a pseudovariety of semigroups containing N. Then the completion homomorphism ι : A+ → ΩAV is injective and A+ is a discrete subspace of ΩAV. In particular, a language L ⊆ A+ is V-recognizable if and only if its closure L in ΩAV is a clopen subset. 73 / 113 Proof. The injectivity of ι amounts to V satisfying no identity u = v with u, v ∈ A+ distinct words. Indeed, Synt({u}) is nilpotent, whence it belongs to V. Since 1u1 ∈ {u} while 1v1 /∈ {u}, we deduce that u and v are not σ{u}-equivalent and so Synt({u}) |= u = v. We may therefore identify each w ∈ A+ with ι(w) ∈ ΩAV. For w ∈ A+, we have {w} = {w}, because ΩAV is a metric space. Since {w} is V-recognizable, its closure {w} is an open subset of ΩAV by Theorem 5.9. Hence A+ is a discrete subset of ΩAV. 74 / 113 Proposition 7.4 The semigroup ΩAN is obtained by adding to A+ a zero element. The open sets containing zero consist of zero together with a cofinite subset of A+.2 Proof. It suffices to observe that a non-eventually constant sequence (wn)n of words of A+ is a Cauchy sequence with respect to the metric dN if and only if lim |wn| = ∞. In the affirmative case, for every homomorphism ϕ : A+ → S into S ∈ N, we have lim ϕ(wn) = 0. Thus, all non-eventually constant Cauchy sequences converge to the same point ot ΩAN, which is a zero. The open subsets of ΩAN containing 0 have complement which is a closed, whence compact, subset of A+. Since A+ is a discrete subset of ΩAN, that complement must be finite. The converse is clear. 2 This is known as the Alexandroff or one-point compactification, which in general is obtained by adding one point and declaring the open sets containing it to consist also of the complement of a compact subset of the original space. 75 / 113 K: finite semigroups satisfying es = e Recall that K = [[xω y = xω ]]. Note that K = n≥1 Kn where Kn = [[x1 · · · xny = x1 · · · xn]]. Let AN denote the set of all right infinite words over A, i.e., sequences of letters. Endow the set S = A+ ∪ AN with the operation u · v = uv if u ∈ A+ u otherwise and the function d : S × S → R≥0 defined by d(u, v) = 2−r(u,v) , where r(u, v) is the length of the longest common prefix of u and v. 76 / 113 Proposition 7.5 The set S is a pro-K semigroup for the above operation and distance function d. The unique continuous homomorphism ΩAK → S that sends each letter a ∈ A to itself is an isomorphism. Proof. It is easy to check that the multiplication defined on S is associative and that d is an totally bounded complete ultrametric. Consider the set Sn consisting of all words of A+ of length at most n, endowed with the operation u · v = uv if |uv| ≤ n in(u) otherwise where in(w) denotes the longest prefix of length at most n of the word w. This operation is associative and Sn ∈ Kn. Moreover, every n-generated semigroup from Kn is a homomorphic image of Sn. Hence Sn ΩAKn. Note also that the mapping ϕn : S → Sn which sends each w ∈ S to in(w) is a continuous homomorphism. Hence, given two distinct points u and v from S, for n = r(u, v) + 1, the mapping ϕn is a continuous homomorphism into a semigroup from K which distinguishes u from v. Thus, S is a pro-K semigroup. 77 / 113 (. . . ) Consider next the unique continuous homomorphism ψ : ΩAK → S which maps each letter a ∈ A to itself. Since K = n≥1 Kn, given distinct u, v ∈ ΩAK, there exists a continuous homomorphism θ : ΩAK → Sn such that θ(u) = θ(v). ΩAK ψ GG θ  S ϕn  Sn ΩAKn µ oo The fact that the above diagram can always be completed by a homomorphism µ shows that ψ(u) = ψ(v). Hence ψ is injective. 78 / 113 Outline Language recognition devices Eilenberg’s correspondence Decidable pseudovarieties Metrics associated with pseudovarieties Pro-V semigroups Reiterman’s Theorem Examples of relatively free profinite semigroups Pseudowords as operations Implicit signatures 79 / 113 Implicit operations Let n be a positive integer. An n-ary implicit operation on pro-V semigroups is a correspondence π associating to each pro-V semigroup S an n-ary operation πS : Sn → S such that , for every continuous homomorphism ϕ : S → T between pro-V semigroups, the following diagam commutes: Sn πS GG ϕn  S ϕ  Tn πT GG T, i.e., ϕ πS (s1, . . . , sn) = πT ϕ(s1), . . . , ϕ(sn) for all s1, . . . , s2 ∈ S. Examples: the binary multiplication (s1, s2) → s1s2 and the component projections (s1, . . . , sn) → si are implicit operations. Composing implicit operations we also obtain implicit operations. 80 / 113 If A and B are finite sets with the same cardinality n, then ΩAV ΩBV. We denote by ΩnV any of them. Usually, we identify ΩnV with ΩXn V, where Xn = {x1, . . . , xn} has cardinality n. To each w ∈ ΩnV, we may associate an n-ary implicit operation πw on pro-V semigroups as follows: for a pro-V semigroup S, given s1, . . . , sn ∈ S, let f : Xn → S be the function defined by f (xi ) = si (i = 1, . . . , n); let (πw )S (s1, . . . , sn) = ˆf (w) where ˆf completes the following diagram: Xn ι GG f 33 ΩnV ˆf  S. 81 / 113 Proposition 8.1 1. For each w ∈ ΩnV, πw is indeed an n-ary implicit operation on pro-V semigroups. 2. The correspondence w ∈ ΩnV → πw is injective and in fact πw is completely characterized by the operations (πw )S with S ∈ V. 82 / 113 Proof. 1. Let ϕ : S → T be a continuous homomorphism between two pro-V semigroups and let s1, . . . , sn be elements of S. Let f : Xn → S be defined by f (xi ) = si (i = 1, . . . , n). Then we have the following commutative diagram: Xn f  ϕ◦f ι  ΩnV ˆf }} ϕ◦f 33 S ϕ GG T which shows that ϕ (πw )S (f (s1), . . . , f (sn)) = ϕ ˆf (w) = ϕ ◦ f (w) = (πw )T ϕ(f (s1)), . . . , ϕ(f (sn)) . 83 / 113 (. . . ) 2. Let u, v ∈ ΩnV be two distinct elements. Then there exists a continuous homomorphism ϕ : ΩnV → S into a semigroup S ∈ V such that ϕ(u) = ϕ(v). Let si = ϕ(xi ) (i = 1, . . . , n). For w ∈ ΩnV, by definition of πw we have (πw )S (s1, . . . , sn) = ϕ(w). Since ϕ(u) = ϕ(v), we deduce that (πu)S (s1, . . . , sn) = (πv )S (s1, . . . , sn) and so, certainly πu = πv . We identify w with πw . Note that S ∈ V satisfies the V-pseudoidentity u = v if and only if uS = vS . We say that a pro-V semigroup S satisfies the V-pseudoidentity u = v if uS = vS . 84 / 113 Outline Language recognition devices Eilenberg’s correspondence Decidable pseudovarieties Metrics associated with pseudovarieties Pro-V semigroups Reiterman’s Theorem Examples of relatively free profinite semigroups Pseudowords as operations Implicit signatures 85 / 113 By an implicit signature we mean a set σ of implicit operations (on S) which includes the binary operation of multiplication. Example: κ = { · , ω−1}. Given an implicit signature σ, each profinite semigroup S becomes a natural σ-algebra in which each operation w ∈ σ is interpreted as wS . In particular, each ΩAV becomes a σ-algebra. The σ-subalgebra generated by ι(A) is denoted Ωσ AV. For the minimum implicit signature σ, consisting only of multiplication, we denote Ωσ AV simply by ΩAV.3 A formal term constructed from the letters a ∈ A using the operations from the implicit signature σ is called a σ-term over A. Such σ-term w determines an element wV of Ωσ AV by evaluating the operations within Ωσ AV. 3 The bar in the notation ΩAV comes from the fact ΩAV = ι(A+ ) is dense in ΩAV. This notation (without reference to V) was introduced by Reiterman [Rei82]. 86 / 113 The following result is an immediate consequence of Theorem 5.3. Proposition 9.1 The σ-algebra Ωσ AV is a V-free σ-algebra freely generated by A in the sense of the following universal property: for every mapping ϕ : A → S into a semigroup S ∈ V, there is a unique homomorphism ˆϕ of σ-algebras such that the following diagram commutes: A ι GG ϕ 33 Ωσ AV ˆϕ  S. 87 / 113 Examples: Ωκ AN = ΩAN; for |A| ≥ 2, since ΩAK is uncountable, we have Ωσ AK ΩAK for every countable implicit signature σ; Ωκ AJ = ΩAJ [Alm95, Section 8.1]; Ωκ AG is the free group freely generated by ι(A) = A; Ωκ ACR is the free completely regular (union of groups) semigroup freely generated by ι(A) = A. 88 / 113 A key problem for the applications is to be able to solve the word problem in the free σ-algebra Ωσ AV: to find an algorithm, if one exists, that given two σ-terms over A, determines whether uV = vV. If such algorithm exists, then we say that the word problem is decidable; otherwise, we say that it is undecidable. 89 / 113 Examples: The word problem for Ωκ AN: two κ-terms coincide in Ωσ AN if and only if they are equal or they both involve the operation ω−1 . The word problem for Ωκ AG is well known: the operation ω−1 is inversion in profinite groups, so all κ-terms can be effectively reduced (over G) to κ-terms in which that operation is only applied to letters; then use, in any order, the reduction rules aaω−1 → 1 and aω−1 a → 1 (a ∈ A) to obtain a canonical form for κ-terms over G; two κ-terms are equal over G if and only if they have the same canonical form. Word problem for ΩAK: exercise. The solution of the word problem for Ωκ AJ = ΩAJ gives the structure of ΩAJ [Alm95, Section 8.1]. The word problem for Ωκ ACR has been solved by Kad’ourek and Pol´ak [KP86]. The word problem for Ωκ AA has been solved by McCammond [McC01]. 90 / 113 Part II Separating words and regular languages 91 / 113 Outline σ-fullness pro-V-metrics 92 / 113 A separation problem Let V be a pseudovariety of semigroups. Suppose that a regular language L ⊆ A+ and a word w ∈ A+ are given. How do we find out whether a proof that w /∈ L exists using V-recognizable languages? More precisely, we wish to decide whether, given such L and w, there exists a V-recognizable language K ⊆ A+ such that L ⊆ K and w /∈ K. For instance, how do we determine whether there exists a finite permutation automaton such that no word from L ends in the same state as w does? Another example of the same type of problem: is there some integer n such that no word from L has the same subwords of length at most n as w does? 93 / 113 Our problem sounds like a topological separation problem, and indeed it admits such a formulation in the profinite world. Proposition 10.1 Let V be a pseudovariety of semigroups, L ⊆ A+ a regular language and w a word in A+. Then there is a V-recognizable language K ⊆ A+ such that L ⊆ K and w /∈ K if and only if ιV(w) does not belong to the closure of ιV(L) in ΩAV. Proof. By Proposition 5.4, the condition ιV(w) belongs to the closure ιV(L) in ΩAV holds if and only if every clopen subset of ΩAV which contains ιV(w) has nontrivial intersection with ιV(L). By Theorem 5.9, such clopen subsets are precisely the sets of the form ιV(K) where K is a V-recognizable subset of A+ . It remains to observe that, ιV(w) ∈ ιV(K) and ιV(K) ∩ ιV(L) = ∅ if and only if w ∈ K and K ∩ L = ∅, which follows from the facts that K = ι−1 V (ιV(K)) and L ⊆ ι−1 V (ιV(L)). 94 / 113 Note that, while ΩAV is in general uncountable, by Theorem 5.9 it has only countably many clopen subsets, since there are only that many V-recognizable subsets of A+ (for instance since they are all recognized by finite automata). An idea due to Pin and Reutenauer [PR91] in the case of the pseudovariety G of all finite groups is to somehow“compute” the closure of ιV(L) not in ΩAG but in the free group Ωκ AG, or even in A+. Under the assumption of a conjectured property for the pseudovariety G, they produced an algorithm for computing the required closure, which solves our problem for G. We proceed to introduce the required property in general, returning later to their algorithm. 95 / 113 σ-fullness For a subset L of A+, denote by clσ,V(L) and clV(L) respectively the closure of ιV(L) in Ωσ AV and in ΩAV. Note that clσ,V(L) = clV(L) ∩ Ωσ AV. Denote by pV the natural continuous homomorphism ΩAS → ΩAV. Since ΩAS is compact and pV is a onto continuous mapping, we always have the equality clV(L) = pV(clS(L)). In general, for a continuous function f : S → T, and a subset X of S, we have f (X) ⊆ f (X). The reverse inclusion also holds if f is onto and S is compact. We say that the pseudovariety V is σ-full if, for every regular language L ⊆ A+, the following equality holds: clσ,V(L) = pV(clσ,S(L)). In other words, membership of w ∈ Ωσ AV in clσ,V(L) is witnessed by some w ∈ clσ,S(L) such that pV(w ) = w. 96 / 113 Examples: The pseudovariety N is κ-full: for a regular language L ⊆ A+ and a κ-term w, wN ∈ clκ,N(L) if and only if w is a word from L or w involves the operation ω−1 and L is infinite; in the latter case, by compactness there is some κ-term v such that vS ∈ clκ,S(L) \ A+ and so wN = 0 = pN(vS). That the pseudovariety J is κ-full follows from the structure theorem for ΩAJ. The pseudovariety G is κ-full: the essential ingredient is a seminal theorem of Ash [Ash91]; the details follow from [AS00] and [Del01]. The pseudovariety Ab is κ-full [Del01]. 97 / 113 The pseudovariety Gp is not κ-full: this follows from a weak version of Ash’s theorem proved by Steinberg [Ste01] for Gp together with fact that the conjunction of this weaker property with κ-fullness implies that the pseudovariety is defined by pseudoidentities in which both sides are given by κ-terms [AS00]; however, such a definition does not exist since, by a theorem of Baumslag [Bau65], the free group is residually a finite p-group. That the pseudovarieties A and R are κ-full has been proved by JA-JCCosta-MZeitoun using the solution of the word problems for Ωκ AA [McC01]4 and Ωκ AR [AZ07]. 4 plus refinements from an alternative proof obtained by the same authors including the fact that Ωκ AA is closed for taking factors in ΩAA. 98 / 113 Outline σ-fullness pro-V-metrics 99 / 113 pro-V metrics The same way we defined a pseudo-ultrametric on the free semigroup A+ associated with a pseudovariety V, we may define a pseudo-ultrametric on an arbitrary semigroup S: let d(s1, s2) = 2−r(s1,s2) , where r(s1, s2) is the smallest cardinality of a semigroup T ∈ V for which there is a homomorphism ϕ : S → T such that ϕ(s1) = ϕ(s2). Similar arguments show that d is indeed a pseudo-ultrametric on S, with respect to which the multiplication in S is uniformly continuous. If S is finitely generated, then the completion ˆS is again a pro-V semigroup, but it may not be a free pro-V semigroup. The pseudo-ultrametric d is an ultrametric if and only if S is residually in V. Every homomorphism S → T into T ∈ V is uniformly continuous. 100 / 113 Pro-H metric on groups Traditionally, one denotes by H an arbitrary pseudovariety of groups. Because a group is highly symmetrical, the pro-H metric structure looks similar everywhere. Lemma 11.1 Let G be a group and consider the pro-H metric on G. Then, for every u, v, w ∈ G, the equalities d(uw, vw) = d(u, v) = d(wu, wv) hold. In particular, for > 0, we have Bε(u) = uBε(1) = Bε(1)u and a subset X is open (respectively closed) if and only if so is Xw. Moreover, for > 0, the ball B (1) is a clopen normal subgroup of G such that G/B (1) ∈ H. A subgroup H is open if and only if it contains some open ball B (1). Proof. This is a simple exercise. 101 / 113 For a subgroup H of a group G, denote by HG the largest normal subgroup of G which is contained in H. It is given by the formula HG = g∈G g−1 Hg. If we let G act on the set of right cosets of H in G by right translation, then we obtain a homomorphism ϕ : G → SG/H into the full symmetric group SG/H (of all permutations of the set G/H) such that ϕ−1(id) = HG . It follows that, if the index (G : H) of the subgroup H in G is finite, then so is (G : HG ) and (G : HG ) is a divisor of (G : H)!. 102 / 113 Lemma 11.2 A subgroup H of G is (cl)open in the pro-H metric if and only if G/HG ∈ H. Proof. Suppose first that H is open. By Lemma 11.1, H contains a normal subgroup K of G such that G/K ∈ H. Then K ⊆ HG and so G/HG (G/K)/(HG /K) belongs to H. Conversely, if G/HG ∈ H then HG is an open set, because the natural homomorphism G → G/HG is (uniformly) continuous. Since H contains HG , H is a union of cosets of HG , and so is its complement. Hence H is clopen. 103 / 113 Another natural question is whether, for a subgroup H of G, the intersection with H of an open subset of G in the pro-H metric of G is also open in the pro-H metric of H. In general, the answer is negative, but there are important situations in which it is affirmative. Example 11.3 Let G be the free group on two free generators a, b and consider the homomorphism ϕ : G → S3 defined by ϕ(a) = (12) and ϕ(b) = (13). Let K = ϕ−1(1) and let H = ϕ−1 (123) be the inverse image of the subgroup of index 2. Then H is clopen in the pro-Ab metric of G and K is clopen in the pro-Ab metric of H but K is not clopen in the pro-Ab metric of G. 104 / 113 Note that, for pseudovarieties of groups K and H, K ∗ H consists of all groups G which have a normal subgroup K such that both K ∈ K and G/K ∈ H.5 If H ∗ H = H, then we say that H is closed under extension. A condition for the answer to the above question to be affirmative is drawn from the following result. Lemma 11.4 Let H be a clopen subgroup of G in the pro-H metric of G and suppose that U is a normal subgroup of H such that H/U ∈ H. Then the normal subgroup UG of G is such that G/UG ∈ H ∗ H. 5 For those unfamiliar with semidirect products, take this as the definition of K ∗ H and show that it is a pseudovariety of groups. 105 / 113 Proof. Consider also the normal subgroup HG and let g ∈ G. By Lemma 11.2, G/HG belongs to H. For each x ∈ HG , the conjugate gxg−1 belongs to H and so the mapping ϕg : HG → H/U which sends x to gxg−1U is a group homomorphism. Moreover, for x ∈ HG , we have x ∈ UG ⇔ x ∈ g−1 Ug for all g ∈ G ⇔ gxg−1 ∈ U for all g ∈ G ⇔ ϕg (x) = 1 for all g ∈ G. It follows that HG /UG embeds in a finite power of H/U and so HG /UG ∈ H. The result now follows from the observation that G/HG (G/UG )/(HG /UG ). 106 / 113 A first application of the preceding lemma is the following answer to the above question. Proposition 11.5 Suppose that H is closed under extension. Let H be a clopen subgroup of G in the pro-H metric of G. Then a subset of H is open in the pro-H metric of H if and only if it is open in the pro-H metric of G. Proof. By Lemma 11.1, a subgroup L of H is open in the pro-H metric of H if and only if it contains a normal subgroup U of H such that H/U ∈ H. By Lemma 11.4, the normal subgroup UG of G is such that U/UG ∈ H ∗ H = H. Hence U is open in the pro-H metric of G by Lemma 11.2. Since L is a union of cosets of U, L is also open in the pro-H metric of G. 107 / 113 In terms of the pro-H metrics, we obtain the following more precise result. Proposition 11.6 Suppose that H is closed under extension and G is a group residually in H. Let H be a clopen subgroup of G in the pro-H metric of G. Then the pro-H metric dH of H and the restriction to H of the pro-H metric dG of G have the same Cauchy sequences. 108 / 113 Proof. Let d be the restriction of dG to H and let r be the corresponding partial function H × H → N. Denote by d the pseudo-metric dH and by r the corresponding partial function. We start by establishing the following function inequalities: r ≤ r ≤ (G : H) · r !. (1) The first inequality in (1) follows from the observation that, if a homomorphism from G into a member of H distinguishes two elements of H then its restriction to H also distinguishes them. Suppose next that u, v ∈ H and the homomorphism ϕ : H → K with K ∈ H are such that ϕ(u) = ϕ(v). Let U = ϕ−1 (1). Then H/U embeds in K and, therefore, it belongs to H. By Lemma 11.4, UG is a normal subgroup of G of finite index such that G/UG ∈ H ∗ H = H and, by an earlier observation, (G : UG ) divides (G : U)!. If we choose above K so that |K| is minimum, then (H : U) = r (u, v) and so, since uUG = vUG , r(u, v) ≤ (G : UG ) ≤ (G : U)! = (G : H) · (H : U) ! = (G : H) · r (u, v) ! which proves (1). 109 / 113 . . . From the first inequality in (1) we deduce that every Cauchy sequence with respect to d is also a Cauchy sequence with respect to d. For the converse, let f (n) = (G : H) · n !. Then f is an increasing sequence and a simple calculation shows that, for every ε > 0, d ≤ 2−f ( − log2 ε ) =⇒ d ≤ ε. This implies that Cauchy sequences for d are also Cauchy sequences for d . 110 / 113 Free products A free product in a variety V of semigroups is given by two homomorphisms ϕi : Si → F (i = 1, 2), with S1, S2, F ∈ V such that, given any other pair of homomorphisms ψi : Si → T, with T ∈ V, there exists a unique homomorphism θ : F → T such that the following diagram commutes: F θ 22 S1 ϕ1 oo ψ1  S2 ϕ2 yy ψ2 GG T By the usual argument, if the free product exists, then it is unique up to isomorphism. 111 / 113 Exercise 11.7 Show that, for every variety V and semigroups S1, S2 ∈ V, the free product of S1 and S2 in V exists. For semigroups S and T in a variety V, we say that S is a free factor of T if there exists U ∈ V such that T is a free product of S and U in V. Note that every semigroup is a free factor of itself. Exercise 11.8 Suppose that S is a free factor of T in the variety V generated by a pseudovariety V. Show that: 1. the pseudo-metric dS V and the restriction of the pseudo-metric dT V to S coincide; 2. the open sets in pro-V metric of S are the intersection with S of the open sets of T in the pro-V metric of T. 112 / 113 Section 12 References 113 / 113 [ABR92] D. Albert, R. Baldinger, and J. Rhodes, The identity problem for finite semigroups (the undecidability of), J. Symbolic Logic 57 (1992), 179–192. [AE03] J. Almeida and A. Escada, Semidirect products with the pseudovariety of all finite groups, Proceedings of the International Conference Words, Languages and Combinatorics (Kyoto, March, 2000) (Singapore) (M. Ito and T. Imaoka, eds.), World Scientific, 2003, pp. 1–21. [Alm95] J. Almeida, Finite semigroups and universal algebra, World Scientific, Singapore, 1995, English translation. [AS00] J. Almeida and B. Steinberg, On the decidability of iterated semidirect products and applications to complexity, Proc. London Math. Soc. 80 (2000), 50–74. [AS03] K. Auinger and B. Steinberg, On the extension problem for partial permutations, Proc. Amer. Math. Soc. 131 (2003), 2693–2703. [Ash87] C. J. Ash, Finite semigroups with commuting idempotents, J. Austral. Math. Soc., Ser. A 43 (1987), 81–90. 113 / 113 [Ash91] , Inevitable graphs: a proof of the type II conjecture and some related decision procedures, Int. J. Algebra Comput. 1 (1991), 127–146. [AZ07] J. Almeida and M. Zeitoun, An automata-theoretic approach of the word problem for ω-terms over R, Theor. Comp. Sci. 370 (2007), 131–169. [Bau65] G. Baumslag, Residual nilpotence and relations in free groups, J. Algebra 2 (1965), 271–282. [BS73] J. A. Brzozowski and I. Simon, Characterizations of locally testable events, Discrete Math. 4 (1973), 243–271. [Del01] M. Delgado, On the hyperdecidability of pseudovarieties of groups, Int. J. Algebra Comput. 11 (2001), 753–771. [Eil76] S. Eilenberg, Automata, languages and machines, vol. B, Academic Press, New York, 1976. [HMPR91] K. Henckell, S. Margolis, J.-E. Pin, and J. Rhodes, Ash’s type II theorem, profinite topology and Malcev products. Part I, Int. J. Algebra Comput. 1 (1991), 411–436. 113 / 113 [HR91] K. Henckell and J. Rhodes, The theorem of Knast, the PG=BG and Type II Conjectures, Monoids and Semigroups with Applications (Singapore) (J. Rhodes, ed.), World Scientific, 1991, pp. 453–463. [Hun88] R. P. Hunter, Certain finitely generated compact zero-dimensional semigroups, J. Austral. Math. Soc., Ser. A 44 (1988), 265–270. [KP86] Jiˇri Kad’ourek and Libor Pol´ak, On the word problem for free completely regular semigroups, Semigroup Forum 34 (1986), 127–138. [KR65] K. Krohn and J. Rhodes, Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines, Trans. Amer. Math. Soc. 116 (1965), 450–464. [McC01] J. McCammond, Normal forms for free aperiodic semigroups, Int. J. Algebra Comput. 11 (2001), 581–625. [MP71] R. McNaughton and S. Papert, Counter-free automata, MIT Press, Cambridge, MA, 1971. [MP84] S. W. Margolis and J.-E. Pin, Varieties of finite monoids and topology for the free monoid, Proc. 1984 Marquette Semigroup Conference (Milwaukee), Marquette University, 1984, pp. 113–129. 113 / 113 [MP87] , Inverse semigroups and varieties of finite semigroups, J. Algebra 110 (1987), 306–323. [Num57] K. Numakura, Theorems on compact totally disconnetced semigroups and lattices, Proc. Amer. Math. Soc. 8 (1957), 623–626. [Pin95] J.-E. Pin, BG=PG: A success story, Semigroups, Formal Languages and Groups (Dordrecht) (J. Fountain, ed.), vol. 466, Kluwer, 1995, pp. 33–47. [PR91] J.-E. Pin and C. Reutenauer, A conjecture on the Hall topology for the free group, Bull. London Math. Soc. 23 (1991), 356–362. [PS85] J.-E. Pin and H. Straubing, Monoids of upper triangular matrices, Semigroups: structure and universal algebraic problems (Amsterdam) (G. Poll´ak, ed.), North-Holland, 1985, pp. 259–272. [Rei82] J. Reiterman, The Birkhoff theorem for finite algebras, Algebra Universalis 14 (1982), 1–10. [Sch65] M. P. Sch¨utzenberger, On finite monoids having only trivial subgroups, Inform. and Control 8 (1965), 190–194. [Sim75] I. Simon, Piecewise testable events, Proc. 2nd GI Conf. (Berlin), Lect. Notes in Comput. Sci., vol. 33, Springer, 1975, pp. 214–222. 113 / 113 [Ste01] B. Steinberg, Inevitable graphs and profinite topologies: some solutions to algorithmic problems in monoid and automata theory, stemming from group theory, Int. J. Algebra Comput. 11 (2001), 25–71. [Sti73] P. Stiffler, Extension of the fundamental theorem of finite semigroups, Advances in Math. 11 (1973), 159–209. 113 / 113