Infinite periodic points of endomorphisms over special confluent rewriting systems
[Points périodiques infinis d’endomorphismes sur des systèmes de réécriture spéciaux confluents]
Cassaigne, Julien ; Silva, Pedro V.
Annales de l'Institut Fourier, Tome 59 (2009), p. 769-810 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2009-01-01
DOI : https://doi.org/10.5802/aif.2447
Classification:  68R15,  37B10,  20M35,  68Q70
Mots clés: points périodiques, endomorphismes, systèmes de réécriture, dynamique 
@article{AIF_2009__59_2_769_0,
     author = {Cassaigne, Julien and Silva, Pedro V.},
     title = {Infinite periodic points  of endomorphisms over special confluent rewriting systems},
     journal = {Annales de l'Institut Fourier},
     volume = {59},
     year = {2009},
     pages = {769-810},
     doi = {10.5802/aif.2447},
     zbl = {1166.68021},
     mrnumber = {2521435},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIF_2009__59_2_769_0}
}

Cassaigne, Julien; Silva, Pedro V. Infinite periodic points  of endomorphisms over special confluent rewriting systems. Annales de l'Institut Fourier, Tome 59 (2009) pp. 769-810. doi : 10.5802/aif.2447. http://gdmltest.u-ga.fr/item/AIF_2009__59_2_769_0/

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

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

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

[4] Bestvina, M.; Feighn, M.; Handel, M. The Tits alternative for Out(F n ), I: Dynamics of exponentially-growing automorphisms, Ann. Math., Tome 151 (2000), pp. 517-623 | Article | MR 1765705 | Zbl 0984.20025

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

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

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

[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 193606 | Zbl 0144.21501

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

[11] Ghys, E.; De La Harpe, P. Sur les groupes hyperboliques d’après Mikhael Gromov, Birkhäuser, Boston (1990) | MR 1086648 | Zbl 0731.20025

[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., Tome 75 (2000), pp. 415-429 | Article | MR 1793796 | Zbl 0965.20026

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

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

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

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

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

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

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

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