The Critical Exponent is Computable for Automatic Sequences

Abstract

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.