Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
437552 | Theoretical Computer Science | 2011 | 5 Pages |
Abstract
Let be the recurrence time of the initial n-word of an infinite sequence . We have that is periodic if and only if there exists M such that for all n>M. For non-periodic sequences, therefore, is the possible lowest upper bound for Rn. We show that if for all n, then is Sturmian. The opposite does not hold in general and we completely classify such Sturmian sequences.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics