The concept of self-similar automata over a changing alphabet and lamplighter groups generated by such automata. (English) Zbl 1291.68233
Summary: Generalizing the idea of self-similar groups defined by Mealy automata, we introduce the notion of a self-similar automaton and a self-similar group over a changing alphabet. We show that every finitely generated residually-finite group is self-similar over an arbitrary unbounded changing alphabet. We construct some naturally defined self-similar automaton representations over an unbounded changing alphabet for any lamplighter group \(K\wr\mathbb Z\) with an arbitrary finitely generated (finite or infinite) abelian group \(K\).
MSC:
| 68Q45 | Formal languages and automata |
| 20F05 | Generators, relations, and presentations of groups |
| 20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
| 68Q70 | Algebraic theory of languages and automata |
Keywords:
rooted tree; changing alphabet; time-varying automaton; group generated by an automaton; lamplighter groupReferences:
| [1] | Bondarenko, I.; Grigorchuk, R.; Kravchenko, R.; Muntyan, Y.; Nekrashevych, V.; Sunic, Z.; Savchuk, D., Groups generated by 3-state automata over a 2-letter alphabet II, J. Math. Sci., 156, 1, 187-208 (2009) · Zbl 1185.20029 |
| [2] | Erschler, A., Piecewise automatic groups, Duke Math. J., 134, 3, 591-613 (2006) · Zbl 1159.20019 |
| [3] | Erschler, A., Automatically presented groups, Groups Geom. Dyn., 47-59 (2007) · Zbl 1183.20040 |
| [4] | Grigorchuk, R., Solved and unsolved problems around one group, (Bartholdi, L.; Ceccherini-Silberstein, T.; Smirnova-Nagnibeda, T.; Żuk, A., Infinite Groups: Geometric, Combinatorial and Dynamical Aspects. Infinite Groups: Geometric, Combinatorial and Dynamical Aspects, Progress in Mathematics Series, vol. 248 (2005)), 413 p. · Zbl 1165.20021 |
| [5] | Grigorchuk, R.; Linnell, P.; Schick, T.; Żuk, A., On a question of Atiyah, C. R. Acad. Sci., Paris, Sr. I, Math., 331, 663-668 (2000) · Zbl 0969.57022 |
| [6] | Grigorchuk, R.; Nekrashevych, V.; Sushchanskii, V., Automata, dynamical systems and groups, Proceedings of Steklov Institute of Mathematics, 231, 128-203 (2000) · Zbl 1155.37311 |
| [7] | Grigorchuk, R.; Żuk, A., The Lamplighter group as a group generated by a 2-state automaton and its spectrum, Geom. Dedicata, 87, 209-244 (2001) · Zbl 0990.60049 |
| [8] | Kaloujnine, L., La structure des \(p\)-groupes de Sylow des groupes symetriques finis, Ann. Sci. Ecole Norm. Sup. (3), 65, 239-276 (1948) · Zbl 0034.30501 |
| [9] | Kambites, M.; Silva, P.; Steinberg, B., The spectra of lamplighter groups and Cayley machines, Geom. Dedicata, 120, 1, 193-227 (2006) · Zbl 1168.20012 |
| [10] | Mikolajczak, B., (Algebraic and Structural Automata Theory. Algebraic and Structural Automata Theory, translated from the Polish Annals of Discrete Mathematics, vol. 44 (1991), North-Holland Publishing Co.: North-Holland Publishing Co. Amsterdam) · Zbl 0717.68004 |
| [11] | Nekrashevych, V., (Self-Similar Groups. Self-Similar Groups, Mathematical Surveys and Monographs, vol. 117 (2005), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI) · Zbl 1087.20032 |
| [12] | Rozhkov, A. V., Theory of Aleshin type groups, Math. Notes, 40, 5, 827-836 (1986) · Zbl 0621.20018 |
| [13] | Rozhkov, A. V., Conditions for finiteness in Aleshin-type groups, Algebra and Logic, 29, 6, 467-479 (1990) · Zbl 0799.20035 |
| [14] | Rozhkov, A. V., Stabilizers of corteges in Aleshin-type groups, Math. Notes, 47, 3, 307-312 (1990) · Zbl 0709.20019 |
| [15] | Silva, P.; Steinberg, B., On a class of automata groups generalizing lamplighter groups, Internat. J. Algebra Comput., 15, 5-6, 1213-1234 (2005) · Zbl 1106.20028 |
| [16] | Sushchanskyy, V. I., Periodic permutation \(p\)-groups and the unrestricted Burnside problem, Soviet Math. Dokl., 20, 4, 766-770 (1979) · Zbl 0428.20023 |
| [17] | Sushchanskyy, V. I., Wreath products and periodic factorable groups, Math. USSR Sbornik, 67, 2, 535-553 (1990) · Zbl 0702.20019 |
| [18] | Sushchanskyy, V. I., Wreath products and factorable groups, St. Petersburg Math., 6, 1, 173-198 (1995) · Zbl 0824.20029 |
| [19] | Vorobets, M.; Vorobets, Ya., On a free group of transformations defined by an automaton, Geom. Dedicata, 124, 237-249 (2007) · Zbl 1183.20024 |
| [20] | Woryna, A., On permutation groups generated by time-varying Mealy automata, Publ. Math. Debrecen, 67, 1-2, 115-130 (2005) · Zbl 1081.20042 |
| [21] | Woryna, A., Representations of a free group of rank two by time-varying Mealy automata, Discuss. Math. Gen. Algebra Appl., 25, 1, 119-134 (2005) · Zbl 1105.20304 |
| [22] | Woryna, A., On generation of wreath products of cyclic groups by two state time varying Mealy automata, Internat. J. Algebra Comput., 16, 2, 397-415 (2006) · Zbl 1150.20012 |
| [23] | Woryna, A., The concept of duality for automata over a changing alphabet and generation a free group by such automata, Theoret. Comput. Sci., 412, 45, 6420-6431 (2011) · Zbl 1230.68139 |
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.
