The Critical Exponent is Computable for Automatic Sequences

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.