Anti-powers in infinite words

Antonio Restivo, Gabriele Fici, Luca Q. Zamboni, Manuel Silva

Risultato della ricerca: Chapter

4 Citazioni (Scopus)

Abstract

In combinatorics of words, a concatenation of k consecutive equal blocks is called a power of order k. In this paper we take a different point of view and define an anti-power of order k as a concatenation of k consecutive pairwise distinct blocks of the same length. As a main result, we show that every infinite word contains powers of any order or anti-powers of any order. That is, the existence of powers or anti-powers is an unavoidable regularity. Indeed, we prove a stronger result, which relates the density of anti-powers to the existence of a factor that occurs with arbitrary exponent. From these results, we derive that at every position of an aperiodic uniformly recurrent word start anti-powers of any order. We further show that any infinite word avoiding anti-powers of order 3 is ultimately periodic, and that there exist aperiodic words avoiding anti-powers of order 4. We also show that there exist aperiodic recurrent words avoiding anti-powers of order 6, and leave open the question whether there exist aperiodic recurrent words avoiding anti-powers of order k for k = 4, 5.
Lingua originaleEnglish
Titolo della pubblicazione ospiteLeibniz International Proceedings in Informatics, LIPIcs
Pagine-
Numero di pagine9
Volume55
Stato di pubblicazionePublished - 2016

All Science Journal Classification (ASJC) codes

  • Software

Cita questo

Restivo, A., Fici, G., Zamboni, L. Q., & Silva, M. (2016). Anti-powers in infinite words. In Leibniz International Proceedings in Informatics, LIPIcs (Vol. 55, pagg. -)

Anti-powers in infinite words. / Restivo, Antonio; Fici, Gabriele; Zamboni, Luca Q.; Silva, Manuel.

Leibniz International Proceedings in Informatics, LIPIcs. Vol. 55 2016. pag. -.

Risultato della ricerca: Chapter

Restivo, A, Fici, G, Zamboni, LQ & Silva, M 2016, Anti-powers in infinite words. in Leibniz International Proceedings in Informatics, LIPIcs. vol. 55, pagg. -.
Restivo A, Fici G, Zamboni LQ, Silva M. Anti-powers in infinite words. In Leibniz International Proceedings in Informatics, LIPIcs. Vol. 55. 2016. pag. -
Restivo, Antonio ; Fici, Gabriele ; Zamboni, Luca Q. ; Silva, Manuel. / Anti-powers in infinite words. Leibniz International Proceedings in Informatics, LIPIcs. Vol. 55 2016. pagg. -
@inbook{5eaf337bef404336acbc2274f0622c96,
title = "Anti-powers in infinite words",
abstract = "In combinatorics of words, a concatenation of k consecutive equal blocks is called a power of order k. In this paper we take a different point of view and define an anti-power of order k as a concatenation of k consecutive pairwise distinct blocks of the same length. As a main result, we show that every infinite word contains powers of any order or anti-powers of any order. That is, the existence of powers or anti-powers is an unavoidable regularity. Indeed, we prove a stronger result, which relates the density of anti-powers to the existence of a factor that occurs with arbitrary exponent. From these results, we derive that at every position of an aperiodic uniformly recurrent word start anti-powers of any order. We further show that any infinite word avoiding anti-powers of order 3 is ultimately periodic, and that there exist aperiodic words avoiding anti-powers of order 4. We also show that there exist aperiodic recurrent words avoiding anti-powers of order 6, and leave open the question whether there exist aperiodic recurrent words avoiding anti-powers of order k for k = 4, 5.",
author = "Antonio Restivo and Gabriele Fici and Zamboni, {Luca Q.} and Manuel Silva",
year = "2016",
language = "English",
isbn = "9783959770132",
volume = "55",
pages = "--",
booktitle = "Leibniz International Proceedings in Informatics, LIPIcs",

}

TY - CHAP

T1 - Anti-powers in infinite words

AU - Restivo, Antonio

AU - Fici, Gabriele

AU - Zamboni, Luca Q.

AU - Silva, Manuel

PY - 2016

Y1 - 2016

N2 - In combinatorics of words, a concatenation of k consecutive equal blocks is called a power of order k. In this paper we take a different point of view and define an anti-power of order k as a concatenation of k consecutive pairwise distinct blocks of the same length. As a main result, we show that every infinite word contains powers of any order or anti-powers of any order. That is, the existence of powers or anti-powers is an unavoidable regularity. Indeed, we prove a stronger result, which relates the density of anti-powers to the existence of a factor that occurs with arbitrary exponent. From these results, we derive that at every position of an aperiodic uniformly recurrent word start anti-powers of any order. We further show that any infinite word avoiding anti-powers of order 3 is ultimately periodic, and that there exist aperiodic words avoiding anti-powers of order 4. We also show that there exist aperiodic recurrent words avoiding anti-powers of order 6, and leave open the question whether there exist aperiodic recurrent words avoiding anti-powers of order k for k = 4, 5.

AB - In combinatorics of words, a concatenation of k consecutive equal blocks is called a power of order k. In this paper we take a different point of view and define an anti-power of order k as a concatenation of k consecutive pairwise distinct blocks of the same length. As a main result, we show that every infinite word contains powers of any order or anti-powers of any order. That is, the existence of powers or anti-powers is an unavoidable regularity. Indeed, we prove a stronger result, which relates the density of anti-powers to the existence of a factor that occurs with arbitrary exponent. From these results, we derive that at every position of an aperiodic uniformly recurrent word start anti-powers of any order. We further show that any infinite word avoiding anti-powers of order 3 is ultimately periodic, and that there exist aperiodic words avoiding anti-powers of order 4. We also show that there exist aperiodic recurrent words avoiding anti-powers of order 6, and leave open the question whether there exist aperiodic recurrent words avoiding anti-powers of order k for k = 4, 5.

UR - http://hdl.handle.net/10447/250822

UR - http://drops.dagstuhl.de/opus/volltexte/2016/6259/

M3 - Chapter

SN - 9783959770132

VL - 55

SP - -

BT - Leibniz International Proceedings in Informatics, LIPIcs

ER -