On bireversible Mealy automata and the Burnside problem. (English) Zbl 1405.68196
Summary: There exist undoubtedly strong links between the Burnside problem and the class of automaton groups. Indeed, many interesting examples of infinite Burnside groups are automaton groups, in particular for any prime \(p\), there exist an infinite Burnise \(p\)-group generated by a Mealy automaton. Moreover the simplest known example of an infinite Burnside group arises in this class. However there is no known example of such a group generated by a reversible Mealy automaton.
In this paper we prove that, in fact, no connected reversible Mealy automaton of prime size can generate an infinite Burnside group. In addition we explain how our method can be applied for some Mealy automata of non prime size.
In this paper we prove that, in fact, no connected reversible Mealy automaton of prime size can generate an infinite Burnside group. In addition we explain how our method can be applied for some Mealy automata of non prime size.
MSC:
| 68Q70 | Algebraic theory of languages and automata |
| 20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
| 20F50 | Periodic groups; locally finite groups |
References:
| [1] | Burnside, W., On an unsettled question in the theory of discontinuous groups, Quart. J. Math., 33, 230-238 (1902) · JFM 33.0149.01 |
| [2] | Golod, E., On nil-algebras and finitely residual groups, Izv. Akad. Nauk SSSR Ser. Mat., 28, 273-276 (1964) |
| [3] | Golod, E.; Shafarevich, I., On the class field tower, Izv. Akad. Nauk SSSR Ser. Mat., 28, 261-272 (1964) · Zbl 0136.02602 |
| [4] | Gluškov, V., Abstract theory of automata, Uspekhi Mat. Nauk, 16, 5, 3-62 (1961) |
| [5] | Alešin, S., Finite automata and the Burnside problem for periodic groups, Mat. Zametki, 11, 319-328 (1972) · Zbl 0246.20024 |
| [6] | Grigorchuk, R., On Burnside’s problem on periodic groups, Funktsional. Anal. i Prilozhen., 14, 1, 53-54 (1980) · Zbl 0595.20029 |
| [7] | Godin, Th.; Klimann, I.; Picantin, M., On torsion-free semigroups generated by invertible reversible Mealy automata, (LATA’15. LATA’15, LNCS, vol. 8977 (2015)), 328-339 · Zbl 1405.68197 |
| [8] | Klimann, I., Automaton semigroups: the two-state case, Theory Comput. Syst., Special issue STACS’13, 1-17 (2014) |
| [9] | Klimann, I.; Picantin, M.; Savchuk, D., A connected 3-state reversible Mealy automaton cannot generate an infinite Burnside group, (DLT’15. DLT’15, LNCS, vol. 9168 (2015)), 313-325 · Zbl 1386.68106 |
| [10] | D’Angeli, D.; Rodaro, E., A geometric approach to (semi)-groups defined by automata via dual transducers, Geom. Dedicata, 174, 1, 375-400 (2015) · Zbl 1322.20049 |
| [11] | Gawron, P.; Nekrashevych, V.; Sushchansky, V., Conjugation in tree automorphism groups, Internat. J. Algebra Comput., 11, 5, 529-547 (2001) · Zbl 1030.20015 |
| [12] | Grigorchuk, R.; Savchuk, D., Ergodic decomposition of group actions on rooted trees, Proc. Steklov Inst. Math., 292, 1, 94-111 (2016) · Zbl 1362.37013 |
| [13] | Godin, Th.; Klimann, I., Connected reversible Mealy automata of prime size cannot generate infinite Burnside groups, (MFCS’16. MFCS’16, LIPIcs, vol. 58 (2016)), 44:1-44:14 · Zbl 1398.68309 |
| [14] | Akhavi, A.; Klimann, I.; Lombardy, S.; Mairesse, J.; Picantin, M., On the finiteness problem for automaton (semi)groups, Internat. J. Algebra Comput., 22, 6 (2012), 26 pp · Zbl 1280.20038 |
| [15] | Zel’manov, E., Solution of the restricted Burnside problem for groups of odd exponent, Izv. Akad. Nauk SSSR Mat., 54, 1, 42-59 (1990), 221 · Zbl 0704.20030 |
| [16] | Zel’manov, E., Solution of the restricted Burnside problem for 2-groups, Mat. Sb., 182, 4, 568-592 (1991) · Zbl 0752.20017 |
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.
