×

Conjugacy and episturmian morphisms. (English) Zbl 1044.68142

Summary: Episturmian morphisms generalize Sturmian morphisms. Here, we study some intrinsic properties of these morphisms: invertibility, presentation, cancellativity, unitarity, characterization by conjugacy. Most of them are generalizations of known properties of Sturmian morphisms. But we present also some results on episturmian morphisms that have not already been stated in the particular case of Sturmian morphisms: characterization of the episturmian morphisms that preserve palindromes, new algorithms to compute conjugates.
We also study the conjugation of morphisms in the general case and show that the monoid of invertible morphisms on an alphabet containing at least three letters is not finitely generated.

MSC:

68R15 Combinatorics on words
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Arnoux, P.; Rauzy, G., Représentation géométrique de suites de complexité 2n+1, Bull. soc. math. France, 119, 199-215, (1991) · Zbl 0789.28011
[2] Berstel, J.; Séébold, P., Sturmian words, (), 45-110 · Zbl 0883.68104
[3] Berthé, V.; Vuillon, L., Tilings and rotations on the torusa two-dimensional generalization of Sturmian sequences, Discrete math., 223, 27-53, (2000) · Zbl 0970.68124
[4] Castelli, M.G.; Mignosi, F.; Restivo, A., Fine and Wilf’s theorem for three periods and a generalization of Sturmian words, Theoret. comput. sci., 218, 83-94, (1999) · Zbl 0916.68114
[5] C. Choffrut, J. Karhumäki, Handbook of Formal Languages, Vol. 1, Chap. 6, Combinatorics of Words, Springer, Berlin, 1997, pp. 329-438.
[6] Coxeter, H.S.M.; Moser, W.O.J., Generators and relations for discrete groups, (1965), Springer Berlin · Zbl 0133.28002
[7] Crochemore, M.; Rytter, W., Text algorithms, (1994), Oxford University Press Oxford · Zbl 0844.68101
[8] Droubay, X.; Justin, J.; Pirillo, G., Episturmian words and some constructions of de luca and Rauzy, Theoret. comput. sci., 255, 1-2, 539-553, (2001) · Zbl 0981.68126
[9] Hubert, P., Suites équilibrées, Theoret. comput. sci., 242, 91-108, (2000) · Zbl 0944.68149
[10] Justin, J., On a paper by castelli, mignosi and restivo, RAIRO theoret. inform. appl., 34, 373-377, (2000) · Zbl 0987.68056
[11] Justin, J., Episturmian words and morphisms (results and conjectures), (), 533-539 · Zbl 0971.68125
[12] Justin, J.; Pirillo, G., Episturmian words and Episturmian morphisms, Theoret. comput. sci., 276, 1-2, 281-313, (2002) · Zbl 1002.68116
[13] Justin, J.; Vuillon, L., Return words in sturmian and Episturmian words, RAIRO theoret. inform. appl., 34, 343-356, (2000) · Zbl 0987.68055
[14] M. Lothaire, Combinatorics on Words, Vol. 17 of Encyclopedia of Mathematics and Applications, Addison-Wesley, Reading, MA, 1983; Reprinted in the Cambridge Mathematical Library, Cambridge Univ. Press, Cambridge, UK, 1997.
[15] Morse, M.; Hedlund, G.A., Symbolic dynamics Iisturmian trajectories, Amer. J. math., 61, 1-42, (1940) · JFM 66.0188.03
[16] G. Rauzy, Suites à termes dans un alphabet fini, Séminaire de Théorie des nombres de Bordeaux, exposé 25, 1983. · Zbl 0547.10048
[17] Séébold, P., Fibonacci morphisms and Sturmian words, Theoret. comput. sci., 88, 365-384, (1991) · Zbl 0737.68068
[18] Séébold, P., On the conjugation of standard morphisms, Theoret. comput. sci., 195, 91-109, (1998) · Zbl 0981.68104
[19] Wen, Z.-X.; Wen, Z.-Y., Local isomorphisms of invertible substitutions, C. R. acad. sci. Paris Série I, 318, 299-304, (1994) · Zbl 0812.11018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.