2025/09/19 by Campbell, John M., Currie, James, Rampersad, Narad · 1 citation
#11B85 #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2509.16034
Letting w denote a finite, nonempty word, let red(w) denote the word obtained from w by replacing every subword s of w of the form cc ⋯ c for a given character c (such that there is no character immediately to the left or right of s equal to c) with c. Complexity functions for infinite words play important roles within combinatorics on words, and this leads us to introduce and investigate variants of the factor and abelian complexity functions using the given reduction operation. By enumerating words v and w of a given length n ≥ 0 and associated with an infinite sequence over a finite alphabet such that red(v) and red(w) are equal or otherwise equivalent in some specified way, by analogy with the factor and abelian complexity functions, this may be seen as producing simplified versions of previously introduced complexity functions. We prove a recursion for the reduced factor complexity function ρtred for the Thue-Morse sequence t, giving us that (ρtred(n) : n ∈ ℕ) is a 2-regular sequence, we prove an explicit evaluation for the reduced factor complexity function ρfred for the (regular) paperfolding sequence f, together with an evaluation for the reduced abelian complexity function ρfab, red for f. We conclude with open problems concerning ρtab, red.