×

zbMATH — the first resource for mathematics

Orbit automata as a new tool to attack the order problem in automaton groups. (English) Zbl 1383.20018
Summary: We introduce a new tool, called the orbit automaton, that describes the action of an automaton group \(G\) on the subtrees corresponding to the orbits of \(G\) on levels of the tree. The connection between \(G\) and the groups generated by the orbit automata is used to find elements of infinite order in certain automaton groups for which other methods failed to work.

MSC:
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20M35 Semigroups in automata theory, linguistics, etc.
20E08 Groups acting on trees
68Q70 Algebraic theory of languages and automata
68Q45 Formal languages and automata
Software:
FR; AutomGrp; GAP
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Gluškov, V. M., Abstract theory of automata, Uspekhi Mat. Nauk, 16, 5(101), 3-62, (1961)
[2] Hořejš, J., Transformations defined by finite automata, Probl. Kibern., 9, 23-26, (1963)
[3] Alešin, S., Finite automata and the Burnside problem for periodic groups, Mat. Zametki, 11, 319-328, (1972)
[4] Merzlyakov, Y. I., Infinite finitely generated periodic groups, Dokl. Akad. Nauk SSSR, 268, 4, 803-805, (1983)
[5] Grigorčuk, R. I., On Burnside’s problem on periodic groups, Funktsional. Anal. i Prilozhen., 14, 1, 53-54, (1980)
[6] Grigorchuk, R. I., Degrees of growth of finitely generated groups and the theory of invariant means, Izv. Akad. Nauk SSSR Ser. Mat., 48, 5, 939-985, (1984)
[7] Milnor, J., Problem 5603, Amer. Math. Monthly, 75, 6, 685-686, (1968)
[8] Gupta, N.; Sidki, S., On the Burnside problem for periodic groups, Math. Z., 182, 3, 385-388, (1983) · Zbl 0513.20024
[9] Šunić, Z.; Ventura, E., The conjugacy problem in automaton groups is not solvable, J. Algebra, 364, 148-154, (2012) · Zbl 1261.20034
[10] Gillibert, P., The finiteness problem for automaton semigroups is undecidable, Internat. J. Algebra Comput., 24, 1, 1-9, (2014) · Zbl 1292.20040
[11] Belk, J.; Bleak, C., Some undecidability results for asynchronous transducers and the brin-Thompson group 2V, (2014), preprint
[12] Bondarenko, I. V.; Bondarenko, N. V.; Sidki, S. N.; Zapata, F. R., 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
[13] Bartholdi, L., FR - package “computations with functionally recursive groups”, (2014), Version 2.1.1, available at
[14] Muntyan, Y.; Savchuk, D., Automgrp - package for computations in self-similar groups and semigroups, (2014), Version 1.2.4, available at
[15] GAP - groups, algorithms, and programming, (2015), Version 4.7.8
[16] Klimann, I., The finiteness of a group generated by a 2-letter invertible-reversible mealy automaton is decidable, (Portier, N.; Wilke, T., 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, LIPIcs. Leibniz Int. Proc. Inform., vol. 20, (2013), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik Dagstuhl, Germany), 502-513 · Zbl 1354.68159
[17] Klimann, I.; Picantin, M.; Savchuk, D., A connected 3-state reversible mealy automaton cannot generate an infinite Burnside group, (Potapov, I., Developments in Language Theory, Lecture Notes in Comput. Sci., vol. 9168, (2015), Springer Berlin), 313-325, preprint · Zbl 1386.68106
[18] Godin, T.; Klimann, I.; Picantin, M., On torsion-free semigroups generated by invertible reversible mealy automata, (Dediu, A.-H.; Formenti, E.; Martín-Vide, C.; Truthe, B., Language and Automata Theory and Applications, Lecture Notes in Comput. Sci., vol. 8977, (2015), Springer International Publishing), 328-339 · Zbl 1405.68197
[19] Aleshin, S. V., A free group of finite automata, Vestnik Moskov. Univ. Ser. I Mat. Mekh., 4, 12-14, (1983) · Zbl 0513.68044
[20] Glasner, Y.; Mozes, S., Automata and square complexes, Geom. Dedicata, 111, 43-64, (2005) · Zbl 1088.20037
[21] Vorobets, M.; Vorobets, Y., On a free group of transformations defined by an automaton, Geom. Dedicata, 124, 237-249, (2007) · Zbl 1183.20024
[22] Vorobets, M.; Vorobets, Y., On a series of finite automata defining free transformation groups, Groups Geom. Dyn., 4, 2, 377-405, (2010) · Zbl 1227.20027
[23] Steinberg, B.; Vorobets, M.; Vorobets, Y., Automata over a binary alphabet generating free groups of even rank, Internat. J. Algebra Comput., 21, 1-2, 329-354, (2011) · Zbl 1239.20033
[24] Savchuk, D.; Vorobets, Y., Automata generating free products of groups of order 2, J. Algebra, 336, 1, 53-66, (2011) · Zbl 1239.20032
[25] D’Angeli, D.; Rodaro, E., Freeness of automata groups vs boundary dynamics, (2014), preprint
[26] Brunner, A. M.; Sidki, S., The generation of \(\operatorname{GL}(n, \mathbb{Z})\) by finite state automata, Internat. J. Algebra Comput., 8, 1, 127-139, (1998) · Zbl 0923.20023
[27] Caponi, L., On classification of groups generated by automata with 4 states over a 2-letter alphabet, (2014), University of South Florida, Department of Mathematics and Statistics Tampa, FL, USA, Master’s thesis
[28] Bondarenko, I.; Grigorchuk, R.; Kravchenko, R.; Muntyan, Y.; Nekrashevych, V.; Savchuk, D.; Šunić, Z., Classification of groups generated by 3-state automata over 2-letter alphabet, Algebra Discrete Math., 1, 1-163, (2008), available at · Zbl 1164.20004
[29] Nekrashevych, V., Self-similar groups, Math. Surveys Monogr., vol. 117, (2005), American Mathematical Society Providence, RI · Zbl 1087.20032
[30] Akhavi, A.; Klimann, I.; Lombardy, S.; Mairesse, J.; Picantin, M., On the finiteness problem for automaton (semi)groups, Internat. J. Algebra Comput., 22, 6, 1-26, (2012) · Zbl 1280.20038
[31] Gawron, P. W.; Nekrashevych, V. V.; Sushchansky, V. I., Conjugation in tree automorphism groups, Internat. J. Algebra Comput., 11, 5, 529-547, (2001) · Zbl 1030.20015
[32] Bondarenko, I. V.; Savchuk, D. M., On sushchansky p-groups, Algebra Discrete Math., 2, 22-42, (2007) · Zbl 1164.20012
[33] Steinberg, B., On some algorithmic properties of finite state automorphisms of rooted trees, (Algorithmic Problems in Group Theory, Their Complexity, and Applications to Cryptography, Contemp. Math., vol. 633, (2015), American Mathematical Society Providence, RI), 115-123 · Zbl 1326.20037
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.