Fragile words and Cayley type transducers

Document Type : Ischia Group Theory 2016

Authors

1 TUGraz

2 Dipartimento di Matematica, Politecnico di Milano, Milano, Italia

Abstract

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.

Keywords

Main Subjects

References

[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.
[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 in Journal of Fractal Geometry.
[3] D. D’Angeli, A. Donno, M. Matter and T. Nagnibeda, Schreier graphs of the Basilica group, J. Mod. Dyn., 4 (2010) 167–205.
[4] D. D’Angeli and E. Rodaro, Groups and semigroups defined by colorings of synchronizing automata, Internat. J. Algebra Comput., 24 (2014) 773–793.
[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.
[6] D. D’Angeli and E. Rodaro, Freeness of automata groups vs boundary dynamics, Journal of Algebra, 462 (2016) 115–136.
[7] D. D’Angeli, E. Rodaro and J. P. Wächter, On the complexity of the word problem for automaton semigroups and automaton groups, Advances in Applied Mathematics, 90 (2017) 160–187.
[8] P. de la Harpe, Topics in geometric group theory, University of Chicago Press, 2000.
[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.
[11] Y. Muntyan and D. Savchuk, Automgrp-gap package for computations in self-similar groups and semigroups, 2008.
[12] V. Nekrashevych, Self-similar groups, Mathematical Surveys and Monographs, American Mathematical Society, Providence, RI, 117 2005.
[13] V. Nekrashevych, Free subgroups in groups acting on rooted trees, Groups Geom. Dyn., 4 (2010) 847–862.
[14] S. Sidki, Automorphisms of one-rooted trees: growth, circuit structure, and acyclicity, J. Math. Sci., 100 (2000) 1925–1943.
[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.
[16] A. M. Vershik, Totally nonfree actions and the infinite symmetric group, Mosc. Math. J., 12 (2012) 193–212.
[17] M. Vorobets and Y. Vorobets, On a free group of transformations defined by an automaton, Geom. Dedicata, 124 (2007) 237–249.
[18] M. Vorobets and Y. Vorobets , On a series of finite automata defining free transformation groups, Groups Geom. Dyn., 4 (2010) 377–405.
International Journal of Group Theory
Volume 7, Issue 3 - Serial Number 3
Proceedings of the Ischia Group Theory 2016-Part III
September 2018
Pages 95-109

Files

Cited by

History

  • Receive Date: 23 November 2016
  • Revise Date: 05 September 2017
  • Accept Date: 26 September 2017
  • Published Online: 01 September 2018

Share

How to cite

Statistics