Subword Complexity and k-Synchronization

Daniel Goc, Luke Schaeffer, Jeffrey Shallit

We show that the subword complexity function p_x(n), which counts the number of distinct factors of length n of a sequence x, is k-synchronized in the sense of Carpi if x is k-auto…