Algebraic characterization of dendricity

[en] Dendric shift spaces simultaneously generalize codings of regular interval exchanges and episturmian shift spaces, themselves both generalizations of Sturmian words. One of the key properties enforced by dendricity is the Return Theorem. In this paper, we prove its converse, providing the following natural algebraic perspective on dendricity: A minimal shift space is dendric if and only if every set of return words is a basis of the free group over the alphabet.

Disciplines :

Mathematics

Author, co-author :

Gheeraert, France ; Université de Liège - ULiège > Mathematics

Goulet-Ouellet, Herman

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 > Département de mathématique > Mathématiques discrètes

Language :

English

Title :

Algebraic characterization of dendricity

Publication date :

28 March 2025

Journal title :

Electronic Journal of Combinatorics

ISSN :

1097-1440

eISSN :

1077-8926

Publisher :

Electronic Journal of Combinatorics, United States - Georgia

Volume :

Peer reviewed :

Peer Reviewed verified by ORBi

Commentary :

7 pages

Available on ORBi :

since 03 July 2024

Statistics

Number of views

134 (10 by ULiège)

Number of downloads

21 (3 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

J. Almeida and A. Costa. A geometric interpretation of the Schützenberger group of a minimal subshift. Ark. Math., 54(2): 243–275, 2016. doi:10.1007/s11512-016-0233-7.
L. Balková, E. Pelantová, and W. Steiner. Sequences with constant number of return words. Monatsh. Math., 155(3-4): 251–263, 2008. doi:10.1007/s00605-008-0001-2.
V. Berthé, C. De Felice, F. Dolce, J. Leroy, D. Perrin, C. Reutenauer, and G. Rindone. Acyclic, connected and tree sets. Monatsh. Math., 176(4): 521–550, 2015. doi:10.1007/s00605-014-0721-4.
V. Berthé, C. D. Felice, F. Dolce, J. Leroy, D. Perrin, C. Reutenauer, and G. Rindone. Maximal bifix decoding. Discrete Math., 338(5): 725–742, 2015. doi:10.1016/j.disc.2014.12.010.
V. Berthé, C. D. Felice, F. Dolce, J. Leroy, D. Perrin, C. Reutenauer, and G. Rindone. The finite index basis property. J. Pure Appl. Algebra, 219(7): 2521–2537, 2015. doi:10.1016/j.jpaa.2014.09.014.
V. Berthé, F. Dolce, F. Durand, J. Leroy, and D. Perrin. Rigidity and substitutive dendric words. Int. J. Found. Comput., 29(05): 705–720, 2018. doi:10.1142/S0129054118420017.
V. Berthé, P. Cecchi Bernales, F. Durand, J. Leroy, D. Perrin, and S. Petite. On the dimension group of unimodular S-adic subshifts. Monatsh. Math., 194(4): 687–717, 2021. doi:10.1007/s00605-020-01488-3.
J. A. Bondy and U. S. R. Murty. Graph Theory with Applications. Macmillan London, 1976.
J. Cassaigne. Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. Simon Stevin, 4(1): 67–88, 1997. doi:10.36045/bbms/1105730624.
M. Damron and J. Fickenscher. The number of ergodic measures for transitive subshifts under the regular bispecial condition. Ergod. Theory Dyn. Syst., 42(1): 86–140, 2020. doi:10.1017/etds.2020.134.
F. Durand. A characterization of substitutive sequences using return words. Discrete Math., 179(1-3): 89–101, 1998. doi:10.1016/S0012-365X(97)00029-0.
S. Ferenczi. Combinatorial methods for interval exchange transformations. Southeast Asian Bull. Math., 37(1): 47–66, 2013.
N. P. Fogg. Substitutions in Dynamics, Arithmetics and Combinatorics. Springer Berlin Heidelberg, 2002. doi:10.1007/b13861.
F. Gheeraert and J. Leroy. S-adic characterization of minimal dendric shifts. DMTCS, 22(7), 2024. doi:10.46298/dmtcs.13130.
F. Gheeraert, M. Lejeune, and J. Leroy. S-adic characterization of minimal ternary dendric shifts. Ergod. Theory Dyn. Syst., 42(11): 3393–3432, 2022. doi:10.1017/etds.2021.84.
A. Glen and J. Justin. Episturmian words: A survey. RAIRO Theor. Inform. Appl., 43(3): 403–442, 2009. doi:10.1051/ita/2009003.
H. Goulet-Ouellet. Suffix-connected languages. Theoret. Comput. Sci., 923: 126–143, 2022. doi:10.1016/j.tcs.2022.05.001.
J. Justin and L. Vuillon. Return words in Sturmian and episturmian words. RAIRO Theor. Inform. Appl., 34(5): 343–356, 2000. doi:10.1051/ita:2000121.
D. Lind and B. Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge, 1995. doi:10.1017/CBO9780511626302.
M. Lothaire. Combinatorics on Words. Cambridge University Press, 1997. doi:10.1017/CBO9780511566097.
M. Lothaire. Algebraic combinatorics on words. Cambridge University Press, 2002. doi:10.1017/CBO9781107326019.
R. C. Lyndon and P. E. Schupp. Combinatorial Group Theory. Springer Berlin Heidelberg, 2001. doi:10.1007/978-3-642-61896-3.
M. Morse and G. A. Hedlund. Symbolic dynamics II: Sturmian trajectories. Am. J. Math., 62(1): 1–42, 1940. doi:10.2307/2371431.
L. Vuillon. A characterization of Sturmian words by return words. Eur. J. Comb., 22(2): 263–275, 2001. doi:10.1006/eujc.2000.0444.