Infinite periodic points of endomorphisms over special confluent rewriting systems

Cassaigne, Julien; Silva, Pedro V.

Annales de l'Institut Fourier, Tome 59 (2009) no. 2, pp. 769-810.

On considère les endomorphismes d’un monoïde défini par un système de réécriture spécial confluent qui admettent une extension continue à sa complétion donnée par les mots infinis réduits, et on étudie d’un point de vue dynamique la nature de leurs points périodiques infinis. Pour les endomorphismes préfixe-convergents et les endomorphismes expansifs, on détermine la structure de l’ensemble de tous les points périodiques infinis en termes de valeurs d’adhérence, on borne les périodes et on prouve que tous les points périodiques réguliers sont des attracteurs.

We consider endomorphisms of a monoid defined by a special confluent rewriting system that admit a continuous extension to the completion given by reduced infinite words, and study from a dynamical viewpoint the nature of their infinite periodic points. For prefix-convergent endomorphisms and expanding endomorphisms, we determine the structure of the set of all infinite periodic points in terms of adherence values, bound the periods and show that all regular periodic points are attractors.

[1] Allouche, J.-P.; Shallit, J. Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003 | MR | Zbl

[2] Benois, M.; LNCS Descendants of regular language in a class of rewriting systems: algorithm and complexity of an automata construction, Proceedings RTA 87, Volume 256, Springer-Verlag, Berlin (1987), pp. 121-132 | MR | Zbl

[3] Berstel, J. Transductions and Context-free Languages, Teubner, Stuttgart, 1979 | MR | Zbl

[4] Bestvina, M.; Feighn, M.; Handel, M. The Tits alternative for $Out\left(F_n\right)$, I: Dynamics of exponentially-growing automorphisms, Ann. Math., Volume 151 (2000), pp. 517-623 | DOI | MR | Zbl

[5] Bestvina, M.; Handel, M. Train tracks and automorphisms of free groups, Ann. Math., Volume 135 (1992), pp. 1-51 | DOI | MR | Zbl

[6] Book, R. V. Confluent and other types of Thue systems, J. Assoc. Comput. Mach., Volume 29 (1982), pp. 171-182 | MR | Zbl

[7] Book, R. V.; Otto, F. String-Rewriting Systems, Springer-Verlag, New York, 1993 | MR | Zbl

[8] Cassaigne, J.; Silva, P. V. Infinite words and confluent rewriting systems: endomorphism extensions (2005) (preprint)

[9] Dugundji, J. Topology, Allyn and Bacon, Boston, 1966 | MR | Zbl

[10] Gaboriau, D.; Jaeger, A.; Levitt, G.; Lustig, M. An index for counting fixed points of automorphisms of free groups, Duke Math. J., Volume 93 (1998), pp. 425-452 | DOI | MR | Zbl

[11] Ghys, E.; de la Harpe, P. Sur les groupes hyperboliques d’après Mikhael Gromov, Birkhäuser, Boston, 1990 | MR | Zbl

[12] Hilion, A. Dynamique des automorphismes du groupe libre, Université Paul Sabatier, Toulouse III (2004) (Thèse de Doctorat)

[13] Levitt, G.; Lustig, M. Periodic ends, growth rates, Hölder dynamics for automorphisms of free groups, Comment. Math. Helv., Volume 75 (2000), pp. 415-429 | DOI | MR | Zbl

[14] Levitt, G.; Lustig, M. Automorphisms of free groups have asymptotically periodic dynamics, J. Reine Angew. Math., Volume 619 (2008), pp. 1-36 | DOI | MR

[15] Lothaire, M. Combinatorics on Words, Addison-Wesley, Reading, 1983 | MR | Zbl

[16] Lothaire, M. Algebraic Combinatorics on Words, Cambridge University Press, Cambridge, 2002 | MR | Zbl

[17] Lyndon, R. C.; Schupp, P. E. Combinatorial Group Theory, Springer-Verlag, Berlin, 1977 | MR | Zbl

[18] Perrin, D.; Pin, J.-E. Infinite Words: Automata, Semigroups, Logic and Games, Pure and Applied Mathematics Series, Volume 141, Elsevier Academic Press, Amsterdam, 2004 | Zbl

[19] Sénizergues, G. On the rational subsets of the free group, Acta Informatica, Volume 33 (1996), pp. 281-296 | DOI | MR | Zbl

[20] Silva, P. V. Rational subsets of partially reversible monoids, Theoret. Comp. Sci. (to appear)

[21] Silva, P. V. Free group languages: rational versus recognizable, Theoret. Inform. Appl., Volume 38 (2004), pp. 49-67 | DOI | Numdam | MR | Zbl