Article ID Journal Published Year Pages File Type
437552 Theoretical Computer Science 2011 5 Pages PDF
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