### Abstract

Lingua originale | English |
---|---|

Titolo della pubblicazione ospite | Leibniz International Proceedings in Informatics, LIPIcs |

Numero di pagine | 9 |

Stato di pubblicazione | Published - 2016 |

### All Science Journal Classification (ASJC) codes

- Software

### Cita questo

*Leibniz International Proceedings in Informatics, LIPIcs*

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

Risultato della ricerca: Chapter

*Leibniz International Proceedings in Informatics, LIPIcs.*

}

TY - CHAP

T1 - Anti-powers in infinite words

AU - Fici, Gabriele

AU - Restivo, Antonio

AU - Silva, Manuel

AU - Zamboni, Luca Q.

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

BT - Leibniz International Proceedings in Informatics, LIPIcs

ER -