An efficient algorithm to decide periodicity of $b$-recognisable sets using LSDF convention

Abstract

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.

References in corpus (2)

• A proof for the decidability of HD0L ultimate periodicity
• Least Significant Digit First Presburger Automata