×

Profinite topologies. (English) Zbl 1511.68176

Pin, Jean-Éric (ed.), Handbook of automata theory. Volume I. Theoretical foundations. Berlin: European Mathematical Society (EMS). 615-652 (2021).
Profinite algebras are inverse limits of inverse systems of finite algebras and have become an important tool in the theory of finite automata. Here, the authors present an overview of research carried out in this area – precise definitions and the most significant results without proofs; for proofs references to original papers are indicated. The first chapter is an introduction to the theory and contains definitions from abstract algebra (signature, homomorphism, syntactic congruence, variety, pseudovariety, pseudoquasivariety, recognizable subset) and topology (pseudometric and uniform spaces, nets, continuity, compactness). In the second chapter this machinery is used to consider universal algebras, e.g. to present Reiterman’s theorem [J. Reiterman, Algebra Univers. 14, 1–10 (1982; Zbl 0484.08007)], “A subclass of a pseudovariety \(V\) is a pseudovariety iff it is defined by some set of pseudoidentities for \(V\)”, and various results on decidability. In the third chapter the authors consider semigroups – the area that is most important for automata and language theory. Because of its importance in practice, a vast number of papers in this area have been published, thus the authors remark that “results mentioned in this section by no means cover entirely the literature in the area that is presently available. In particular, we stick to the more classical case of semigroups”; for instance, they leave aside ordered semigroups or stamps. Here they consider computing profinite closures and tameness. In the fourth chapter they consider relatively free profinite semigroups: connections with symbolic dynamics and closed subgroups of relatively free profinite semigroups. The paper has an extensive list of references (109) and for the referenced papers also their q.v. (quod vide) are indicated, i.e., other pages where this paper is relevant.
For the entire collection see [Zbl 1470.68001].

MSC:

68Q70 Algebraic theory of languages and automata
08A70 Applications of universal algebra in computer science
20M35 Semigroups in automata theory, linguistics, etc.
54H13 Topological fields, rings, etc. (topological aspects)

Citations:

Zbl 0484.08007
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] D. Albert, R. Baldinger, and J. Rhodes, Undecidability of the identity problem for finite semigroups. J. Symbolic Logic 57 (1992), no. 1, 179-192. MR 1150933 Zbl 0780.20035 q.v. 631 · Zbl 0780.20035
[2] K. Alibabaei, Every decidable pseudovariety of abelian groups is completely tame. Semi-group Forum 99 (2019), no. 1, 106-125. MR 3978501 Zbl 07080906 q.v. 639 · Zbl 1442.20033
[3] K. Alibabaei, The pseudovariety of all nilpotent groups is tame. Internat. J. Algebra Com-put. 29 (2019), no. 6, 1019-1034. MR 3996983 Zbl 07119216 q.v. 639 · Zbl 1468.20097
[4] J. Almeida, Residually finite congruences and quasi-regular subsets in uniform algebras. Portugal. Math. 46 (1989), no. 3, 313-328. MR 1021193 Zbl 0688.08001 q.v. 625 · Zbl 0688.08001
[5] J. Almeida, On pseudovarieties, varieties of languages, filters of congruences, pseudoiden-tities and related topics. Algebra Universalis 27 (1990), no. 3, 333-350. MR 1058478 Zbl 0715.08006 q.v. 630 · Zbl 0715.08006
[6] J. Almeida, Finite semigroups and universal algebra. Translated from the 1992 Por-tuguese original and revised by the author. Series in Algebra, 3. World Scientific, River Edge, N.J., 1994. MR 1331143 Zbl 0844.20039 q.v. 630, 639, 640, 641
[7] J. Almeida, Hyperdecidable pseudovarieties and the calculation of semidirect products. Internat. J. Algebra Comput. 9 (1999), no. 3-4, 241-261. Dedicated to the memory of Marcel-Paul Schützenberger. MR 1722629 Zbl 1028.20038 q.v. 631, 632, 637
[8] J. Almeida, Some algorithmic problems for pseudovarieties. Publ. Math. Debrecen 54 (1999), suppl., 531-552. Automata and formal languages, VIII (Salgótarján, 1996). MR 1709911 Zbl 0981.20049 q.v. 631 · Zbl 0981.20049
[9] J. Almeida, Dynamics of implicit operations and tameness of pseudovarieties of groups. Trans. Amer. Math. Soc. 354 (2002), no. 1, 387-411. MR 1859280 Zbl 0988.20014 q.v. 639 · Zbl 0988.20014
[10] J. Almeida, Finite semigroups: an introduction to a unified theory of pseudovarieties. In Semigroups, algorithms, automata and languages (G. M. S. Gomes, J.-É. Pin, and P. V. Silva, eds.). Papers from the Thematic Term held in Coimbra, May-July 2001. World Scientific, River Edge, N,J., 2002, 3-64. MR 2023783 Zbl 1033.20067 q.v. 624, 625, 627, 631, 632
[11] J. Almeida, Profinite groups associated with weakly primitive substitutions. Fun-dam. Prikl. Mat. 11 (2005), no. 3, 13-48. In Russian. English translation, J. Math. Sci. (N.Y.) 144 (2007), no. 2, 3881-3903. MR 2176678 Zbl 1110.20022 q.v. 642, 644 · Zbl 1110.20022
[12] J. Almeida, Profinite semigroups and applications. Notes taken by A. Costa. In Struc-tural theory of automata, semigroups, and universal algebra (V. B. Kudryavtsev and I. G. Rosenberg, eds.). Proceedings of the NATO Advanced Study Institute (the 42 nd Séminaire des Mathématiques Supérieures) held at the University of Montreal, Montreal, QC, July 7-18, 2003, 1-45. MR 2210124 Zbl 1109.20050 q.v. 627
[13] J. Almeida and C. Borlido, Complete -reducibility of pseudovarieties of the form DRH. Internat. J. Algebra Comput. 27 (2017), no. 2, 189-235. MR 3633403 Zbl 06717910 q.v. 640 · Zbl 1472.20123
[14] J. Almeida and A. Costa, Infinite-vertex free profinite semigroupoids and symbolic dy-namics. J. Pure Appl. Algebra 213 (2009), no. 5, 605-631. MR 2494356 Zbl 1179.20050 q.v. 639, 642 · Zbl 1179.20050
[15] J. Almeida and A. Costa, Presentations of Schützenberger groups of minimal subshifts. Israel J. Math. 196 (2013), no. 1, 1-31. MR 3096581 Zbl 1293.20054 q.v. 644 · Zbl 1293.20054
[16] J. Almeida and A. Costa, A note on pseudovarieties of completely regular semigroups. Bull. Aust. Math. Soc. 92 (2015), no. 2, 233-237. MR 3392250 Zbl 1346.20074 q.v. 639 · Zbl 1346.20074
[17] J. Almeida and A. Costa, A geometric interpretation of the Schützenberger group of a minimal subshift. Ark. Mat. 54 (2016), no. 2, 243-275. MR 3546353 Zbl 1394.20033 q.v. 644 · Zbl 1394.20033
[18] J. Almeida, A. Costa, J. C. Costa, and M. Zeitoun, The linear nature of pseudowords. Publ. Mat. 63 (2019), no. 2, 361-422. MR 3980930 Zbl 07094859 q.v. 641 · Zbl 1508.20071
[19] J. Almeida, J. C. Costa, and M. L. Teixeira, Semidirect product with an order-computable pseudovariety and tameness. Semigroup Forum 81 (2010), no. 1, 26-50. MR 2672170 Zbl 1229.20059 q.v. 640 · Zbl 1229.20059
[20] J. Almeida, J. C. Costa, and M. Zeitoun, Tameness of pseudovariety joins involving R. Monatsh. Math. 146 (2005), no. 2, 89-111. MR 2176337 Zbl 1091.20036 q.v. 640 · Zbl 1091.20036
[21] J. Almeida, J. C. Costa, and M. Zeitoun, Complete reducibility of systems of equations with respect to R. Port. Math. (N.S.) 64 (2007), no. 4, 445-508. MR 2374398 Zbl 1148.20042 q.v. 639 · Zbl 1148.20042
[22] J. Almeida, J. C. Costa, and M. Zeitoun, Closures of regular languages for profinite topologies. Semigroup Forum 89 (2014), no. 1, 20-40. MR 3249866 Zbl 1307.20048 q.v. 637 · Zbl 1307.20048
[23] J. Almeida and M. Delgado, Sur certains systèmes d’équations avec contraintes dans un groupe libre. Port. Math. (N.S.) 56 (1999), no. 4, 409-417. MR 1732025 Zbl 0960.20014 q.v. 638, 639 · Zbl 0960.20014
[24] J. Almeida and M. Delgado, Sur certains systèmes d’équations avec contraintes dans un groupe libre -addenda. Port. Math. (N.S.) 58 (2001), no. 4, 379-387. MR 1881867 Zbl 0960.20014 q.v. 638, 639 · Zbl 1046.20023
[25] J. Almeida and M. Delgado, Tameness of the pseudovariety of abelian groups. Internat. J. Algebra Comput. 15 (2005), no. 2, 327-338. MR 2142087 Zbl 1083.20045 q.v. 638 · Zbl 1083.20045
[26] J. Almeida and O. Klíma, Towards a pseudoequational proof theory. Port. Math. (N.S.) 75 (2018), no. 2, 79-119. MR 3892751 Zbl 07031079 q.v. 633 · Zbl 1504.20057
[27] J. Almeida, M. H. Shahzamanian, and B. Steinberg, The pro-nilpotent group topology on a free group. J. Algebra 480 (2017), 332-345. MR 3633311 Zbl 06710531 q.v. 637 · Zbl 1472.20124
[28] J. Almeida and P. V. Silva, On the hyperdecidability of semidirect products of pseudova-rieties. Comm. Algebra 26 (1998), no. 12, 4065-4077. MR 1661260 Zbl 0931.20047 q.v. 640 · Zbl 0931.20047
[29] J. Almeida and P. V. Silva, SC-hyperdecidability of R. Theoret. Comput. Sci. 255 (2001), no. 1-2, 569-591. MR 1819091 Zbl 0989.20045 q.v. 639 · Zbl 0989.20045
[30] J. Almeida and B. Steinberg, On the decidability of iterated semidirect products with ap-plications to complexity. Proc. London Math. Soc. (3) 80 (2000), no. 1, 50-74. MR 1719180 Zbl 1027.20033 q.v. 631, 633, 634, 635, 638, 639, 640 · Zbl 1027.20033
[31] J. Almeida and B. Steinberg, Syntactic and global semigroup theory, a synthesis ap-proach. In Algorithmic problems in groups and semigroups (J. C. Birget, S. W. Margolis, J. Meakin, and M. V. Sapir, eds.). Papers from the International Conference held at the University of Nebraska, Lincoln, NE, May 11-16, 1998. Trends in Mathematics. Birkhäuser Boston, Boston, MA, 2000, 1-23. MR 1750489 Zbl 0947.20043 q.v. 633, 637
[32] J. Almeida and B. Steinberg, Rational codes and free profinite monoids. J. Lond. Math. Soc. (2) 79 (2009), no. 2, 465-477. MR 2496524 Zbl 1172.20039 q.v. 619, 628 · Zbl 1172.20039
[33] J. Almeida and P. G. Trotter, Hyperdecidability of pseudovarieties of orthogroups. Glasg. Math. J. 43 (2001), no. 1, 67-83. MR 1825723 Zbl 0982.20040 q.v. 639 · Zbl 0982.20040
[34] J. Almeida and P. G. Trotter, The pseudoidentity problem and reducibility for completely regular semigroups. Bull. Austral. Math. Soc. 63 (2001), no. 3, 407-433. MR 1834943 Zbl 0982.20042 q.v. 639 · Zbl 0982.20042
[35] 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 Zbl 1186.20040 q.v. 643, 644 · Zbl 1186.20040
[36] J. Almeida and P. Weil, Relatively free profinite monoids: an introduction and examples. In Semigroups, formal languages and groups (J. B. Fountain, ed.). Proceedings of the NATO Advanced Study Institute held at the University of York, York, August 7-21, 1993. NATO Advanced Science Institutes Series C: Mathematical and Physical Sci-ences, 466. Kluwer Academic Publishers Group, Dordrecht, 1995, 73-117. MR 1630619 Zbl 0877.20038 q.v. 625 · Zbl 0877.20038
[37] J. Almeida and P. Weil, Free profinite R-trivial monoids. Internat. J. Algebra Comput. 7 (1997), no. 5, 625-671. MR 1470356 Zbl 0892.20035 q.v. 639, 641 · Zbl 0892.20035
[38] J. Almeida and P. Weil, Profinite categories and semidirect products. J. Pure Appl. Alge-bra 123 (1998), no. 1-3, 1-50. MR 1492894 Zbl 0891.20037 q.v. 631 · Zbl 0891.20037
[39] J. Almeida and M. Zeitoun, The pseudovariety J is hyperdecidable. RAIRO Inform. Théor. Appl. 31 (1997), no. 5, 457-482. MR 1611659 Zbl 0928.20046 q.v. 639 · Zbl 0928.20046
[40] J. Almeida and M. Zeitoun, An automata-theoretic approach to the word problem for !-terms over R. Theoret. Comput. Sci. 370 (2007), no. 1-3, 131-169. MR 2289710 Zbl 1110.68059 q.v. 641 · Zbl 1110.68059
[41] C. J. Ash, Inevitable graphs: a proof of the type II conjecture and some related decision procedures. Internat. J. Algebra Comput. 1 (1991), no. 1, 127-146. MR 1112302 Zbl 0722.20039 q.v. 633, 636, 638 · Zbl 0722.20039
[42] K. Auinger and B. Steinberg, On the extension problem for partial permutations. Proc. Amer. Math. Soc. 131 (2003), no. 9, 2693-2703. MR 1974324 Zbl 1027.20035 q.v. 631 · Zbl 1027.20035
[43] G. Birkho , On the structure of abstract algebras. Proc. Cambridge Phil. Soc. 31 (1935), 433-454. JFM 61.1026.07 Zbl 0013.00105 q.v. 617, 618 · Zbl 0013.00105
[44] G. Birkho , Moore-Smith convergence in general topology. Ann. of Math. (2) 38 (1937), no. 1, 39-56. MR 1503323 JFM 63.0567.06 Zbl 0016.08502 q.v. 616 · Zbl 0016.08502
[45] S. Burris and H. P. Sankappanavar, A course in universal algebra. Graduate Texts in Mathematics, 78. Springer, Berlin, 1981. MR 0648287 Zbl 0478.08001 q.v. 616, 626 · Zbl 0478.08001
[46] D. Clark, B. A. Davey, R. S. Freese, and M. Jackson, Standard topological algebras: syn-tactic and principal congruences and profiniteness. Algebra Universalis 52 (2004), no. 2-3, 343-376. MR 2161658 Zbl 1088.08006 q.v. 618, 625 · Zbl 1088.08006
[47] A. Costa, Conjugacy invariants of subshifts: an approach from profinite semigroup theory. Internat. J. Algebra Comput. 16 (2006), no. 4, 629-655. MR 2258833 Zbl 1121.37013 q.v. 642, 644 · Zbl 1121.37013
[48] A. Costa and B. Steinberg, Profinite groups associated to sofic shifts are free. Proc. Lond. Math. Soc. (3) 102 (2011), no. 2, 341-369. MR 2769117 Zbl 1257.20054 q.v. 641, 642, 643, 645 · Zbl 1257.20054
[49] J. C. Costa, Free profinite locally idempotent and locally commutative semigroups. J. Pure Appl. Algebra 163 (2001), no. 1, 19-47. MR 1847374 Zbl 0990.20038 q.v. 641, 642 · Zbl 0990.20038
[50] J. C. Costa and C. Nogueira. Complete reducibility of the pseudovariety LSl. Internat. J. Algebra Comput. 19 (2009), no. 2, 247-282. MR 2512554 Zbl 1188.20069 q.v. 640 · Zbl 1188.20069
[51] J. C. Costa and M. L. Teixeira, Tameness of the pseudovariety LSl. Internat. J. Algebra Comput. 14 (2004), no. 5-6, 627-654. International Conference on Semigroups and Groups in honor of the 65 th birthday of Prof. John Rhodes. MR 2104772 Zbl 1087.20039 q.v. 640 · Zbl 1087.20039
[52] T. Coulbois and A. Khélif, Equations in free groups are not finitely approximable. Proc. Amer. Math. Soc. 127 (1999), no. 4, 963-965. MR 1485465 Zbl 0914.20031 q.v. 638 · Zbl 0914.20031
[53] M. Delgado, On the hyperdecidability of pseudovarieties of groups. Internat. J. Algebra Comput. 11 (2001), no. 6, 753-771. MR 1880376 Zbl 1880376 q.v. 637 · Zbl 1026.20039
[54] M. Delgado, A. Masuda, and B. Steinberg, Solving systems of equations modulo pseu-dovarieties of abelian groups and hyperdecidability. In Semigroups and formal lan-guages (J. M. André, V. H. Fernandes, M. J. J. Branco, G. M. S. Gomes, J. Fountain, and J. C. Meakin, eds.). Proceedings of the International Conference held at the Universidade de Lisboa, Lisboa, July 12-15, 2005. World Scientific, Hackensack, N.J., 2007, 57-65. MR 2364777 Zbl 1133.20046 q.v. 639 · Zbl 1133.20046
[55] F. Durand, B. Host, and C. Skau, Substitutional dynamical systems, Bratteli diagrams and dimension groups. Ergodic Theory Dynam. Systems 19 (1999), no. 4, 953-993. MR 1709427 Zbl 1044.46543 q.v. 644 · Zbl 1044.46543
[56] S. Eilenberg, Automata, languages, and machines. Vol. B. With two chapters by B. Tilson. Pure and Applied Mathematics, 59. Academic Press, New York and London, 1976. MR 0530383 Zbl 0359.94067 q.v. 630, 635, 639, 640 · Zbl 0359.94067
[57] M. Gehrke, S. Grigorie , and J.-É. Pin, Duality and equational theory of regular lan-guages. In Automata, languages and programming (L. Aceto, I. Damgård, L. A. Gold-berg, M. M. Halldórsson, A. Ingólfsdóttir, and I. Walukiewicz, eds.). Part II. Proceedings of the 35 th International Colloquium (ICALP 2008) held in Reykjavik, July 7-11, 2008. Lecture Notes in Computer Science, 5126. Springer, Berlin, 2008, 246-257. MR 2503592 Zbl 1165.68049 q.v. 615, 626 · Zbl 1165.68049
[58] M. Gehrke, S. Grigorie , and J.-É. Pin, A topological approach to recognition. In Automata, languages and programming (S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide and P. G. Spirakis, eds.). Part II. Proceedings of the 37 th Interna-tional Colloquium (ICALP 2010) held in Bordeaux, July 6-10, 2010. Lecture Notes in Computer Science, 6199. Springer, Berlin, 2010, 151-162. MR 2734643 Zbl 1288.68176 q.v. 615, 626 · Zbl 1288.68176
[59] S. J. v. Gool and B. Steinberg, Pro-aperiodic monoids via saturated models. In 34 th Sym-posium on Theoretical Aspects of Computer Science (H. Vollmer and B. Vallée, eds.). Pro-ceedings of the symposium (STACS 2017) held in Hannover, March 8-11, 2017. LIPIcs. Leibniz International Proceedings in Informatics, 66. Schloss Dagstuhl. Leibniz-Zentrum für Informatik, Wadern, 2017, Art. No. 39, 14 pp. MR 3655366 Zbl 1402.68126 q.v. 641 · Zbl 1402.68126
[60] M. Hall, A topology for free groups and related groups. Ann. of Math. (2) 52 (1950), 127-139. MR 0036767 Zbl 0041.36210 Zbl 0045.31204 q.v. 636 · Zbl 0041.36210
[61] K. Henckell, Pointlike sets: the finest aperiodic cover of a finite semigroup. J. Pure Appl. Algebra 55 (1988), no. 1-2, 85-126. MR 0968571 Zbl 0682.20044 q.v. 640 · Zbl 0682.20044
[62] K. Henckell and J. Rhodes, The theorem of Knast, the P G D BG and Type II con-jectures. In Monoids and semigroups with applications (J. Rhodes, ed). Proceedings of the Workshop on Monoids held at the University of California, Berkeley, California, July 31-August 5, 1989. World Scientific, River Edge, N.J., 1991, 453-463. MR 1142393 Zbl 0826.20054 q.v. 638 · Zbl 0826.20054
[63] K. Henckell, J. Rhodes, and B. Steinberg, Aperiodic pointlikes and beyond. Internat. J. Algebra Comput. 20 (2010), no. 2, 287-305. MR 2646752 Zbl 1227.20049 q.v. 640 · Zbl 1227.20049
[64] B. Herwig and D. Lascar, Extending partial automorphisms and the profinite topology on free groups. Trans. Amer. Math. Soc. 352 (2000), no. 5, 1985-2021. MR 1621745 Zbl 0947.20018 q.v. 638 · Zbl 0947.20018
[65] R. P. Hunter, Some remarks on subgroups defined by the Bohr compactification. Semi-group Forum 26 (1983), no. 1-2, 125-137. MR 0685122 Zbl 0503.22001 q.v. 627 · Zbl 0503.22001
[66] R. P. Hunter, Certain finitely generated compact zero-dimensional semigroups. J. Austral. Math. Soc. Ser. A 44 (1988), no. 2, 265-270. MR 0922611 Zbl 0649.22002 q.v. 625 · Zbl 0649.22002
[67] M. Huschenbett and M. Kufleitner, Ehrenfeucht-Fraïssé games on omega-terms. In 31 st International Symposium on Theoretical Aspects of Computer Science (E. W. Mayr and N. Portier, eds.). Proceedings of the Symposium (STACS’14) held in Lyon, March 5-8, 2014. LIPIcs. Leibniz International Proceedings in Informatics, 25. Schloss Dagstuhl. Leibniz-Zentrum für Informatik, Wadern, 2014, 374-385. MR 3181430 Zbl 1359.03013 q.v. 641 · Zbl 1359.03013
[68] J. Karnofsky and J. Rhodes, Decidability of complexity one-half for finite semigroups. Semigroup Forum 24 (1982), no. 1, 55-66. MR 0645703 Zbl 0503.20028 q.v. 638 · Zbl 0503.20028
[69] O. G. Kharlampovich and M. Sapir, Algorithmic problems in varieties. Internat. J. Algebra Comput. 5 (1995), no. 4-5, 379-602. MR 1361261 Zbl 0837.08002 q.v. 630 · Zbl 0837.08002
[70] K. Krohn and J. Rhodes, Complexity of finite semigroups. Ann. of Math. (2) 88 (1968), 128-160. MR 0236294 Zbl 0162.03902 q.v. 640 · Zbl 0162.03902
[71] M. Kufleitner and J. P. Wächter, The word problem for omega-terms over the Trotter-Weil hierarchy. Theory Comput. Syst. 62 (2018), no. 3, 682-738. MR 3774450 Zbl 06879947 q.v. 641 · Zbl 1435.20065
[72] D. Lind and B. Marcus, An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge, 1995. MR 1369092 Zbl 1106.37301 q.v. 641, 643 · Zbl 1106.37301
[73] M. Lothaire, Algebraic combinatorics on words. A collective work by J. Berstel, D. Perrin, P. Seebold, J. Cassaigne, A. De Luca, S. Varricchio, A. Lascoux, B. Leclerc, J.-Y. Thibon, V. Bruyère, C. Frougny, F. Mignosi, A. Restivo, C. Reutenauer, D. Foata, G.-N. Han, J. Désarménien, V. Diekert, T. Harju, J. Karhumäki and W. Plandowski. With a preface by Berstel and Perrin. Encyclopedia of Mathematics and its Applications, 90. Cambridge University Press, Cambridge, 2002. MR 905123 Zbl 1001.68093 q.v. 642 · Zbl 1001.68093
[74] G. S. Makanin, The problem of solvability of equations in a free semigroup. Mat. Sb. (N.S.) 103(145) (1977), no. 2, 147-236, 319. In Russian. English translation, Math. USSR-Sb. 32 (1977), 128-198. MR 0470107 Zbl 0396.20037 q.v. 639 · Zbl 0396.20037
[75] S. Margolis, M. Sapir, and P. Weil, Closed subgroups in pro-V topologies and the ex-tension problem for inverse automata. Internat. J. Algebra Comput. 11 (2001), no. 4, 405-445. MR 1850210 Zbl 1027.20036 q.v. 637 · Zbl 1027.20036
[76] J. McCammond, Normal forms for free aperiodic semigroups. Internat. J. Algebra Com-put. 11 (2001), no. 5, 581-625. MR 1869233 Zbl 1026.20037 q.v. 640 · Zbl 1026.20037
[77] V. A. Molchanov, Nonstandard characterization of pseudovarieties. Algebra Univer-salis 33 (1995), no. 4, 533-547. MR 1331916 Zbl 0840.03055 q.v. 630 · Zbl 0840.03055
[78] A. Moura, Representations of the free profinite object over DA. Internat. J. Algebra Com-put. 21 (2011), no. 5, 675-701. MR 2827197 Zbl 1243.20070 q.v. 641 · Zbl 1243.20070
[79] N. Nikolov and D. Segal, Finite index subgroups in profinite groups. C. R. Math. Acad. Sci. Paris 337 (2003), no. 5, 303-308. MR 2016979 Zbl 1033.20029 q.v. 626 · Zbl 1033.20029
[80] K. Numakura, Theorems on compact totally disconnected semigroups and lattices. Proc. Amer. Math. Soc. 8 (1957), 623-626. MR 0087032 Zbl 0081.25602 q.v. 625 · Zbl 0081.25602
[81] P. Perkins, Bases for equational theories of semigroups. J. Algebra 11 (1969), 298-314. MR 0233911 q.v. 630 · Zbl 0186.03401
[82] J.-É. Pin, Topologies for the free monoid. J. Algebra 137 (1991), no. 2, 297-337. MR 1094245 Zbl 0739.20032 q.v. 637 · Zbl 0739.20032
[83] J.-É. Pin, Eilenberg’s theorem for positive varieties of languages. Izv. Vyssh. Uchebn. Zaved. Mat. 1995, no. 1, 80-90. In Russian. English translation, Russian Math. (Iz. VUZ) 39 (1995), no. 1, 74-83. MR 1391325 Zbl 0852.20059 q.v. 630 · Zbl 0852.20059
[84] J.-É. Pin and C. Reutenauer, A conjecture on the Hall topology for the free group. Bull. London Math. Soc. 23 (1991), no. 4, 356-362. MR 1125861 Zbl 0754.20007 q.v. 636 · Zbl 0754.20007
[85] J.-É. Pin and P. V. Silva, On profinite uniform structures defined by varieties of finite monoids. Internat. J. Algebra Comput. 21 (2011), no. 1-2, 295-314. MR 2787462 Zbl 1238.20068 q.v. 623 · Zbl 1238.20068
[86] J.-É. Pin and P. V. Silva, A noncommutative extension of Mahler’s theorem on interpola-tion series. European J. Combin. 36 (2014), 564-578. MR 3131915 Zbl 1357.11116 q.v. 624 · Zbl 1357.11116
[87] J.-É. Pin and P. Weil, Profinite semigroups, Mal’cev products and identities. J. Al-gebra 182 (1996), no. 3, 604-626. MR 1398113 Zbl 0857.20040 q.v. 631 · Zbl 0857.20040
[88] J.-É. Pin and P. Weil, A Reiterman theorem for pseudovarieties of finite first-order struc-tures. Algebra Universalis 35 (1996), no. 4, 577-595. MR 1392285 Zbl 0864.03024 q.v. 630 · Zbl 0864.03024
[89] T. Place and M. Zeitoun, Going higher in the first-order quantifier alternation hierarchy on words. In Automata, languages, and programming (J. Esparza, P. Fraigniaud, T. Husfeldt, and E. Koutsoupias, eds.). Part II. Proceedings of the 41 st International Colloquium (ICALP 2014) held at the IT University of Copenhagen, Copenhagen, July 8-11, 2014. Lecture Notes in Computer Science, 8573. Springer, Berlin, 2014, 342-353. MR 3238384 Zbl 1407.03055 q.v. 637 · Zbl 1407.03055
[90] T. Place and M. Zeitoun, Separating regular languages with first-order logic. In Proceed-ings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). Held in Vienna, July 14-18, 2014. Association for Computing Machinery, New York, 2014, Article no. 75, 10 pp. MR 3397696 Zbl 1401.68165 q.v. 640 · Zbl 1401.68165
[91] L. Polák, A classification of rational languages by semilattice-ordered monoids. Arch. Math. (Brno) 40 (2004), no. 4, 395-406. MR 2129961 Zbl 1112.68098 q.v. 630 · Zbl 1112.68098
[92] N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics (V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel, eds.). Lecture Notes in Mathematics, 1794. Springer, Berlin, 2002. MR 1970385 Zbl 1014.11015 q.v. 642
[93] J. Reiterman, The Birkho theorem for finite algebras. Algebra Universalis 14 (1982), no. 1, 1-10. MR 0634411 Zbl 0484.08007 q.v. 630 · Zbl 0484.08007
[94] J. Rhodes and B. Steinberg, Profinite semigroups, varieties, expansions and the structure of relatively free profinite semigroups. Internat. J. Algebra Comput. 11 (2001), no. 6, 627-672. MR 1880372 Zbl 1026.20057 q.v. 641, 645 · Zbl 1026.20057
[95] J. Rhodes and B. Steinberg, Closed subgroups of free profinite monoids are projective profinite groups. Bull. Lond. Math. Soc. 40 (2008), no. 3, 375-383. MR 2418793 Zbl 1153.20029 q.v. 645 · Zbl 1153.20029
[96] J. Rhodes and B. Steinberg, The q-theory of finite semigroups. Springer Monographs in Mathematics. Springer, New York, 2009. MR 2472427 Zbl 1186.20043 q.v. 631, 632, 644, 645
[97] L. Ribes and P. A. Zalesskiȋ, On the profinite topology on a free group. Bull. London Math. Soc. 25 (1993), no. 1, 37-43. MR 1190361 Zbl 0811.20026 q.v. 636 · Zbl 0811.20026
[98] L. Ribes and P. A. Zalesskiȋ, The pro-p topology of a free group and algorithmic prob-lems in semigroups. Internat. J. Algebra Comput. 4 (1994), no. 3, 359-374. MR 1297146 Zbl 0839.20041 q.v. 637 · Zbl 0839.20041
[99] L. Ribes and P. A. Zalesskiȋ, Profinite groups. Ergebnisse der Mathematik und ihrer Gren-zgebiete, 3. Folge, 40. Springer, Berlin, 2000. MR 1775104 Zbl 0949.20017 q.v. 627, 644, 645
[100] M. V. Sapir, On the finite basis property for pseudovarieties of finite semigroups. C. R. Acad. Sci. Paris Sér. I Math. 306 (1988), no. 20, 795-797. MR 0949035 Zbl 0658.20033 q.v. 630 · Zbl 0658.20033
[101] B. Steinberg, Inevitable graphs and profinite topologies: some solutions to algorith-mic problems in monoid and automata theory, stemming from group theory. Internat. J. Algebra Comput. 11 (2001), no. 1, 25-71. MR 1818661 Zbl 1024.68064 q.v. 639 · Zbl 1024.68064
[102] B. Steinberg, On algorithmic problems for joins of pseudovarieties. Semigroup Forum 62 (2001), no. 1, 1-40. MR 1832252 Zbl 0980.20055 q.v. 635, 641 · Zbl 0980.20055
[103] B. Steinberg, A combinatorial property of ideals in free profinite monoids. J. Pure Appl. Algebra 214 (2010), no. 9, 1693-1695. MR 2593694 Zbl 1203.20052 q.v. 641 · Zbl 1203.20052
[104] B. Steinberg, Maximal subgroups of the minimal ideal of a free profinite monoid are free. Israel J. Math. 176 (2010), 139-155. MR 2653189 Zbl 1220.20045 q.v. 641, 645 · Zbl 1220.20045
[105] B. Steinberg, On the endomorphism monoid of a profinite semigroup. Port. Math. 68 (2011), no. 2, 177-183. MR 2849853 Zbl 1226.22003 q.v. 627 · Zbl 1226.22003
[106] M. Steinby, A theory of tree language varieties. In Tree automata and languages (M. Nivat and A. Podelski, eds.). Papers from the workshop held in Le Touquet, June 1990. Stud-ies in Computer Science and Artificial Intelligence, 10. North-Holland Publishing Co., Amsterdam, 1992, 57-81. MR 1196732 Zbl 0798.68087 q.v. 630
[107] M. V. Volkov, On a class of semigroup pseudovarieties without finite pseudoidentity ba-sis. Internat. J. Algebra Comput. 5 (1995), no. 2, 127-135. MR 1328547 Zbl 0834.20058 q.v. 630 · Zbl 0834.20058
[108] P. Walters, An Introduction to ergodic theory. Graduate Texts in Mathematics, 79. Springer, Berlin, 1982. MR 0648108 Zbl 0475.28009 q.v. 642 · Zbl 0475.28009
[109] S. Willard, General topology. Addison-Wesley, Reading, MA, 1970. MR 0264581 Zbl 0205.26601 q.v. 619, 620, 621, 624, 625 · Zbl 0205.26601
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.