Article (Scientific journals)
Avoiding 2-binomial squares and cubes
Rao, Michaël; Rigo, Michel; Salimov, Pavel
2015In Theoretical Computer Science, 572, p. 83-91
Peer Reviewed verified by ORBi
 

Files


Full Text
final.pdf
Author preprint (143.18 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
avoidance; binomial equivalence; infinite word; squarefree; cubefree
Abstract :
[en] Two finite words $u,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.
Disciplines :
Mathematics
Author, co-author :
Rao, Michaël
Rigo, Michel  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Salimov, Pavel
Language :
English
Title :
Avoiding 2-binomial squares and cubes
Publication date :
2015
Journal title :
Theoretical Computer Science
ISSN :
0304-3975
Publisher :
Elsevier Science, Amsterdam, Netherlands
Volume :
572
Pages :
83-91
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 26 February 2015

Statistics


Number of views
34 (7 by ULiège)
Number of downloads
258 (1 by ULiège)

Scopus citations®
 
13
Scopus citations®
without self-citations
6
OpenCitations
 
10

Bibliography


Similar publications



Contact ORBi