Reference : Computing k-binomial equivalence and avoiding binomial repetitions
Scientific congresses and symposiums : Unpublished conference/Abstract
Physical, chemical, mathematical & earth Sciences : Mathematics
Computing k-binomial equivalence and avoiding binomial repetitions
Rigo, Michel mailto [Université de Liège > Département de mathématique > Mathématiques discrètes >]
Automatic sequences, Number theory, Aperiodic order
from 28-10-2015 to 30-10-2015
TU 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.

File(s) associated to this reference

Fulltext file(s):

Open access
Rigo.pdfBeamer of the talkAuthor preprint426.84 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.