The Maximal Subword Complexity of Quasiperiodic Infinite Words

Ronny Polley
(Uni Halle)
Ludwig Staiger
(Uni Halle)

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.

In Ian McQuillan and Giovanni Pighizzini: Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems (DCFS 2010), Saskatoon, Canada, 8-10th August 2010, Electronic Proceedings in Theoretical Computer Science 31, pp. 169–176.
Published: 7th August 2010.

ArXived at: bibtex PDF

Comments and questions to:
For website issues: