Abstract
This paper studies obstructions to preservation of return sets by episturmian morphisms. We show, by way of an explicit construction, that infinitely many obstructions exist. This generalizes and improves an earlier result about Sturmian morphisms.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data Availability
No datasets were generated or analysed during the current study.
References
Almeida, J., Costa, A.: Presentations of Schützenberger groups of minimal subshifts. Israel J. Math. 196(1), 1–31 (2013). https://doi.org/10.1007/s11856-012-0139-4
Almeida, J., Costa, A.: A geometric interpretation of the Schützenberger group of a minimal subshift. Ark. Math. 54(2), 243–275 (2016). https://doi.org/10.1007/s11512-016-0233-7
Arnoux, P., Rauzy, G.: Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. Fr. 119(2), 199–215 (1991). https://doi.org/10.24033/bsmf.2164
Berthé, V., Goulet-Ouellet, H.: On substitutions preserving their return sets. In: Frid, A., Mercas, R. (eds.) Combinatorics on words, WORDS 2023, volume 13899 of Lecture Notes in Computer Science, pp. 77–90 (2023). https://doi.org/10.1007/978-3-031-33180-0_6
Berthé, V., De Felice, C., Dolce, F., Leroy, J., Perrin, D., Reutenauer, C., Rindone, G.: Acyclic, connected and tree sets. Monatsh. Math. 176(4), 521–550 (2015). https://doi.org/10.1007/s00605-014-0721-4
Cassaigne, J., Chekhova, N.: Fonctions de récurrence des suites d’Arnoux-Rauzy et réponse à une question de Morse et Hedlund. Ann. Inst. Fourier 56(7), 2249–2270 (2006). https://doi.org/10.5802/aif.2239
Castelli, M., Mignosi, F., Restivo, A.: Fine and Wilf’s theorem for three periods and a generalization of Sturmian words. Theoret. Comput. Sci. 218(1), 83–94 (1999). https://doi.org/10.1016/s0304-3975(98)00251-5
de Luca, A.: Sturmian words: structure, combinatorics, and their arithmetics. Theoret. Comput. Sci. 183(1), 45–82 (1997). https://doi.org/10.1016/s0304-3975(96)00310-6
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). https://doi.org/10.1016/s0304-3975(99)00320-5
Durand, F.: A characterization of substitutive sequences using return words. Discrete Math. 179(1–3), 89–101 (1998). https://doi.org/10.1016/S0012-365X(97)00029-0
Durand, F., Perrin, D.: Dimension Groups and Dynamical Systems. Cambridge Studies in Advanced Mathematics. Cambridge University Press (2022). https://doi.org/10.1017/9781108976039
Fogg, N.P.: Substitutions in Dynamics, Arithmetics and Combinatorics. Springer Berlin Heidelberg (2002). https://doi.org/10.1007/b13861. Edited by Berthé, V., Ferenczi, S., Mauduit, C., Siegel, A.
Glen, A., Justin, J.: Episturmian words: A survey. RAIRO Theor. Inform. Appl. 43(3), 403–442 (2009). https://doi.org/10.1051/ita/2009003
Glen, A., Levé, F., Richomme, G.: Directive words of episturmian words: equivalences and normalization. RAIRO Theor. Inform. Appl. 43(2), 299–319 (2009). https://doi.org/10.1051/ita:2008029
Goulet-Ouellet, H.: Suffix-connected languages. Theoret. Comput. Sci. 923, 126–143 (2022). https://doi.org/10.1016/j.tcs.2022.05.001
Justin, J.: On a paper by Castelli, Mignosi, Restivo. RAIRO Theor. Inform. Appl. 34(5), 373–377 (2000). https://doi.org/10.1051/ita:2000122
Justin, J.: Episturmian morphisms and a Galois theorem on continued fractions. RAIRO Theor. Inform. Appl. 39(1), 207–215 (2005). https://doi.org/10.1051/ita:2005012
Justin, J., Pirillo, G.: Episturmian words and episturmian morphisms. Theoret. Comput. Sci. 276(1–2), 281–313 (2002). https://doi.org/10.1016/s0304-3975(01)00207-9
Justin, J., Vuillon, L.: Return words in Sturmian and episturmian words. RAIRO Theor. Inform. Appl. 34(5), 343–356 (2000). https://doi.org/10.1051/ita:2000121
Lothaire, M.: Algebraic combinatorics on words. Cambridge University Press (2002)
Perrin, D., Reutenauer, C.: The palindromization map. Discrete Appl. Math. 340, 202–214 (2023). https://doi.org/10.1016/j.dam.2023.07.008
Queffélec, M.: Substitution Dynamical Systems: Spectral Analysis. Springer Berlin Heidelberg (2010). https://doi.org/10.1007/978-3-642-11212-6
Rauzy, G.: Nombres algébriques et substitutions. Bull. Soc. Math. Fr. 79, 147–178 (1982). https://doi.org/10.24033/bsmf.1957
Richomme, G.: Conjugacy and episturmian morphisms. Theoret. Comput. Sci. 302(1–3), 1–34 (2003). https://doi.org/10.1016/s0304-3975(02)00726-0
Richomme, G.: Some algorithms to compute the conjugates of episturmian morphisms. RAIRO Theor. Inform. Appl. 37(1), 85–104 (2003). https://doi.org/10.1051/ita:2003009
Séébold, P.: On the conjugation of standard morphisms. Theoret. Comput. Sci. 195(1), 91–109 (1998). https://doi.org/10.1016/s0304-3975(97)00159-x
Acknowledgements
The authors warmly thank the referees who helped us to improve the previous version of this paper.
Author information
Authors and Affiliations
Contributions
Both authors have contributed to this paper.
Corresponding author
Ethics declarations
Competing interests
The authors declare no competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work was supported by the Agence Nationale de la Recherche through the project SymDynAr (ANR-23-CE40-0024-01). The second author was supported by the CTU Global Postdoc Fellowship program.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Berthé, V., Goulet-Ouellet, H. Obstructions to Return Preservation for Episturmian Morphisms. Theory Comput Syst (2024). https://doi.org/10.1007/s00224-024-10190-y
Accepted:
Published:
DOI: https://doi.org/10.1007/s00224-024-10190-y