Testing k-binomial equivalence

Dominik D. Freydenberger, Pawel Gawrychowski, Juhani Karhumäki +2

Two words $w_1$ and $w_2$ are said to be $k$-binomial equivalent if every non-empty word $x$ of length at most $k$ over the alphabet of $w_1$ and $w_2$ appears as a scattered facto…