## 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.

Original language | English |
---|---|

Title of host publication | 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 |

Editors | Yuval Rabani, Ioannis Chatzigiannakis, Davide Sangiorgi, Michael Mitzenmacher |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Volume | 55 |

ISBN (Electronic) | 9783959770132 |

DOIs | |

Publication status | Published - 1 Aug 2016 |

Event | 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 - Rome, Italy Duration: 12 Jul 2016 → 15 Jul 2016 |

### Conference

Conference | 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 |
---|---|

Country/Territory | Italy |

City | Rome |

Period | 12/07/16 → 15/07/16 |

## Keywords

- Anti-power
- Avoidability
- Infinite word
- Unavoidable regularity