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 : https://doi.org/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},
zbl = {1266.20069},
mrnumber = {2904968},
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
DA  - 2012///
SP  - 165
EP  - 179
VL  - 46
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2011125/
UR  - https://zbmath.org/?q=an%3A1266.20069
UR  - https://www.ams.org/mathscinet-getitem?mr=2904968
UR  - https://doi.org/10.1051/ita/2011125
DO  - 10.1051/ita/2011125
LA  - en
ID  - ITA_2012__46_1_165_0
ER  - 
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 903667 | Zbl 0643.68119

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

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

[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 2268363 | Zbl 1116.20027

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

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

[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 2521435 | Zbl 1166.68021

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

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

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

[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 809716 | Zbl 0582.20023

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

[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 645626 | Zbl 0472.68034

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

[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 2017513 | Zbl 1031.20014

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

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

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

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

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

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

Cité par Sources :