On a group theoretic generalization of the Morse-Hedlund theorem

[en] In their 1938 seminal paper on symbolic dynamics, Morse and Hedlund proved that every aperiodic infinite word contains at least n+ 1 distinct factors of each length n. They further showed that an infinite word has exactly n+ 1 distinct factors of each length n if and only if it is binary, aperiodic and balanced, i.e., it is a Sturmian word. In this paper we obtain a broad generalization of the Morse-Hedlund theorem via group actions.

Disciplines :

Mathematics

Author, co-author :

Charlier, Emilie ; Université de Liège > Département de mathématique > Mathématiques discrètes

Puzynina, Svetlana

Zamboni, Luca

Language :

English

Title :

On a group theoretic generalization of the Morse-Hedlund theorem

Publication date :

2017

Journal title :

Proceedings of the American Mathematical Society

ISSN :

0002-9939

eISSN :

1088-6826

Publisher :

American Mathematical Society

Volume :

145

Issue :

Pages :

3381–3394

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 28 January 2016

Statistics

Number of views

77 (10 by ULiège)

Number of downloads

126 (1 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

publications

supporting

mentioning

contrasting

Smart Citations

Citing PublicationsSupportingMentioningContrasting

View Citations

See how this article has been cited at scite.ai

scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.

Bibliography

A. Aberkane and S. Brlek, Suites de même complexité que celle de Thue–Morse, in Actes des Journées Montoises d’informatique théorique, Montpellier, France, 2002, pp. 85–89.
Jean-Paul Allouche, The number of factors in a paperfolding sequence, Bull. Austral. Math. Soc. 46 (1992), no. 1, 23–32, DOI 10.1017/S0004972700011655. MR1170439
Jean-Paul Allouche, Michael Baake, Julien Cassaigne, and David Damanik, Palindrome complexity, Theoret. Comput. Sci. 292 (2003), no. 1, 9–31, DOI 10.1016/S0304-3975(01)00212-2. Selected papers in honor of Jean Berstel. MR1964623
Jean Berstel and Aldo de Luca, Sturmian words, Lyndon words and trees, Theoret. Comput. Sci. 178 (1997), no. 1-2, 171–203, DOI 10.1016/S0304-3975(96)00101-6. MR1453849
Valérie Berthé, Aldo de Luca, and Christophe Reutenauer, On an involution of Christoffel words and Sturmian morphisms, European J. Combin. 29 (2008), no. 2, 535–553, DOI 10.1016/j.ejc.2007.03.001. MR2388389
Jean-Pierre Borel and Christophe Reutenauer, On Christoffel classes, Theor. Inform. Appl. 40 (2006), no. 1, 15–27, DOI 10.1051/ita:2005038. MR2197281
Julien Cassaigne, Gabriele Fici, Marinella Sciortino, and Luca Q. Zamboni, Cyclic complexity of words, J. Combin. Theory Ser. A 145 (2017), 36–56, DOI 10.1016/j.jcta.2016.07.002. MR3551645
Ethan M. Coven and G. A. Hedlund, Sequences with minimal block growth, Math. Systems Theory 7 (1973), 138–153. MR0322838
Van Cyr and Bryna Kra, Complexity of short rectangles and periodicity. Part A, European J. Combin. 52 (2016), 146–173, DOI 10.1016/j.ejc.2015.10.003. MR3425972
Aldo de Luca, Sturmian words: structure, combinatorics, and their arithmetics, Theoret. Comput. Sci. 183 (1997), no. 1, 45–82, DOI 10.1016/S0304-3975(96)00310-6. MR1468450
Aldo de Luca and Filippo Mignosi, Some combinatorial properties of Sturmian words, Theoret. Comput. Sci. 136 (1994), no. 2, 361–385, DOI 10.1016/0304-3975(94)00035-H. MR1311214
Fabien Durand and Michel Rigo, Multidimensional extension of the Morse-Hedlund theorem, European J. Combin. 34 (2013), no. 2, 391–409, DOI 10.1016/j.ejc.2012.08.003. MR2994406
A. Ehrenfeucht, K. P. Lee, and G. Rozenberg, Subword complexities of various classes of deterministic developmental languages without interactions, Theor. Comput. Sci. 1 (1975), no. 1, 59–75. MR0388861
Michael Hoffman, An invariant of finite abelian groups, Amer. Math. Monthly 94 (1987), no. 7, 664–666, DOI 10.2307/2322221. MR935854
Oliver Jenkinson, Optimization and majorization of invariant measures, Electron. Res. An-nounc. Amer. Math. Soc. 13 (2007), 1–12, DOI 10.1090/S1079-6762-07-00170-9. MR2285761
Oliver Jenkinson, Balanced words and majorization, Discrete Math. Algorithms Appl. 1 (2009), no. 4, 463–483, DOI 10.1142/S179383090900035X. MR2725729
Vasso Anagnostopoulou and Oliver Jenkinson, Which beta-shifts have a largest invariant measure?, J. Lond. Math. Soc. (2) 79 (2009), no. 2, 445–464, DOI 10.1112/jlms/jdn070. MR2496523
Oliver Jenkinson and Luca Q. Zamboni, Characterisations of balanced words via orderings, Theoret. Comput. Sci. 310 (2004), no. 1-3, 247–271, DOI 10.1016/S0304-3975(03)00397-9. MR2020344
Teturo Kamae and Luca Zamboni, Sequence entropy and the maximal pattern complexity of infinite words, Ergodic Theory Dynam. Systems 22 (2002), no. 4, 1191–1199, DOI 10.1017/S0143385702000585. MR1926282
M. Lothaire, Algebraic combinatorics on words, A collective work by Jean Berstel, Dominique Perrin, Patrice Seebold, Julien Cassaigne, Aldo De Luca, Steffano Varricchio, Alain Lascoux, Bernard Leclerc, Jean-Yves Thibon, Veronique Bruyere, Christiane Frougny, Filippo Mignosi, Antonio Restivo, Christophe Reutenauer, Dominique Foata, Guo-Niu Han, Jacques Desar-menien, Volker Diekert, Tero Harju, Juhani Karhumaki and Wojciech Plandowski; with a preface by Berstel and Perrin. Encyclopedia of Mathematics and its Applications, vol. 90, Cambridge University Press, Cambridge, 2002. MR1905123
Marston Morse and Gustav A. Hedlund, Symbolic dynamics, Amer. J. Math. 60 (1938), no. 4, 815–866, DOI 10.2307/2371264. MR1507944
Marston Morse and Gustav A. Hedlund, Symbolic dynamics II. Sturmian trajectories, Amer. J. Math. 62 (1940), 1–42. MR0000745
Igor Pak and Amanda Redlich, Long cycles in abc-permutations, Funct. Anal. Other Math. 2 (2008), no. 1, 87–92, DOI 10.1007/s11853-008-0017-0. MR2466089
Gwénaël Richomme, Kalle Saari, and Luca Q. Zamboni, Abelian complexity of minimal sub-shifts, J. Lond. Math. Soc. (2) 83 (2011), no. 1, 79–95, DOI 10.1112/jlms/jdq063. MR2763945
J. W. Sander and R. Tijdeman, The rectangle complexity of functions on two-dimensional lattices, Theoret. Comput. Sci. 270 (2002), no. 1-2, 857–863, DOI 10.1016/S0304-3975(01)00281-X. MR1871099
A. Thue, Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat-Nat. Kl. 7 (1906), 1–22.

Similar publications

Sorry the service is unavailable at the moment. Please try again later.

Name	Provider / Domaine	Expiration	Description
JSESSIONID	Oracle Corporation www.uliege.be	Session	General purpose platform session cookie, used by sites written in JSP. Usually used to maintain an anonymous user session by the server.
CookieScriptConsent	CookieScript .uliege.be	1 year	This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.

Name	Provider / Domaine	Expiration	Description
_pk_id	InnoCraft Ltd .uliege.be	1 year	Used to store a few details about the user such as the unique visitor ID
_pk_ses	InnoCraft Ltd .uliege.be	30 minutes	Short lived cookies used to temporarily store data for the visit
_pk_ref	InnoCraft Ltd .uliege.be	6 months	Used to store the attribution information, the referrer initially used to visit the website