Abstract: In this paper we give a broad unified framework via group actions for constructing complexity functions of infinite words x = x0x1x2 · · · ∈ AN with values in a finite set A. Factor complexity, Abelian complexity and cyclic complexity are all particular cases of this general construction. We consider infinite sequences of permutation groups ω = (Gn)n≥1 with each Gn ⊆ Sn. Associated with every such sequence is a complexity function pω,x : N → N which counts, for each length n, the number of equivalence classes of factors of x of length n under the action of Gn on An given by g ∗ (u1u2 · · · un) = ug−1(1)ug−1(2) · · · ug−1(n). Each choice of ω = (Gn)n≥1 defines a unique complexity function which reflects a different combinatorial property of a given infinite word. For instance, an infinite word x has bounded Abelian complexity if and only if x is k-balanced for some positive integer k, while bounded cyclic complexity is equivalent to x being ultimately periodic. A celebrated result of G.A. Hedlund and M. Morse states that every aperiodic infinite word x ∈ AN contains at least n + 1 distinct factors of each length n. Moreover x ∈ AN has exactly n + 1 distinct factors of each length n if and only if x is a Sturmian word, i.e., binary, aperiodic and balanced. We prove that this characterisation of aperiodicity and Sturmian words extends to this general framework.

Cite: Charlier É. , Puzynina, S. , Zamboni L.Q.
On a group theoretic generalization of the Morse-Hedlund theorem
Proceedings of the American Mathematical Society. 2017. V.145. N8. P.3381-3394. DOI: 10.1090/proc/13589 WOS Scopus OpenAlex

Identifiers:

≡ Web of science:	WOS:000404112000018
≡ Scopus:	2-s2.0-85019618349
≡ OpenAlex:	W2964134153

Altmetrics: