2005/12/13 by Irina Gheorghiciuc, Gheorghiciuc, Irina
Computer Science · #Algorithms and Data Compression #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.math/0512256
openalex publication_date 2005/12/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let Aq be a q-letter alphabet and w be a right infinite word on this alphabet. A subword of w is a block of consecutive letters of w. The subword complexity function of w assigns to each positive integer n the number fw(n) of distinct subwords of length n of w. The gap function of an infinite word over the binary alphabet \0,1 \ gives the distances between consecutive 1's in this word. In this paper we study infinite binary words whose gap function is injective or "almost injective". A method for computing the subword complexity of such words is given. A necessary and sufficient condition for a function to be the subword complexity function of a binary word whose gap function is strictly increasing is obtained.