The abelian complexity of infinite words and the Frobenius problem

2019/07/18 by I. David Kaye, Narad Rampersad, Kaye, Ian +1
Computer Science · #68R15 #Coding theory and cryptography #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1907.08247

openalex publication_date 2019/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the following problem, first introduced by Dekking. Consider an infinite word x over an alphabet 0,1,...,k-1 and a semigroup homomorphism S:0,1,...,k-1* -> N. Let L_x denote the set of factors of x. What conditions on S and the abelian complexity of x guarantee that S(L_x) contains all but finitely many elements of N? We examine this question for some specific infinite words x having different abelian complexity functions.

Related

• On abelian and additive complexity in infinite words
• On a generalization of Abelian equivalence and complexity of infinite words
• Variations of the Morse-Hedlund Theorem for k-Abelian Equivalence
• Subword complexity and decomposition of the set of factors
• Abelian Properties of Words (Extended abstract)