On a group theoretic generalization of the Morse-Hedlund theorem

Charlier, Emilie; Puzynina, Svetlana; Zamboni, Luca

doi:10.1090/proc/13589

Download

Article (Scientific journals)

On a group theoretic generalization of the Morse-Hedlund theorem

Charlier, Emilie; Puzynina, Svetlana; Zamboni, Luca

2017 • In Proceedings of the American Mathematical Society, 145 (8), p. 3381–3394

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/192556

DOI
10.1090/proc/13589

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

Group Complexity-orbi.pdf

Author preprint (317.79 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

combinatorics on words; aperiodicty; Morse-Hedlund theorem

Abstract :

[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

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.