[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
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
Carpi A. On abelian power-free morphisms. Internat. J. Algebra Comput. 1993, 3:151-167.
Dekking F.M. Strongly nonrepetitive sequences and progression-free sets. J. Combin. Theory Ser. A 1979, 27:181-185.
Erdös P. Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. 1961, 6:221-254.
Entringer R.C., Jackson D.E., Schatz J.A. On nonrepetitive sequences. J. Combin. Theory Ser. A 1974, 16:159-164.
Fraenkel A.S., Simpson R.J. How many squares must a binary sequence contain?. Electron. J. Combin. 1995, 2.
Huova M., Karhumäki J. Observations and problems on k-abelian avoidability. Dagstuhl Seminar 2011, vol. 11081:2215-2219.
Huova M., Karhumäki J. On unavoidability of k-abelian squares in pure morphic words. J. Integer Seq. 2013, 16(2):13.2.9.
Karhumäki J., Saarela A., Zamboni L.Q. On a generalization of abelian equivalence and complexity of infinite words. J. Combin. Theory Ser. A 2013, 120:2189-2206.
Keränen V. Abelian squares are avoidable on 4 letters. Lecture Notes in Comput. Sci. 1992, vol. 623:41-52.
Lothaire M. Combinatorics on Words, Cambridge Mathematical Library 1997, Cambridge University Press.
Rao M. On some generalizations of abelian power avoidability. Theoret. Comput. Sci. 2015, in press.
Rigo M., Salimov P. Another generalization of abelian equivalence: binomial complexity of infinite words. Lect. Notes in Comput. Sci. 2013, vol. 8079:217-228. Springer Verlag. J. Karhumäki, L. Zamboni (Eds.).
Thue A. Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr. Mat. Nat. Kl. 1906, 7:1-22.
Thue A. Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske Vid. Selsk. Skr. Mat. Nat. Kl. 1912, 1:1-67.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
