The Critical Exponent is Computable for Automatic Sequences

Jeffrey Shallit
(School of Computer Science, University of Waterloo)

The critical exponent of an infinite word is defined to be the supremum of the exponent of each of its factors. For k-automatic sequences, we show that this critical exponent is always either a rational number or infinite, and its value is computable. This generalizes or recovers previous results of Krieger and others. Our technique is applicable to other situations; e.g., the computation of the optimal recurrence constant for a linearly recurrent k-automatic sequence.

In Petr Ambrož, Štěpán Holub and Zuzana Masáková: Proceedings 8th International Conference Words 2011 (WORDS 2011), Prague, Czech Republic, 12-16th September 2011, Electronic Proceedings in Theoretical Computer Science 63, pp. 231–239.
Published: 17th August 2011.

ArXived at: http://dx.doi.org/10.4204/EPTCS.63.29 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org