The Maximal Subword Complexity of Quasiperiodic Infinite Words
Ronny Polley, Ludwig Staiger · Electronic Proceedings in Theoretical Computer Science · 2010
We provide an exact estimate on the maximal subword complexity for quasiperiodic infinite words. To this end we give a representation of the set of finite and of infinite words having a certain quasiperiod q via a finite language derived from q. It is shown that this language is a suffix code having a bounded delay of decipherability. Our estimate of the subword complexity now follows from this result, previously known results on the subword complexity and elementary results on formal power series.