| Autor: |
Ronny Polley, Ludwig Staiger |
| Jazyk: |
angličtina |
| Rok vydání: |
2010 |
| Předmět: |
|
| Zdroj: |
Electronic Proceedings in Theoretical Computer Science, Vol 31, Iss Proc. DCFS 2010, Pp 169-176 (2010) |
| Druh dokumentu: |
article |
| ISSN: |
2075-2180 |
| DOI: |
10.4204/EPTCS.31.19 |
| Popis: |
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. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
