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.
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita/2011125/
[1] 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] Transductions and Context-free Languages. Teubner, Stuttgart (1979). | MR | Zbl
,[3] Train tracks and automorphisms of free groups. Ann. Math. 135 (1992) 1-51. | MR | Zbl
and ,[4] The conjugacy problem is solvable in free-by-cyclic groups. Bull. Lond. Math. Soc. 38 (2006) 787-794. | MR | Zbl
, , and ,[5] String-Rewriting Systems. Springer-Verlag, New York (1993). | MR | Zbl
and ,[6] Infinite words and confluent rewriting systems: endomorphism extensions. Int. J. Algebra Comput. 19 (2009) 443-490. | MR | Zbl
and ,[7] Infinite periodic points of endomorphisms over special confluent rewriting systems. Ann. Inst. Fourier 59 (2009) 769-810. | Numdam | MR | Zbl
and ,[8] Efficient representatives for automorphisms of free products. Mich. Math. J. 41 (1994) 443-464. | MR | Zbl
and ,[9] Automorphisms of free groups have finitely generated fixed point sets. J. Algebra 111 (1987) 453-456. | MR | Zbl
,[10] Fixed points of automorphisms of free groups. Adv. Math. 64 (1987) 51-85. | MR | Zbl
,[11] Monomorphisms of finitely generated free groups have finitely generated equalizers. Invent. Math. 82 (1985) 283-289. | MR | Zbl
and ,[12] Fixed subgroups of homomorphisms of free groups. Bull. Lond. Math. Soc. 18 (1986) 468-470. | MR | Zbl
and ,[13] Characterization of finite and one-sided infinite fixed points of morphisms on free monoids. Technical Report CS-99-17 (1999).
and ,[14] Fixed languages and the adult languages of 0L schemes. Int. J. Comput. Math. 10 (1981) 103-107. | MR | Zbl
,[15] Semigroups. Fizmatgiz. Moscow (1960). English translation by Am. Math. Soc. (1974). | Zbl
,[16] 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] On directly infinite rings. Acta Math. Hung. 85 (1999) 153-165. | MR | Zbl
and ,[18] Éléments de Théorie des Automates. Vuibert, Paris (2003). | Zbl
,[19] Rational subsets of partially reversible monoids. Theoret. Comput. Sci. 409 (2008) 537-548. | MR | Zbl
,[20] Fixed points of endomorphisms over special confluent rewriting systems. Monatsh. Math. 161 (2010) 417-447. | MR | Zbl
,[21] Fixed subgroups of endomorphisms of free products. J. Algebra 315 (2007) 274-278. | MR | Zbl
,[22] Fixed subgroups of free groups: a survey. Contemp. Math. 296 (2002) 231-255. | MR | Zbl
,Cité par Sources :