Characterizations of families of morphisms and words via binomial complexities

Two words are k-binomially equivalent if each subword of length at most k occurs the same number of times in both words. The k-binomial complexity of an infinite word is a counting function that maps n to the number of k-binomial equivalence classes represented by its factors of length n. Cassaigne et al. (2011) characterized a family of morphisms, which we call Parikh-collinear, as those morphisms that map all words to words with bounded 1-binomial complexity. Firstly, we extend this characterization: they map words with bounded k-binomial complexity to words with bounded (k+1)-binomial complexity. As a consequence, fixed points of Parikh-collinear morphisms are shown to have bounded k-binomial complexity for all k. Secondly, we give a new characterization of Sturmian words with respect to their k-binomial complexity. Then we characterize recurrent words having, for some k, the same j-binomial complexity as the Thue–Morse word for all j≤k. Finally, inspired by questions raised by Lejeune, we study the relationships between the k- and (k+1)-binomial complexities of infinite words; as well as the link with the usual factor complexity.<p></p>