The Maximal Complexity of Quasiperiodic Infinite Words

Abstract

A quasiperiod of a finite or infinite string is a word whose occurrences cover every part of the string. An infinite string is referred to as quasiperiodic if it has a quasiperiod. We present a characterisation of the set of infinite strings having a certain word q as quasiperiod via a finite language Pq consisting of prefixes of the quasiperiod q. It turns out its star root Pq* is a suffix code having a bounded delay of decipherability. This allows us to calculate the maximal subword (or factor) complexity of quasiperiodic infinite strings having quasiperiod q and further to derive that maximally complex quasiperiodic infinite strings have quasiperiods aba or aabaa. It is shown that, for every length l≥3, a word of the form anban (or anbban if l is even) generates the most complex infinite string having this word as quasiperiod. We give the exact ordering of the lengths l with respect to the achievable complexity among all words of length l.

Keywords

• quasiperiod
• formal language
• asymptotic growth
• polynomial