Fixed points of endomorphisms of certain free products
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 1, pp. 165-179.

The fixed point submonoid of an endomorphism of a free product of a free monoid and cyclic groups is proved to be rational using automata-theoretic techniques. Maslakova's result on the computability of the fixed point subgroup of a free group automorphism is generalized to endomorphisms of free products of a free monoid and a free group which are automorphisms of the maximal subgroup.

DOI : 10.1051/ita/2011125
Classification : 20M05, 20F10
Mots clés : endomorphisms, fixed points, free products
@article{ITA_2012__46_1_165_0,
     author = {Silva, Pedro V.},
     title = {Fixed points of endomorphisms of certain free products},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {165--179},
     publisher = {EDP-Sciences},
     volume = {46},
     number = {1},
     year = {2012},
     doi = {10.1051/ita/2011125},
     mrnumber = {2904968},
     zbl = {1266.20069},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2011125/}
}
TY  - JOUR
AU  - Silva, Pedro V.
TI  - Fixed points of endomorphisms of certain free products
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2012
SP  - 165
EP  - 179
VL  - 46
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2011125/
DO  - 10.1051/ita/2011125
LA  - en
ID  - ITA_2012__46_1_165_0
ER  - 
%0 Journal Article
%A Silva, Pedro V.
%T Fixed points of endomorphisms of certain free products
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2012
%P 165-179
%V 46
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2011125/
%R 10.1051/ita/2011125
%G en
%F ITA_2012__46_1_165_0
Silva, Pedro V. Fixed points of endomorphisms of certain free products. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 1, pp. 165-179. doi : 10.1051/ita/2011125. http://www.numdam.org/articles/10.1051/ita/2011125/

[1] M. Benois, Descendants of regular language in a class of rewriting systems: algorithm and complexity of an automata construction, in Proc. of RTA 87. Lect. Notes Comput. Sci. 256 (1987) 121-132. | MR | Zbl

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

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

[4] O. Bogopolski, A. Martino, O. Maslakova and E. Ventura, The conjugacy problem is solvable in free-by-cyclic groups. Bull. Lond. Math. Soc. 38 (2006) 787-794. | MR | Zbl

[5] R.V. Book and F. Otto, String-Rewriting Systems. Springer-Verlag, New York (1993). | MR | Zbl

[6] J. Cassaigne and P.V. Silva, Infinite words and confluent rewriting systems: endomorphism extensions. Int. J. Algebra Comput. 19 (2009) 443-490. | MR | Zbl

[7] J. Cassaigne and P.V. Silva, Infinite periodic points of endomorphisms over special confluent rewriting systems. Ann. Inst. Fourier 59 (2009) 769-810. | Numdam | MR | Zbl

[8] D.J. Collins and E.C. Turner, Efficient representatives for automorphisms of free products. Mich. Math. J. 41 (1994) 443-464. | MR | Zbl

[9] D. Cooper, Automorphisms of free groups have finitely generated fixed point sets. J. Algebra 111 (1987) 453-456. | MR | Zbl

[10] S.M. Gersten, Fixed points of automorphisms of free groups. Adv. Math. 64 (1987) 51-85. | MR | Zbl

[11] R.Z. Goldstein and E.C. Turner, Monomorphisms of finitely generated free groups have finitely generated equalizers. Invent. Math. 82 (1985) 283-289. | MR | Zbl

[12] R.Z. Goldstein and E.C. Turner, Fixed subgroups of homomorphisms of free groups. Bull. Lond. Math. Soc. 18 (1986) 468-470. | MR | Zbl

[13] D. Hamm and J. Shallit, Characterization of finite and one-sided infinite fixed points of morphisms on free monoids. Technical Report CS-99-17 (1999).

[14] T. Head, Fixed languages and the adult languages of 0L schemes. Int. J. Comput. Math. 10 (1981) 103-107. | MR | Zbl

[15] S. Lyapin, Semigroups. Fizmatgiz. Moscow (1960). English translation by Am. Math. Soc. (1974). | Zbl

[16] O.S. Maslakova, The fixed point group of a free group automorphism. Algebra i Logika 42 (2003) 422-472. English translation in Algebra Logic 42 (2003) 237-265. | MR | Zbl

[17] M. Petrich and P.V. Silva, On directly infinite rings. Acta Math. Hung. 85 (1999) 153-165. | MR | Zbl

[18] J. Sakarovitch, Éléments de Théorie des Automates. Vuibert, Paris (2003). | Zbl

[19] P.V. Silva, Rational subsets of partially reversible monoids. Theoret. Comput. Sci. 409 (2008) 537-548. | MR | Zbl

[20] P.V. Silva, Fixed points of endomorphisms over special confluent rewriting systems. Monatsh. Math. 161 (2010) 417-447. | MR | Zbl

[21] M. Sykiotis, Fixed subgroups of endomorphisms of free products. J. Algebra 315 (2007) 274-278. | MR | Zbl

[22] E. Ventura, Fixed subgroups of free groups: a survey. Contemp. Math. 296 (2002) 231-255. | MR | Zbl

Cité par Sources :