The Subword Complexity of a Two-Parameter Family of Sequences

Abstract

We determine the subword complexity of the characteristic functions of a two-parameter family $\{A_n\}_{n=1}^\infty$ of infinite sequences which are associated with the winning strategies for a family of 2-player games. A special case of the family has the form $A_n=\lfloor n\alpha\rfloor$ for all $n\in {\bf Z}_{>0}$, where $\alpha$ is a fixed positive irrational number. The characteristic functions of such sequences have been shown to have subword complexity $n+1$. We show that every sequence in the extended family has subword complexity $O(n)$.