A1 Refereed original research article in a scientific journal
Cyclically repetition-free words on small alphabets
Authors: Harju Tero, Nowotka Dirk
Publisher: ELSEVIER SCIENCE BV
Publication year: 2010
Journal: Information Processing Letters
Journal name in source: INFORMATION PROCESSING LETTERS
Journal acronym: INFORM PROCESS LETT
Number in series: 14-15
Volume: 110
Issue: 14-15
First page : 591
Last page: 595
Number of pages: 5
ISSN: 0020-0190
DOI: https://doi.org/10.1016/j.ipl.2010.05.005
Self-archived copy’s web address: https://research.utu.fi/converis/portal/Publication/3917430
Abstract
All sufficiently long binary words contain a square but there are infinite binary words having only the short squares 00, 11 and 0101. Recently it was shown by J. Currie that there exist cyclically square-free words in a ternary alphabet except for lengths 5, 7, 9, 10, 14, and 17. We consider binary words all conjugates of which contain only short squares. We show that the number c(n) of these binary words of length n grows unboundedly. In order for this, we show that there are morphisms that preserve circular square-free words in the ternary alphabet. (C) 2010 Published by Elsevier B.V.
All sufficiently long binary words contain a square but there are infinite binary words having only the short squares 00, 11 and 0101. Recently it was shown by J. Currie that there exist cyclically square-free words in a ternary alphabet except for lengths 5, 7, 9, 10, 14, and 17. We consider binary words all conjugates of which contain only short squares. We show that the number c(n) of these binary words of length n grows unboundedly. In order for this, we show that there are morphisms that preserve circular square-free words in the ternary alphabet. (C) 2010 Published by Elsevier B.V.
Downloadable publication This is an electronic reprint of the original article. |  |
UTU Research Portal