The Maximal Subword Complexity of Quasiperiodic Infinite Words
Ronny Polley, Ludwig Staiger
Electronic Proceedings in Theoretical Computer Science · 2010
doi:10.4204/eptcs.31.19 (opens in a new tab)
We email you when a new notice or a question about this paper appears.
Abstract
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.
Abstract licence: CC BY-NC-ND
Reads
Read by people on this page
None yet.
Checked or read by AI through naulon
None yet.
A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.
Are you an author?
Is this your paper?
Claim it to add your note and be paid when agents cite it. Free.