RAIRO-Theor. Inf. Appl.
Volume 48, Number 3, July-August 2014Special issue in the honor of the 14th “Journées montoises d’informatique théorique”. I.
|Page(s)||307 - 314|
|Published online||10 July 2014|
Existence of an infinite ternary 64-abelian square-free word
1 Department of Mathematics and Statistics & TUCS, University of Turku,
20014 Turku, Finland.
Accepted: 14 March 2014
We consider a recently defined notion of k-abelian equivalence of words by concentrating on avoidance problems. The equivalence class of a word depends on the numbers of occurrences of different factors of length k for a fixed natural number k and the prefix of the word. We have shown earlier that over a ternary alphabet k-abelian squares cannot be avoided in pure morphic words for any natural number k. Nevertheless, computational experiments support the conjecture that even 3-abelian squares can be avoided over ternary alphabets. In this paper we establish the first avoidance result showing that by choosing k to be large enough we have an infinite k-abelian square-free word over three letter alphabet. In addition, this word can be obtained as a morphic image of a pure morphic word.
Mathematics Subject Classification: 68R15
Key words: Combinatorics on words / k-abelian equivalence / square-freeness
© EDP Sciences 2014
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.