Automata, Dynamical Systems, and Groups

R. I. Grigorchuk ; V. V. Nekrashevych ; V. I. Sushchanskii

Informatics and Automation, Dynamical systems, automata, and infinite groups, Tome 231 (2000), pp. 134-214.

Résumé

This paper is devoted to the groups of finite automata and their applications in algebra, dynamical systems, and geometry. The groups of synchronous automata as well as the groups of asynchronous automata are considered. The problems of reduction of finite asynchronous automata, the types of growth of finite synchronous automata, and the conditions of embeddability of groups in the group of automata are studied. The automorphism groups of cellular automata are investigated. A group of rational homeomorphisms of the Cantor set is introduced. The dynamics, on the boundary of a tree, determined by an automaton group is investigated. Certain unsolved problems are formulated.

Bibliographie

[1] Adams S., “Trees and amenable equivalence relations”, Ergod. Th. and Dyn. Syst., 10 (1990), 1–14 | MR | Zbl

[2] Adams S., Spacier R., “Kazhdan groups, cocycles and trees”, Amer. J. Math., 112 (1990), 271–287 | DOI | MR | Zbl

[3] Alseda L., Misiurewicz M., Llibre J., Combinatorial dynamics and entropy in dimension one, Adv. Ser. Nonlin. Dyn., 5, World Sci., Singapore, 1993 | MR | Zbl

[4] Bartholdi L., Lower bounds of the growth of Grigorchuk's torsion group, Preprint Univ. Genève, 1999

[5] Bartholdi L., Croissance de groupes agissant sur des arbres, PhD Diss. Univ. Genève, 2000

[6] Bartholdi L., Grigorchuk R., On parabolic subgroups and Hecke algebras of some fractal groups, Preprint Forschungsinst. Math. ETH-Zürich, 1999 | MR | Zbl

[7] Bartholdi L., Grigorchuk R. I., “On the spectrum of Hecke type operators related to some fractal groups”, Din. Sist., Avtom. i Beskon. Gruppy, Tr. Mat. Inst. Steklova, 231, 2000, 5–45 | MR | Zbl

[8] Bruin H., Keller G., Pierre M. St., “Adding machines and wild attractors”, Ergod. Th. and Dyn. Syst., 17 (1997), 1267–1287 | DOI | MR | Zbl

[9] Bass H., Otero-Espinar M., Rockmore D. N., Tresser C. P. L., Cyclic renormalization and the automorphism groups of rooted trees, Springer, Berlin etc., 1995, Lect. Notes Math., v. 1621 | MR

[10] Brunner A. M., Sidki S., “The generation of $GL(n,\mathbf Z)$ by finite state automata”, Intern. J. Alg. and Comput., 8:1 (1998), 127–139 | DOI | MR | Zbl

[11] Buescu J., Exotic attractors (from Liapunov stability to riddled basins), Birkhäuser, Basel etc., 1997 | MR | Zbl

[12] Buescu J., Stewart I., “Liapunov stability and adding machines”, Ergod. Th. and Dyn. Syst., 15 (1995), 1–20 | MR

[13] Connes A., Feldman J., Weiss B., “An amenable equivalence relation is generated by a single transformation”, Ergod. Th. and Dyn. Syst., 1 (1981), 431–450 | MR | Zbl

[14] Cannon J. W., Floyd W. I., Parry W. R., “Introductory notes on Richard Thompson groups”, Enseign. math., 42:2 (1996), 25–256 | MR

[15] Dougherty R., Jackson S., Kechris A. S., “The structure of hyperfinite Borel equivalence relations”, Trans. Amer. Math. Soc., 341:1 (1994), 193–225 | DOI | MR | Zbl

[16] Dye H., “On groups of measure preserving transformations. I”, Amer. J. Math., 81 (1959), 119–159 | DOI | MR | Zbl

[17] Epstein D. B. A., Cannon J. W., Holt D. F., Levy S. V. F., Paterson M. S., Thurston W. P., Word processing and group theory, Jones and Bartlett, Boston, 1992 | MR | Zbl

[18] Eilenberg S., Automata, languages, and machines, v. A, Acad. Press, New York–London, 1974 | MR | Zbl

[19] Fabrykowski J., Gupta N., “On groups with sub-exponential growth functions. II”, J. Indian Math. Soc., 56:1–4 (1991), 217–228 | MR | Zbl

[20] Feldman J., Moore C., “Ergodic equivalence relations, cohomology and von Neumann algebras. I”, Trans. Amer. Math. Soc., 234 (1977), 289–324 | DOI | MR | Zbl

[21] Gaboriau D., “Sur la (co)homologie $L_2$ des actions préservant une mesure”, C. r. Acad. sci. Paris., Sér. 1: Math., 330:5m (2000), 365–370 | MR | Zbl

[22] Giordano T., Putnam I. F., Skau C. F., “Topological orbit equivalence and $C^*$-crossed products”, J. reine und angew. Math., 469 (1995), 51–111 | MR | Zbl

[23] Giordano T., Putnam I. F., Skau C. F., “Full groups of Cantor minimal systems”, Israel J. Math., 111 (1999), 285–320 | DOI | MR | Zbl

[24] Grigorchuk R., “Just infinite branch groups”, New horizons in pro-$p$ groups, Progr. Math., 184, eds. M. du Sautoy, D. Segal, A. Shalev, Birkhäuser, Boston etc., 2000, 121–179 | MR | Zbl

[25] Grigorchuk R. I., Linnel P., Schick T., Żuk A., “On a question of Atiyah”, C. R. Acad. Sci. Paris, Sér. I: Math., 331:9 (2000), 663–668 | MR | Zbl

[26] Gromov M., “Groups of polynomial growth and expanding maps”, Publ. Math. IHES, 53 (1981), 53–73 | MR

[27] Gupta N., Sidki S., “On the Burnside problem for periodic groups”, Math. Ztschr., 182 (1983), 385–388 | DOI | MR | Zbl

[28] Gupta N., Sidki S., “Some infinite $p$-groups”, Algebra i logika, 22:5 (1983), 584–589 | MR | Zbl

[29] Grigorchuk R., Żuk A., “On the asymptotic spectrum of random walks on infinite families of graphs”, Random walks and discrete potential theory, Proc. Conf. (Cortona, 22–28 June 1997), Sympos. math., 22, eds. M. Picardello, W. Woess, Cambridge Univ. Press, Cambridge, 1999, 134–150 | MR

[30] Grigorchuk R., Żuk A., The lamplighter group as a group generated by a 2-state automaton and its spectrum, preprint FIM ETH-Zürich, 1999, to appear in Geom. dedicata | MR

[31] de la Harpe P., Topics in geometric group theory, Univ. Chicago Press, Chicago, 2000 | MR

[32] Hjorth G., Kechris A. S., “Borel equivalence relations and classifications of countable models”, Ann. Pure and Appl. Logic., 82 (1996), 221–272 | DOI | MR | Zbl

[33] Hořejš J., “Preobrazovaniya, opredelennye konechnymi avtomatami”, Problemy kibernetiki, 9 (1963), 23–26

[34] Kaimanovich V. A., “Amenability, hyperfiniteness, and isoperimetric inequalities”, C. r. Acad. sci. Paris, Sér. 1: Math., 325 (1997), 999–1004 | MR | Zbl

[35] Kitchens B. P., Symbolic dynamics, Springer, Berlin etc., 1998 | MR | Zbl

[36] Kharlampovich O. G., Sapir M. V., “Algorithmic problems in varieties”, Intern. J. Alg. and Comput., 5:4 (1995), 379–602 | DOI | MR | Zbl

[37] Levitt G., “Homéomorphisme dynamiquement simples de l'ensemble de Cantor”, Enseign. math., 44:3–4 (1998), 279–289 | MR | Zbl

[38] Liardet P., Stambul P., “Algebraic computations with continued fractions”, J. Number Theory, 73:1 (1998), 92–121 | DOI | MR | Zbl

[39] Lind D., Marcus B., Symbolic dynamics and coding, Cambridge Univ. Press, Cambridge, 1995 | MR

[40] Lubotzky A., Mozes S., Zimmer R. J., “Superrigidity for the commensurability group of tree lattices”, Comment. math. helv., 69 (1994), 523–548 | DOI | MR | Zbl

[41] Lubotzky A., Discrete groups, expanding graphs and invariant measures, Progr. Math., 125, Birkhäuser, Boston etc., 1994 | MR | Zbl

[42] Macedońska O., Nekrashevych V., Sushchansky V., “Commensurators of groups and reversible automata”, Dopov. Nats. Akad. Nauk Ukr. Mat. Prirodozn. Tekh. Nauki, 2000, no. 12, 36–39 | MR | Zbl

[43] de Melo W., van Strien S., One-dimensional dynamics, Mod. Surv. Math., Springer, Berlin etc., 1993 | MR | Zbl

[44] Narkiewicz W., Polynomial mappings, Lect. Notes Math., 1600, Springer, Berlin etc., 1995 | MR | Zbl

[45] Nekrashevych V., Sidki S., “Automorphisms of the binary tree: state-closed subgroups and dynamics of 1/2-endomorphisms”, Groups: topological, combinatorial and arithmetic aspects, London Math. Soc. Lecture Note Ser., 311, Cambridge Univ. Press, Cambridge, 2004, 375–404 | MR | Zbl

[46] Nekrashevych V. V., Sushchansky V. I., “Some problems on groups of finitely automatic permutations”, Mat. stud., 13:1 (2000), 93–96 | MR

[47] Nekrashevych V., Sushchansky V., “On confinal dynamics of rooted tree automorphisms”, Computational and geometric aspects of modern algebra, LMS Lect. Note Ser., 275, eds. M. Atkinson, N. Gilbert, H. Howie, Cambridge Univ. Press, Cambridge, 2000, 229–246 | MR

[48] Nekrashevych V. V., Sushchansky V. I., “Automata with restricted memory and endomorphisms of a shift”, Dopov. Nats. Akad. Nauk Ukr. Mat. Prirodozn. Tekh. Nauki, 2001, no. 4, 18–21 | MR

[49] Olijnyk A., “Free products of $C_2$ as groups of finitely automatic permutations”, Vopr. algebry, 14 (1999), 158–165

[50] Ornstein D., Weiss B., “Ergodic theory of amenable group actions. I. The Rohlin lemma”, Bull. Amer. Math. Soc., 2 (1980), 161 | DOI | MR | Zbl

[51] Paulin F., “Propriétés asymptotiques des relations d'équivalences mesurées discrètes”, Markov Process. Related Fields, 5:2 (1999), 163–200 | MR | Zbl

[52] Plotkin B. I., Greenglaz L. Ja., Gvaramija A. A., Algebraic structures in automata and databases theory, World Sci., Singapore–New Gercey–London–Hong Kong, 1992 | MR | Zbl

[53] Pride S. J., “The concept of “largness” in group theory”, Word problems II, Stud. Logic and Found. Math., 95, eds. S. I. Adian, W. W. Boone, G. Higman, North-Holland, Amsterdam, 1980, 299–335 | MR

[54] Rhodes J., “Monoids acting on trees”, Intern. J. Alg. and Comput., 1 (1991), 253–279 | DOI | MR | Zbl

[55] Rhodes J., “Undecidability, automata, and pseudovarities of finite semigroups”, Intern. J. Alg. and Comput., 9:4 (1999), 455–473 | DOI | MR | Zbl

[56] Röver C. E., “Constructing finitely presented simple groups that contain Grigorchuk groups”, J. Algebra, 220 (1999), 284–313 | DOI | MR | Zbl

[57] Ribes L., Zalesskiĭ P., “Pro-$p$ trees and applications”, New horizons in pro-$p$ groups, eds. M. du Sautoy, D. Segal, A. Shalev, Birkhäuser, Boston etc., 2000, 75–119, Progr. Math., v. 184 | MR | Zbl

[58] Sidki S., Regular trees and their automorphisms, IMPA, Rio de Janeiro, 1998, Monogr. mat., v. 56 | MR | Zbl

[59] Sidki S., “Automorphisms of one-rooted trees: growth, circuit structure and acyclicity”, J. Math. Sci., 100:1 (2000), 1925–1943 | DOI | MR | Zbl

[60] Sushchansky V. I., Moćko E., “Cycles of distance-decreasing mappings in the ring of $n$-adic integers”, Colloq. Math., 105:2 (2006), 197–205 | DOI | MR

[61] Streich W. J., Rösner Th., Theorie linearer Automaten, VEB Dtsch. Verl. Wissensch., Berlin, 1978, Studienbücherei | MR | Zbl

[62] Thompson R. J., “Embeddings into finitely generated simple groups which preserve the word problem”, Word problems, v. II, Stud. Logic and Found. Math., 95, eds. S. I. Adian, W. W. Boone, G. Higman, North-Holland, Amsterdam, 1980, 401–441 | MR

[63] Aleshin S. V., “Konechnye avtomaty i problema Bernsaida o periodicheskikh gruppakh”, Mat. zametki, 11:3 (1972), 319–328 | MR | Zbl

[64] Aleshin S. V., “Svobodnaya gruppa konechnykh avtomatov”, Vestn. MGU. Matematika. Mekhanika, 1983, no. 4, 12–16 | MR

[65] M. A. Arbib (red.), Algebraicheskaya teoriya avtomatov, yazykov i polugrupp, Statistika, M., 1975 | MR | Zbl

[66] Bezuschak O. O., Suschanskii V. I., “Sopryazhennost v gruppakh izometrii berovskikh metrik”, Ukr. mat. zhurn., 43:9 (1991), 1148–1155 | MR

[67] Gavron P., Hekrashevich V. V., Suschanskii V. I., “Klassy sopryazhennosti gruppy avtomorfizmov dereva”, Mat. zametki, 65:6 (1999), 938–941 | MR

[68] Glebskii Yu. V., “Kodirovanie s pomoschyu konechnykh avtomatov”, DAN SSSR, 141:5 (1961), 1054–1057 | MR

[69] Glushkov V. M., “Abstraktnaya teoriya avtomatov”, UMN, 16:5 (1961), 3–62 | MR

[70] Golod E. S., “O nil-algebrakh i finitno approksimiruemykh gruppakh”, Izv. AN SSSR. Ser. mat., 28:2 (1964), 273–276 | MR | Zbl

[71] Grigorchuk R. I., “K probleme Bernsaida o periodicheskikh gruppakh”, Funkts. analiz i ego pril., 14:1 (1980), 53–54 | MR | Zbl

[72] Grigorchuk R. I., “Stepeni rosta konechno porozhdennykh grupp i teoriya invariantnykh srednikh”, Izv. AH SSSR. Ser. mat., 48:5 (1984), 939–985 | MR

[73] Grigorchuk R. I., “O periodicheskikh gruppakh, porozhdennykh konechnymi avtomatami”, 18-ya Vsesoyuznaya algebraicheskaya konferentsiya, Tez. dokl. i soobsch., Kishinev, 1985

[74] Grigorchuk R. I., “O polugruppakh s sokrascheniyami stepennogo rosta”, Mat. zametki, 43:3 (1988), 305–319 | MR

[75] Grigorchuk R. I., “O ryade Gilberta–Puankare graduirovannykh algebr, assotsiirovannykh s gruppami”, Mat. sb., 180:2 (1989), 207–225 | MR

[76] Kudryavtsev V. M., Aleshin S. V., Podkolzin A. S., Vvedenie v teoriyu avtomatov, Nauka, M., 1985 | MR

[77] Levenshtein V. I., “Ob obraschenii konechnykh avtomatov”, DAN SSSR, 147:6 (1962), 1300–1303 | MR

[78] Levenshtein V. I., “O nekotorykh svoistvakh kodirovaniya i samonastraivayuschikhsya avtomatakh dlya dekodirovaniya soobschenii”, Problemy kibernetiki, 11, 1964, 63–121

[79] Leonov Yu. G., Nizhnyaya otsenka rosta gruppy Grigorchuka, Preprint, Odessa, 1999

[80] Maltsev A. I., “Nilpotentnye polugruppy”, Uchen. zap. Ivanov. ped. in-ta, 4 (1953), 107–111

[81] Merzlyakov Yu. I., “O beskonechnykh konechno porozhdennykh periodicheskikh gruppakh”, DAN SSSR, 268:4 (1983), 803–805 | MR | Zbl

[82] Oliinyk A., “Svobodnye gruppy avtomatnykh podstanovok”, Dop. NAN Ukr., 1998, no. 7, 40–44 | MR

[83] Oliinik A., “Vilni abelevi grupi skinchennikh avtomativ”, Visn. Kiïv. univ. Fiz.-mat. nauki, 1999, no. 1, 74–77 | MR

[84] Oliinyk A. S., Suschanskii V. I., “Svobodnaya gruppa beskonechnykh unitreugolnykh matrits”, Mat. zametki, 67:3 (2000), 382–386 | MR | Zbl

[85] Rozhkov A. V., Usloviya konechnosti v gruppakh avtomorfizmov derevev, Dokt. dis., Chelyabinsk, 1996

[86] Suschanskii V. I., “Periodicheskie $p$-gruppy podstanovok i neogranichennaya problema Bernsaida”, DAH SSSR, 247:3 (1979), 557–561 | MR

[87] Suschanskii V.I., “Spleteniya i periodicheskie faktoriziruemye gruppy”, Mat. sb., 180:8 (1989), 1073–1091 | MR | Zbl

[88] Suschanskii V. I., “Spleteniya i faktorizuemye gruppy”, Algebra i analiz, 6:1 (1994), 203–238 | MR | Zbl

[89] Suschanskii V. I., “Grupi avtomatnikh pidstanovok”, Dop. NAN Ukr., 1998, no. 6, 47–51

[90] Suschanskii V. I., “Grupi skinchenno avtomatnikh pidstanovok”, Dop. NAN Ukr., 1999, no. 2, 29–32

[91] Sharkovskii A., “Sosuschestvovanie tsiklov nepreryvnykh otobrazhenii pryamoi v sebya”, Ukr. mat. zhurn., 16 (1964), 61–71