Automatic semigroups vs automaton semigroups. (English) Zbl 07561617
Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 124, 15 p. (2019).
Summary: We develop an effective and natural approach to interpret any semigroup admitting a special language of greedy normal forms as an automaton semigroup, namely the semigroup generated by a Mealy automaton encoding the behaviour of such a language of greedy normal forms under one-sided multiplication. The framework embraces many of the well-known classes of (automatic) semigroups: free semigroups, free commutative semigroups, trace or divisibility monoids, braid or Artin-Tits or Krammer or Garside monoids, Baumslag-Solitar semigroups, etc. Like plactic monoids or Chinese monoids, some neither left- nor right-cancellative automatic semigroups are also investigated, as well as some residually finite variations of the bicyclic monoid. It provides what appears to be the first known connection from a class of automatic semigroups to a class of automaton semigroups. It is worthwhile noting that, “being an automatic semigroup” and “being an automaton semigroup” become dual properties in a very automata-theoretical sense. Quadratic rewriting systems and associated tilings appear as the cornerstone of our construction.
For the entire collection see [Zbl 1414.68003].
For the entire collection see [Zbl 1414.68003].
References:
| [1] | Ali Akhavi, Ines Klimann, Sylvain Lombardy, Jean Mairesse, and Matthieu Picantin. On the finiteness problem for automaton (semi)groups. Internat. J. Algebra Comput., 22(6):1-26, 2012. · Zbl 1280.20038 |
| [2] | Stanislas V. Alëšin. Finite automata and the Burnside problem for periodic groups. Mat. Zametki, 11:319-328, 1972. · Zbl 0246.20024 |
| [3] | Stanislav V. Alëšin. A free group of finite automata. Vestnik Moskov. Univ. Ser. I Mat. Mekh., 4:12-14, 1983. · Zbl 0513.68044 |
| [4] | Algirdas Avižienis. Signed-digit number representations for fast parallel arithmetic. IRE Trans. Electronic Computers, 10(3):389-400, 1961. |
| [5] | Laurent Bartholdi. FR -GAP package “Computations with functionally recursive groups”, Version 2.4.5, 2018. URL: http://www.gap-system.org/Packages/fr.html. |
| [6] | Laurent Bartholdi, Thibault Godin, Ines Klimann, and Matthieu Picantin. A New Hierarchy for Automaton Semigroups. In 23rd International Conference on Implementation and Applications of Automata (CIAA 2018), volume 10977 of LNCS, pages 71-83, 2018. · Zbl 1458.68084 |
| [7] | Laurent Bartholdi and Pedro V. Silva. Groups defined by automata. In J.-É. Pin, editor, AutoMathA Handbook. Europ. Math. Soc., 2010. (arXiv version: arXiv:1012.1531). |
| [8] | Laurent Bartholdi and Pedro V. Silva. Rational subsets of groups. In J.-É. Pin, editor, AutoMathA Handbook. Europ. Math. Soc., 2010. (arXiv version: arXiv:1012.1532). |
| [9] | Laurent Bartholdi and Zoran Šuniḱ. Some solvable automaton groups. In Topological and asymptotic aspects of group theory, volume 394 of Contemp. Math., pages 11-29. Amer. Math. Soc., Providence, RI, 2006. · Zbl 1106.20021 |
| [10] | Ievgen V. Bondarenko, Natalia V. Bondarenko, Saïd N. Sidki, and Flavia R. Zapata. On the conjugacy problem for finite-state automorphisms of regular rooted trees. Groups Geom. Dyn., 7(2):323-355, 2013. With an appendix by Raphaël M. Jungers. · Zbl 1286.20034 |
| [11] | Tara Brough and Alan J. Cain. Automaton semigroup constructions. Semigroup Forum, 90(3):763-774, 2015. · Zbl 1336.20062 |
| [12] | Tara Brough and Alan J. Cain. Automaton semigroups: new constructions results and examples of non-automaton semigroups. Theoret. Comput. Sci., 674:1-15, 2017. · Zbl 1381.20052 |
| [13] | Kai-Uwe Bux et al. Selfsimilar groups and conformal dynamics -Problem List. AIM workshop 2006. URL: http://www.aimath.org/WWN/selfsimgroups/selfsimgroups.pdf. |
| [14] | Alan J. Cain. Automaton semigroups. Theoret. Comput. Sci., 410(47-49):5022-5038, 2009. · Zbl 1194.68133 |
| [15] | Alan J. Cain. Personal communication, 2016. |
| [16] | Alan J. Cain, Robert D. Gray, and António Malheiro. Rewriting systems and biautomatic structures for Chinese, hypoplactic, and Sylvester monoids. Internat. J. Algebra Comput., 25(1-2):51-80, 2015. · Zbl 1326.20058 |
| [17] | Colin M. Campbell, Edmund F. Robertson, Nikola Ruškuc, and Richard M. Thomas. Automatic semigroups. Theoret. Comput. Sci., 250(1-2):365-391, 2001. · Zbl 0987.20033 |
| [18] | Augustin-Louis Cauchy. Sur les moyens d’éviter les erreurs dans les calculs numériques, volume 5 of Cambridge Library Collection -Mathematics, pages 431-442. Cambridge University Press, 2009. |
| [19] | Daniele D’Angeli, Thibault Godin, Ines Klimann, Matthieu Picantin, and Emanuele Rodaro. Boundary action of automaton groups without singular points and Wang tilings. Submitted, 2016. arXiv:1604.07736. |
| [20] | Patrick Dehornoy. Garside and quadratic normalisation: a survey. In 19th International Conference on Developments in Language Theory (DLT 2015), volume 9168 of LNCS, pages 14-45, 2015. · Zbl 1434.20038 |
| [21] | Patrick Dehornoy et al. Foundations of Garside theory. Europ. Math. Soc. Tracts in Mathem-atics, volume 22, 2015. URL: http://www.math.unicaen.fr/ garside/Garside.pdf. · Zbl 1370.20001 |
| [22] | Patrick Dehornoy and Yves Guiraud. Quadratic normalization in monoids. Internat. J. Algebra Comput., 26(5):935-972, 2016. · Zbl 1388.20072 |
| [23] | Murray Elder. Automaticity, almost convexity and falsification by fellow traveler properties of some finitely presented groups. PhD thesis, Univ Melbourne, 2000. |
| [24] | David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvio V. F. Levy, Michael S. Paterson, and William P. Thurston. Word processing in groups. Jones and Bartlett Publishers, Boston, MA, 1992. · Zbl 0764.20017 |
| [25] | Pierre Gillibert. The finiteness problem for automaton semigroups is undecidable. Internat. J. Algebra Comput., 24(1):1-9, 2014. · Zbl 1292.20040 |
| [26] | Thibault Godin, Ines Klimann, and Matthieu Picantin. On torsion-free semigroups generated by invertible reversible Mealy automata. In 9th International Conference on Language and Automata Theory and Applications (LATA 2015), pages 328-339, 2015. · Zbl 1405.68197 |
| [27] | Rostislav I. Grigorchuk. On Burnside’s problem on periodic groups. Funktsional. Anal. i Prilozhen., 14(1):53-54, 1980. · Zbl 0595.20029 |
| [28] | Rostislav I. Grigorchuk. Degrees of growth of finitely generated groups and the theory of invariant means. Izv. Akad. Nauk SSSR Ser. Mat., 48(5):939-985, 1984. |
| [29] | Yves Guiraud and Matthieu Picantin. Resolutions by differential graded polygraphs. In preparation, 2019. |
| [30] | Alexander Hess. Factorable monoids: resolutions and homology via discrete Morse theory. PhD thesis, Univ Bonn, 2012. URL: http://hss.ulb.uni-bonn.de/2012/2932/2932.pdf. · Zbl 1337.20073 |
| [31] | Alexander Hess and Viktoriya Ozornova. Factorability, string rewriting and discrete Morse theory. Submitted. arXiv:1412.3025. |
| [32] | Michael Hoffmann. Automatic Semigroups. PhD thesis, Univ Leicester, 2001. |
| [33] | Michael Hoffmann and Richard M. Thomas. Biautomatic semigroups. In 15th International Symposium on Fundamentals of Computation Theory (FCT 2005), volume 3623 of LNCS, pages 56-67, 2005. · Zbl 1123.68073 |
| [34] | Ines Klimann. The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), volume 20 of LIPIcs, pages 502-513, 2013. · Zbl 1354.68159 |
| [35] | Ines Klimann, Jean Mairesse, and Matthieu Picantin. Implementing Computations in Auto-maton (Semi)groups. In 17th International Conference on Implementation and Applications of Automata (CIAA 2012), volume 7381 of LNCS, pages 240-252, 2012. · Zbl 1297.68145 |
| [36] | Ines Klimann and Matthieu Picantin. Automaton (semi)groups: Wang tilings and Schreier tries. In Valérie Berthé and Michel Rigo, editors, Sequences, Groups, and Number Theory. Trends in Mathematics, 2018. · Zbl 1486.20043 |
| [37] | Ines Klimann, Matthieu Picantin, and Dmytro Savchuk. A Connected 3-State Reversible Mealy Automaton Cannot Generate an Infinite Burnside Group. In 19th International Conference on Developments in Language Theory (DLT 2015), volume 9168 of LNCS, pages 313-325, 2015. 124:15 · Zbl 1386.68106 |
| [38] | Ines Klimann, Matthieu Picantin, and Dmytro Savchuk. Orbit automata as a new tool to attack the order problem in automaton groups. J. Algebra, 445:433-457, 2016. · Zbl 1383.20018 |
| [39] | Daan Krammer. An asymmetric generalisation of Artin monoids. Groups Complex. Cryptol., 5:141-168, 2013. · Zbl 1303.20061 |
| [40] | Yaroslav Lavrenyuk, Volodymyr Mazorchuk, Andriy Oliynyk, and Vitaliy Sushchansky. Faithful group actions on rooted trees induced by actions of quotients. Comm. Algebra, 35(11):3759-3775, 2007. · Zbl 1187.20021 |
| [41] | Anatoly I. Malcev. On the immersion of an algebraic ring into a field. Math. Ann., 113(1):686-691, 1937. · Zbl 0015.38801 |
| [42] | Anatoly I. Malcev. Über die Einbettung von assoziativen Systemen in Gruppen. Rec. Math. [Mat. Sbornik] N.S., 6 (48):331-336, 1939. · Zbl 0022.31103 |
| [43] | Anatoly I. Malcev. Über die Einbettung von assoziativen Systemen in Gruppen. II. Rec. Math. [Mat. Sbornik] N.S., 8 (50):251-264, 1940. · JFM 66.0097.04 |
| [44] | Victor D. Mazurov and Evgeny I. Khukhro. Unsolved problems in group theory. The Kourovka Notebook. No 19. URL: https://kourovka-notebook.org/. |
| [45] | David McCune. Groups and Semigroups Generated by Automata. PhD thesis, Univ Nebraska-Lincoln, 2011. |
| [46] | Yevgen Muntyan and Dmytro Savchuk. AutomGrp -GAP package for computations in self-similar groups and semigroups, Version 1.3, 2016. URL: http://www.gap-system.org/ Packages/automgrp.html. |
| [47] | Volodymyr V. Nekrashevych. Self-similar groups, volume 117 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2005. · Zbl 1087.20032 |
| [48] | Viktoriya Ozornova. Factorability, discrete Morse theory, and a reformularion of K(π, 1)-conjecture. PhD thesis, Univ Bonn, 2013. URL: http://hss.ulb.uni-bonn.de/2013/3117/ 3117.pdf. |
| [49] | Matthieu Picantin. Finite transducers for divisibility monoids. Theoret. Comput. Sci., 362(1-3):207-221, 2006. · Zbl 1100.68057 |
| [50] | Matthieu Picantin. Tree products of cyclic groups and HNN extensions. Preprint, 2015. arXiv:1306.5724v4. |
| [51] | Matthieu Picantin. Automates, (semi)groupes, dualités. Habilitation à diriger des recherches, Univ Paris Diderot, 2017. URL: https://www.irif.fr/ picantin/papers/hdr_memoire.pdf and https://www.irif.fr/ picantin/papers/hdr_soutenance.pdf. |
| [52] | Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, New York, NY, USA, 2009. · Zbl 1188.68177 |
| [53] | Marcel-Paul Schützenberger. Pour le monoïde plaxique. Math. Inform. Sci. Humaines, 140:5-10, 1997. · Zbl 0948.20040 |
| [54] | Pedro V. Silva. Groups and Automata: A Perfect Match. In 14th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2012), volume 7386 of LNCS, pages 50-63, 2012. · Zbl 1304.68122 |
| [55] | Pedro V. Silva and Benjamin Steinberg. On a class of automata groups generalizing lamplighter groups. Internat. J. Algebra Comput., 15(5-6):1213-1234, 2005. · Zbl 1106.20028 |
| [56] | Bartosz Tarnawski. Automatic groups as groups defined by transducers. Master’s thesis, Univ Warsaw, Faculty of Mathematics, Informatics and Mechanics, Poland, 2017. |
| [57] | Daniel T. Wise. A non-Hopfian automatic group. J. Algebra, 180(3):845-847, 1996. · Zbl 0848.20028 |
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.
