Combinatorics on words; Factor complexity; Abelian complexity; Binomial complexity; iterates of Thue-Morse morphism
Abstract :
[en] Two words are k-binomially equivalent, if each word of length at most k occurs as a subword, or scattered factor, the same number of times in both words. The k-binomial complexity of an infinite word maps the natural n to the number of k-binomial equivalence classes represented by its factors of length n. Inspired by questions raised by Lejeune, we study the relationships between the k and (k+1)-binomial complexities; as well as the link with the usual factor complexity. We show that pure morphic words obtained by iterating a Parikh-collinear morphism, i.e. a morphism mapping all words to words with bounded abelian complexity, have bounded k-binomial complexity. In particular, we study the properties of the image of a Sturmian word by an iterate of the Thue-Morse morphism.
Binomial complexities and Parikh-collinear morphisms
Publication date :
09 May 2022
Event name :
26th International Conference Developments in Language Theory (DLT-2022)
Event organizer :
University of South Florida (USF)
Event date :
May 9-13
Audience :
International
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique
Commentary :
Work in collaboration with Michel Rigo (ULiège) and Markus A. Whiteland (ULiège). // Travail en collaboration avec Michel Rigo (ULiège) et Markus A. Whiteland (ULiège).