The subword complexity of a class of infinite binary words

AbstractThe 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 increasing is obtained