dc.contributor.author |
Polley, R |
en |
dc.contributor.author |
Staiger, L |
en |
dc.date.accessioned |
2016-01-04T21:55:57Z |
en |
dc.date.available |
2016-01-04T21:55:57Z |
en |
dc.date.issued |
2015 |
en |
dc.identifier.citation |
CDMTCS Research Reports CDMTCS-479 (2015) |
en |
dc.identifier.issn |
1178-3540 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/27848 |
en |
dc.description.abstract |
A quasiperiod of a word or an infinite string is a word which covers every part of the string. A word or an infinite string is referred to as quasiperiodic if it has a quasiperiod. It is obvious that a quasiperiodic infinite string cannot have every word as a subword (factor). Therefore, the question
arises how large the set of subwords of a quasiperiodic infinite string can be [Mar04].
Here we show that on the one hand the maximal subword complexity of quasiperiodic infinite strings and on the other hand the size of the sets of maximally complex quasiperiodic infinite strings both are intimately related to the smallest Pisot number tP (also known as plastic constant). We provide an exact estimate on the maximal subword complexity for quasiperiodic infinite words. |
en |
dc.publisher |
Department of Computer Science, The University of Auckland, New Zealand |
en |
dc.relation.ispartofseries |
CDMTCS Research Report Series |
en |
dc.rights |
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.source.uri |
https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/index.php |
en |
dc.title |
Quasiperiods, Subword Complexity and the Smallest Pisot Number |
en |
dc.type |
Technical Report |
en |
dc.subject.marsden |
Fields of Research |
en |
dc.rights.holder |
The author(s) |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |