一句话：刻画周期 b-可识别集的最小自动机，并在线性时间验证，从而以 O(b log n) 判定周期性。
设 b>1，非负整数集经 b 进制表示可视为 {0,...,b-1} 上的语言；若该语言正则，则称集合 b-可识别。最终周期集均为 b-可识别，而 Cobham 定理表明反之仅在所有进制下成立。论文研究判定问题：给定表示 b-可识别集 S 的有限自动机，S 是否最终周期？Honkala 已证明可判定，Leroux 用最低有效位优先（LSDF）约定给出二次算法。本文同样采用 LSDF，先刻画接受周期集的最小自动机的结构，再证明可在关于状态数的线性时间内验证该结构。由此得到 O(b log n) 的过程，用于判定 n 状态自动机是否接受最终周期集。
Let $b$ be an integer strictly greater than $1$. Each set of nonnegative integers is represented in base $b$ by a language over $\{0, 1, \dots, b - 1\}$. The set is said to be $b$-recognisable if it is represented by a regular language. It is known that ultimately periodic sets are $b$-recognisable, for every base $b$, and Cobham's theorem implies the converse: no other set is $b$-recognisable in every base $b$. We consider the following decision problem: let $S$ be a set of nonnegative integers that is $b$-recognisable, given as a finite automaton over $\{0,1, \dots, b - 1\}$, is $S$ periodic? Honkala showed in 1986 that this problem is decidable. Later on, Leroux used in 2005 the convention to write number representations with the least significant digit first (LSDF), and designed a quadratic algorithm to solve a more general problem. We use here LSDF convention as well and give a structural description of the minimal automata that accept periodic sets. Then, we show that it can be verified in linear time if a minimal automaton meets this description. In general, this yields a $O(b \log(n))$ procedure to decide whether an automaton with $n$ states accepts an ultimately periodic set of nonnegative integers.
@article{paperbot777,
title = {An efficient algorithm to decide periodicity of $b$-recognisable sets using LSDF convention},
author = {Victor Marsault},
journal = {Logical Methods in Computer Science},
volume = {Volume 15, Issue 3},
year = {2019},
doi = {10.23638/lmcs-15(3:8)2019}
}