Stability properties for subgroups generated by return words

Discrete Mathematics and Combinatorics; Computer Science - Discrete Mathematics; Mathematics - Combinatorics; Mathematics - Dynamical Systems; Mathematics - Group Theory

Abstract :

[en] Return words are a classical tool for studying shift spaces with low factor complexity. In recent years, their projection inside groups have attracted some attention, for instance in the context of dendric shift spaces, of generation of pseudorandom numbers (through the welldoc property), and of profinite invariants of shift spaces. Aiming at unifying disparate works, we introduce a notion of stability for subgroups generated by return words. Within this framework, we revisit several existing results and generalize some of them. We also study general aspects of stability, such as decidability or closure under certain operations.

Disciplines :

Mathematics

Author, co-author :

Gheeraert, France ; Université de Liège - ULiège > Mathematics ; LAMFA, Université de Picardie Jules Verne, Amiens, France

Goulet-Ouellet, Herman; Université de Moncton, Moncton, Canada

Leroy, Julien ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Stas, Pierre ; Université de Liège - ULiège > Mathematics

Language :

English

Title :

Stability properties for subgroups generated by return words

Publication date :

December 2025

Journal title :

European Journal of Combinatorics

ISSN :

0195-6698

eISSN :

1095-9971

Publisher :

Academic Press

Volume :

130

Pages :

104224

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://api.elsevier.com/content/article/PII:S0195669825001131?httpAccept=text/xml

Funding text :

The second author was supported by the CTU Global Postdoc Fellowship program.

Available on ORBi :

since 15 June 2026

Statistics

Number of views

10 (2 by ULiège)

Number of downloads

19 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenAlex citations

Bibliography

Allenby, R.B.J.T., Gregorac, R.J., On locally extended residually finite groups. Gatterdam, R.W., Weston, K.W., (eds.) Conference on Group Theory, 1973, Springer Berlin Heidelberg, Berlin, Heidelberg, 9–17.
Almeida, J., Costa, A., Kyriakoglou, R., Perrin, D., Profinite Semigroups and Symbolic Dynamics. 2020, Springer International Publishing.
Balková, Ľ., Bucci, M., De Luca, A., Hladký, J., Puzynina, S., Aperiodic pseudorandom number generators based on infinite words. Theoret. Comput. Sci. 647 (2016), 85–100.
Balková, Ľ., Pelantová, E., Steiner, W., Sequences with constant number of return words. Monatsh. Math. 155:3–4 (2008), 251–263.
Berstel, J., Felice, C.D., Perrin, D., Reutenauer, C., Rindone, G., Bifix codes and Sturmian words. J. Algebra 369 (2012), 146–202.
Berthé, V., De Felice, C., Dolce, F., Leroy, J., Perrin, D., Reutenauer, C., Rindone, G., Acyclic, connected and tree sets. Monatsh. Math. 176:4 (2015), 521–550.
Berthé, V., De Felice, C., Dolce, F., Leroy, J., Perrin, D., Reutenauer, C., Rindone, G., Maximal bifix decoding. Discrete Math. 338:5 (2015), 725–742.
Berthé, V., Goulet-Ouellet, H., On substitutions preserving their return sets. Frid, A., Mercaş, R., (eds.) Combinatorics on Words, 2023, Springer Nature Switzerland, Cham, 77–90.
Berthé, V., Goulet-Ouellet, H., Nyberg-Brodda, C.-F., Perrin, D., Petersen, K., Density of group languages in shift spaces. 2024 Preprint.
Burns, R.G., On finitely generated subgroups of free products. J. Aust. Math. Soc. 12:3 (1971), 358–364.
Dolce, F., Dvořáková, Ľ., Pelantová, E., On balanced sequences and their critical exponent. Theoret. Comput. Sci. 939 (2023), 18–47.
Durand, F., A characterization of substitutive sequences using return words. Discrete Math. 179:1–3 (1998), 89–101.
Durand, F., HD0L-ω-equivalence and periodicity problems in the primitive case (to the memory of G. Rauzy). Unif. Distrib. Theory 7:1 (2012), 199–215.
Durand, F., Decidability of uniform recurrence of morphic sequences. Internat. J. Found. Comput. Sci. 24:1 (2013), 123–146.
Durand, F., Leroy, J., Decidability of isomorphism and factorization between minimal substitution subshifts. Discret. Anal., 7, 2022.
Dvořáková, Ľ., Pelantová, E., The repetition threshold of episturmian sequences. European J. Combin., 120, 2024, 104001.
Gheeraert, F., Goulet-Ouellet, H., Leroy, J., Stas, P., Algebraic characterization of dendricity. Electron. J. Comb., 32(1), 2025.
Glen, A., Justin, J., Widmer, S., Zamboni, L.Q., Palindromic richness. European J. Combin. 30:2 (2009), 510–531.
Goulet-Ouellet, H., Suffix-connected languages. Theoret. Comput. Sci. 923 (2022), 126–143.
Hall, M., Coset representations in free groups. Trans. Amer. Math. Soc., 67(2), 1949, 421.
Harju, T., Linna, M., On the periodicity of morphisms on free monoids. RAIRO Theor. Inform. Appl. 20:1 (1986), 47–54.
Justin, J., Vuillon, L., Return words in Sturmian and episturmian words. RAIRO Theor. Inform. Appl. 34:5 (2000), 343–356, 10.1051/ita:2000121.
Kapovich, I., Myasnikov, A., Stallings foldings and subgroups of free groups. J. Algebra 248:2 (2002), 608–668.
Krawczyk, E., Dynamical and Arithmetic Properties of Substitutive Systems. (Ph.D. thesis), 2023, Jagiellonian University of Kraków.
Kyriakoglou, R., Iterated Morphisms, Combinatorics on Words and Symbolic Dynamical Systems. (Ph.D. thesis), 2019, Université Paris-Est.
Lyndon, R.C., Schupp, P.E., Combinatorial Group Theory. 2001, Springer Berlin Heidelberg.
Malcev, A.I., On homomorphisms onto finite groups. Transl. Ser. 2, Am. Math. Soc. 119 (1983), 67–79.
Mossé, B., Puissances de mots et reconnaissabilité des points fixes d'une substitution. Theoret. Comput. Sci. 99:2 (1992), 327–334.
Pansiot, J.-J., Decidability of periodicity for infinite words. RAIRO Theor. Inform. Appl. 20:1 (1986), 43–46.
Raptis, E., Varsos, D., On the subgroup separability of the fundamental group of a finite graph of groups. Demonstr. Math. 29:1 (1996), 43–52.
Savelev, V.E., On Abelian Properties of Morphic Words. (Master's thesis), 2024, Saint-Petersburg State University.
Stallings, J.R., Foldings of G-trees. Alperin, R.C., (eds.) Arboreal Group Theory, 1991, Springer New York, New York, NY, 355–368.
Steinberg, B., Monoid kernels and profinite topologies on the free Abelian group. Bull. Aust. Math. Soc. 60:3 (1999), 391–402.
The SageMath Developers, SageMath, the Sage Mathematics Software System, Version 9.7. 2022.
Vuillon, L., A characterization of Sturmian words by return words. European J. Combin. 22:2 (2001), 263–275.
Weil, P., Stallings graphs research code. 2019 URL https://www.labri.fr/perso/weil/software/version-0-2/html/.