Catalan fragile words

Document Type : Ischia Group Theory 2018


1 TUGraz

2 Università degli Studi Niccolò Cusano Dipartimento di Ingegneria Via Don Carlo Gnocchi, 3 00166 Roma, Italy

3 Dipartimento di Matematica, Politecnico di Milano, Milano, Italia


‎Fragile words have been already considered in the context of automata groups‎. ‎Here we focus our attention on a special class of strongly fragile words that we call Catalan fragile words‎. ‎Among other properties‎, ‎we show that there exists a one-to-one correspondence between the set of Catalan fragile words and the set of full binary trees‎.


Main Subjects

[1] S. V. Al¨eshin, A free group of finite automata, Mosc. Univ. Math. Bull., 38 (1983) 10–13.
[2] B. Bollob´as, Modern graph theory, Graduate Texts in Mathematics, 184, Springer-Verlag, New York, 1998.
[3] L. Bartholdi, R. Grigorchuk and V. Nekrashevych, From fractal groups to fractal sets, Fractals in Graz 2001,
Trends Math., Birkh¨auser Basel, (2003) 25–118.
[4] D. D’Angeli and E. Rodaro, Fragile words and Cayley type transducers, Int. J. Group Theory, 7 no. 3 (2018)
[5] S. Eilenberg, Automata, Languages and Machines, A, Pure and Applied Mathematics, 58, Academic Press [A
subsidiary of Harcourt Brace Jovanovich, Publishers], New York, 1974.
[6] R. Grigorchuk, V. Nekrashevych and V. Sushchanskii, Automata, dynamical systems and infinite groups, Proc.
Steklov Inst. Math., 231 (2000) 134–214.
[7] R. Grigorchuk, Some topics of dynamics of group actions on rooted trees, Proc. Steklov Inst. Math., 273 (2011)
[8] V. Nekrashevych, Self-similar groups, Mathematical Surveys and Monographs, 117, American Mathematical Society, Providence, RI, 2005.
[9] S. Roman, An introduction to Catalan numbers, Compact textbooks in Mathematics, Birkhauser, Basel, 2005.
[10] B. Steinberg, M. Vorobets and Y. Vorobets, Automata over a binary alphabet generating free groups of even rank,
Int. J. Algebra Comput., 21 (2011) 329–354.
[11] M. Vorobets and Y. Vorobets, On a free group of transformations defined by an automaton, Geom. Dedicata, 124
(2007) 237–249.
[12] M. Vorobets and Y. Vorobets, On a series of finite automata defining free transformation groups, Groups Geom.
Dyn., 4 (2010) 377–405.
Volume 9, Issue 2 - Serial Number 2
Proceedings of the Ischia Group Theory 2018- Part 2
June 2020
Pages 69-80
  • Receive Date: 03 October 2018
  • Revise Date: 05 March 2019
  • Accept Date: 07 March 2019
  • Published Online: 01 June 2020