Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
433927 | Theoretical Computer Science | 2015 | 9 Pages |
Abstract
Two finite words u,vu,v are 2-binomially equivalent if, for all words x of length at most 2, the number of occurrences of x as a (scattered) subword of u is equal to the number of occurrences of x in v. This notion is a refinement of the usual abelian equivalence. A 2-binomial square is a word uv where u and v are 2-binomially equivalent.In this paper, considering pure morphic words, we prove that 2-binomial squares (resp. cubes) are avoidable over a 3-letter (resp. 2-letter) alphabet. The sizes of the alphabets are optimal.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Michaƫl Rao, Michel Rigo, Pavel Salimov,