Computing k-binomial equivalence and avoiding binomial repetitions

English

Rigo, Michel[Université de Liège > Département de mathématique > Mathématiques discrètes >]

28-Oct-2015

No

Yes

Automatic sequences, Number theory, Aperiodic order

from 28-10-2015 to 30-10-2015

TU Delft

Delft

The Netherlands

[en] combinatorics on words ; binomial coefficients ; equivalence

[en] 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.