zbMATH — the first resource for mathematics

Fragile words and Cayley type transducers. (English) Zbl 1446.20043
Summary: We address the problem of finding examples of non-bireversible transducers defining free groups, we show examples of transducers with sink accessible from every state which generate free groups, and, in general, we link this problem to the non-existence of certain words with interesting combinatorial and geometrical properties that we call fragile words. By using this notion, we exhibit a series of transducers constructed from Cayley graphs of finite groups whose defined semigroups are free, and thus having exponential growth.
20E08 Groups acting on trees
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
68Q45 Formal languages and automata
Full Text: DOI
[1] L. Bartholdi, R. I. Grigorchuk and V. Nekrashevych,From fractal groups to fractal sets, In Peter Grabner and Wolfgang Woess, editors, Fractals in Graz 2001, Trends Math., Birkhuser, Basel, 2003 25-118. · Zbl 1037.20040
[2] I. Bondarenko, D. D’Angeli and T. Nagnibeda, Ends of Schreier graphs and cut-points of limit spaces of self-similar groups, To appear inJournal of Fractal Geometry. · Zbl 1423.20041
[3] D. D’Angeli, A. Donno, M. Matter and T. Nagnibeda, Schreier graphs of the Basilica group,J. Mod. Dyn.,4(2010) 167-205. · Zbl 1239.20031
[4] D. D’Angeli and E. Rodaro, Groups and semigroups defined by colorings of synchronizing automata,Internat. J. Algebra Comput.,24(2014) 773-793. · Zbl 1314.20028
[5] D. D’Angeli and E. Rodaro, A geometric approach to (semi)-groups defined by automata via dual transducers, Geom. Dedicata,174(2015) 375-400. · Zbl 1322.20049
[6] D. D’Angeli and E. Rodaro, Freeness of automata groups vs boundary dynamics,Journal of Algebra,462(2016) 115-136. · Zbl 1454.20069
[7] D. D’Angeli, E. Rodaro and J. P. W¨achter, On the complexity of the word problem for automaton semigroups and automaton groups,Advances in Applied Mathematics,90(2017) 160-187. · Zbl 1393.20014
[8] P. de la Harpe,Topics in geometric group theory, University of Chicago Press, 2000. · Zbl 0965.20025
[9] R. I. Grigorchuk, Some topics of dynamics of group actions on rooted trees,Proc. Steklov Inst. Math.,273(2011) 1-118.
[10] R. I. Grigorchuk and D. Savchuk, Self-similar groups acting essentially freely on the boundary of the binary rooted tree,Contemp. Math.,611(2014) 9-48. · Zbl 1308.20025
[11] Y. Muntyan and D. Savchuk, Automgrp-gap package for computations in self-similar groups and semigroups, 2008, version
[12] V. Nekrashevych, Self-similar groups, Mathematical Surveys and Monographs,American Mathematical Society, Providence, RI,1172005. · Zbl 1087.20032
[13] V. Nekrashevych, Free subgroups in groups acting on rooted trees,Groups Geom. Dyn.,4(2010) 847-862. · Zbl 1267.37009
[14] S. Sidki, Automorphisms of one-rooted trees: growth, circuit structure, and acyclicity,J. Math. Sci.,100(2000) 1925-1943. · Zbl 1069.20504
[15] B. Steinberg, M. Vorobets and Y. Vorobets, Automata over a binary alphabet generating free groups of even rank, Internat. J. Algebra Comput.,21(2011) 329-354. · Zbl 1239.20033
[16] A. M. Vershik, Totally nonfree actions and the infinite symmetric group,Mosc. Math. J.,12(2012) 193-212. · Zbl 1294.37004
[17] M. Vorobets and Y. Vorobets, On a free group of transformations defined by an automaton,Geom. Dedicata,124 (2007) 237-249. · Zbl 1183.20024
[18] M. Vorobets and Y. Vorobets,
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.