Representations of relatively free profinite semigroups, irreducibility, and order primitivity

Almeida, Jorge; Klíma, Ondřej

doi:10.1090/tran/7951

Representations of relatively free profinite semigroups, irreducibility, and order primitivity
HTML articles powered by AMS MathViewer

by Jorge Almeida and Ondřej Klíma PDF

Trans. Amer. Math. Soc. 373 (2020), 1941-1981 Request permission

Abstract:

We establish that, under certain closure assumptions on a pseudovariety of semigroups, the corresponding relatively free profinite semigroups freely generated by a nonsingleton finite set act faithfully on their minimum ideals. As applications, we enlarge the scope of several previous join irreducibility results for pseudovarieties of semigroups, which turn out to be even join irreducible in the lattice of pseudovarieties of ordered semigroups, so that, in particular, they are not generated by proper subpseudovarieties of ordered semigroups. We also prove the stronger form of join irreducibility for the Krohn-Rhodes complexity pseudovarieties, thereby solving a problem proposed by Rhodes and Steinberg.

References

Douglas Albert, Robert Baldinger, and John Rhodes, Undecidability of the identity problem for finite semigroups, J. Symbolic Logic 57 (1992), no. 1, 179–192. MR 1150933, DOI 10.2307/2275184
Jorge Almeida, On finite simple semigroups, Proc. Edinburgh Math. Soc. (2) 34 (1991), no. 2, 205–215. MR 1115641, DOI 10.1017/S0013091500007112
Jorge Almeida, Finite semigroups and universal algebra, Series in Algebra, vol. 3, World Scientific Publishing Co., Inc., River Edge, NJ, 1994. Translated from the 1992 Portuguese original and revised by the author. MR 1331143
Jorge Almeida, A syntactical proof of locality of DA, Internat. J. Algebra Comput. 6 (1996), no. 2, 165–177. MR 1386073, DOI 10.1142/S021819679600009X
J. Almeida and A. Costa, Handbook of AutoMathA, ch. Profinite topologies, European Math. Soc. Publ. House, To appear.
Jorge Almeida and Alfredo Costa, Infinite-vertex free profinite semigroupoids and symbolic dynamics, J. Pure Appl. Algebra 213 (2009), no. 5, 605–631. MR 2494356, DOI 10.1016/j.jpaa.2008.08.009
Jorge Almeida and Alfredo Costa, A note on pseudovarieties of completely regular semigroups, Bull. Aust. Math. Soc. 92 (2015), no. 2, 233–237. MR 3392250, DOI 10.1017/S0004972715000532
J. Almeida and O. Klíma, On the irreducibility of pseudovarieties of semigroups, J. Pure Appl. Algebra 220 (2016), no. 4, 1517–1524. MR 3423461, DOI 10.1016/j.jpaa.2015.09.015
Jorge Almeida and Ondřej Klíma, Pseudovarieties of ordered completely regular semigroups, Results Math. 74 (2019), no. 2, Paper No. 78, 28. MR 3923509, DOI 10.1007/s00025-019-0998-7
Jorge Almeida and Peter G. Trotter, Hyperdecidability of pseudovarieties of orthogroups, Glasg. Math. J. 43 (2001), no. 1, 67–83. MR 1825723
Jorge Almeida and Peter G. Trotter, The pseudoidentity problem and reducibility for completely regular semigroups, Bull. Austral. Math. Soc. 63 (2001), no. 3, 407–433. MR 1834943, DOI 10.1017/S000497270001950X
J. Almeida and M. V. Volkov, Subword complexity of profinite words and subgroups of free profinite semigroups, Internat. J. Algebra Comput. 16 (2006), no. 2, 221–258. MR 2228511, DOI 10.1142/S0218196706002883
K. Auinger and B. Steinberg, On the extension problem for partial permutations, Proc. Amer. Math. Soc. 131 (2003), no. 9, 2693–2703. MR 1974324, DOI 10.1090/S0002-9939-03-06860-6
Jean-Camille Birget, Iteration of expansions—unambiguous semigroups, J. Pure Appl. Algebra 34 (1984), no. 1, 1–55. MR 766154, DOI 10.1016/0022-4049(84)90055-0
Jean-Camille Birget and John Rhodes, Almost finite expansions of arbitrary semigroups, J. Pure Appl. Algebra 32 (1984), no. 3, 239–287. MR 745358, DOI 10.1016/0022-4049(84)90092-6
J. H. Carruth, J. A. Hildebrant, and R. J. Koch, The theory of topological semigroups. Vol. 2, Monographs and Textbooks in Pure and Applied Mathematics, vol. 100, Marcel Dekker, Inc., New York, 1986. MR 827714
Laura Chaubard, Jean-Éric Pin, and Howard Straubing, Actions, wreath products of $\scr C$-varieties and concatenation product, Theoret. Comput. Sci. 356 (2006), no. 1-2, 73–89. MR 2217828, DOI 10.1016/j.tcs.2006.01.039
Volker Diekert, Manfred Kufleitner, and Pascal Weil, Star-free languages are Church-Rosser congruential, Theoret. Comput. Sci. 454 (2012), 129–135. MR 2966629, DOI 10.1016/j.tcs.2012.01.028
Samuel Eilenberg, Automata, languages, and machines. Vol. B, Pure and Applied Mathematics, Vol. 59, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1976. With two chapters (“Depth decomposition theorem” and “Complexity of semigroups and morphisms”) by Bret Tilson. MR 0530383
Stephen J. Emery, Varieties and pseudovarieties of ordered normal bands, Semigroup Forum 58 (1999), no. 3, 348–366. MR 1678504, DOI 10.1007/BF03325434
Ryszard Engelking, General topology, 2nd ed., Sigma Series in Pure Mathematics, vol. 6, Heldermann Verlag, Berlin, 1989. Translated from the Polish by the author. MR 1039321
Karsten Henckell, Stuart W. Margolis, Jean-Eric Pin, and John Rhodes, Ash’s type $\textrm {II}$ theorem, profinite topology and Mal′cev products. I, Internat. J. Algebra Comput. 1 (1991), no. 4, 411–436. MR 1154442, DOI 10.1142/S0218196791000298
J. A. Hildebrant, J. D. Lawson, and D. P. Yeager, The translational hull of a topological semigroup, Trans. Amer. Math. Soc. 221 (1976), no. 2, 251–280. MR 409712, DOI 10.1090/S0002-9947-1976-0409712-8
Jiří Kaďourek and Libor Polák, On the word problem for free completely regular semigroups, Semigroup Forum 34 (1986), no. 2, 127–138. MR 868250, DOI 10.1007/BF02573158
K. Krohn, J. Rhodes, and B. Tilson, Lectures on the algebraic theory of finite semigroups and finite-state machines, Algebraic Theory of Machines, Languages, and Semigroups (New York) (M. A. Arbib, ed.), Academic Press, 1968, Chapter 6 with M. A. Arbib.
Martin Kuřil, On varieties of ordered semigroups, Semigroup Forum 90 (2015), no. 2, 475–490. MR 3318276, DOI 10.1007/s00233-014-9630-z
S. Margolis, M. Sapir, and P. Weil, Irreducibility of certain pseudovarieties, Comm. Algebra 26 (1998), no. 3, 779–792 (English, with English and French summaries). MR 1606233, DOI 10.1080/00927879808826163
J. D. McKnight Jr. and A. J. Storey, Equidivisible semigroups, J. Algebra 12 (1969), 24–48. MR 238982, DOI 10.1016/0021-8693(69)90015-5
V. Molchanov, Nonstandard characterization of pseudovarieties, Algebra Universalis 33 (1995), no. 4, 533–547. MR 1331916, DOI 10.1007/BF01225473
Katsumi Numakura, Theorems on compact totally disconnected semigroups and lattices, Proc. Amer. Math. Soc. 8 (1957), 623–626. MR 87032, DOI 10.1090/S0002-9939-1957-0087032-5
Jean-Eric Pin, Propriétés syntactiques du produit non ambigu, Automata, languages and programming (Proc. Seventh Internat. Colloq., Noordwijkerhout, 1980) Lecture Notes in Comput. Sci., vol. 85, Springer, Berlin-New York, 1980, pp. 483–499 (French). MR 589026
J.-E. Pin, Varieties of formal languages, Foundations of Computer Science, Plenum Publishing Corp., New York, 1986. With a preface by M.-P. Schützenberger; Translated from the French by A. Howie. MR 912694, DOI 10.1007/978-1-4613-2215-3
Zhan-Erik Pèn, Eilenberg’s theorem for positive varieties of languages, Izv. Vyssh. Uchebn. Zaved. Mat. 1 (1995), 80–90 (Russian); English transl., Russian Math. (Iz. VUZ) 39 (1995), no. 1, 74–83. MR 1391325
J.-E. Pin and P. Weil, Profinite semigroups, Mal′cev products, and identities, J. Algebra 182 (1996), no. 3, 604–626 (English, with English and French summaries). MR 1398113, DOI 10.1006/jabr.1996.0192
J.-E. Pin and P. Weil, A Reiterman theorem for pseudovarieties of finite first-order structures, Algebra Universalis 35 (1996), no. 4, 577–595 (English, with English and French summaries). MR 1392285, DOI 10.1007/BF01243597
J.-E. Pin and P. Weil, Polynomial closure and unambiguous product, Theory Comput. Syst. 30 (1997), no. 4, 383–422. MR 1450862, DOI 10.1007/s002240000058
Norman R. Reilly, The Rhodes expansion and free objects in varieties of completely regular semigroups, J. Pure Appl. Algebra 69 (1990), no. 1, 89–109. MR 1082447, DOI 10.1016/0022-4049(90)90080-2
Jan Reiterman, The Birkhoff theorem for finite algebras, Algebra Universalis 14 (1982), no. 1, 1–10. MR 634411, DOI 10.1007/BF02483902
John Rhodes, Infinite iteration of matrix semigroups. II. Structure theorem for arbitrary semigroups up to aperiodic morphism, J. Algebra 100 (1986), no. 1, 25–137. With an appendix by Jerrold R. Goodwin. MR 839575, DOI 10.1016/0021-8693(86)90070-0
J. Rhodes and D. Allen, Jr., Synthesis of the classical and modern theory of finite semigroups, Adv. in Math. 11 (1973), 238–266.
John Rhodes and Benjamin Steinberg, Join irreducible pseudovarieties, group mapping, and Kovács-Newman semigroups, LATIN 2004: Theoretical informatics, Lecture Notes in Comput. Sci., vol. 2976, Springer, Berlin, 2004, pp. 279–291. MR 2095203, DOI 10.1007/978-3-540-24698-5_{3}2
John Rhodes and Benjamin Steinberg, The $q$-theory of finite semigroups, Springer Monographs in Mathematics, Springer, New York, 2009. MR 2472427, DOI 10.1007/b104443
Imre Simon, Piecewise testable events, Automata theory and formal languages (Second GI Conf., Kaiserslautern, 1975), Lecture Notes in Comput. Sci., Vol. 33, Springer, Berlin, 1975, pp. 214–222. MR 0427498
Howard Straubing, Aperiodic homomorphisms and the concatenation product of recognizable sets, J. Pure Appl. Algebra 15 (1979), no. 3, 319–327. MR 537504, DOI 10.1016/0022-4049(79)90025-2
Howard Straubing, Finite semigroup varieties of the form $V\ast D$, J. Pure Appl. Algebra 36 (1985), no. 1, 53–94. MR 782639, DOI 10.1016/0022-4049(85)90062-3
Howard Straubing and Denis Thérien, Partially ordered finite monoids and a theorem of I. Simon, J. Algebra 119 (1988), no. 2, 393–399. MR 971141, DOI 10.1016/0021-8693(88)90067-1
Pascal Weil, Some results on the dot-depth hierarchy, Semigroup Forum 46 (1993), no. 3, 352–370 (English, with English and French summaries). MR 1206213, DOI 10.1007/BF02573578