文章基本信息

标题：The Critical Exponent is Computable for Automatic Sequences
本地全文：下载
作者：Jeffrey Shallit
期刊名称：Electronic Proceedings in Theoretical Computer Science
电子版ISSN：2075-2180
出版年度：2011
卷号：63
页码：231-239
DOI：10.4204/EPTCS.63.29
出版社：Open Publishing Association
摘要：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.