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

lmcs:3882 - Logical Methods in Computer Science, July 31, 2019, Volume 15, Issue 3
An efficient algorithm to decide periodicity of $b$-recognisable sets using LSDF convention

Authors: Marsault, Victor

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.


Source : oai:arXiv.org:1708.06228
DOI : 10.23638/LMCS-15(3:8)2019
Volume: Volume 15, Issue 3
Published on: July 31, 2019
Submitted on: August 25, 2017
Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Logic in Computer Science


Share