Computing k-binomial equivalence and avoiding binomial repetitions
Michel Rigo · Open Repository and Bibliography (University of Liège) · 2015
In this talk, I will first recall basic results on binomial coefficients of words, then review the connections and differences with Parikh matrices. As a generalization of abelian equivalence, two words u and v are k-binomially equivalent if every word of length at most k appears as a subword of u exactly as many times as it appears as a subword of v. So a k-binomial square is a word uv where u and v are k-binomially equivalent. We will discuss avoidance of squares and cubes in infinite words (this is a joint word with M. Rao). Finally, I will consider the question of deciding whether or not two finite words are k-binomially equivalent. This problem has recently been shown to be decidable in polynomial time by Freydenberger, Gawrychowski et al.