2013/01/12 by Victor Marsault, Marsault, Victor, Jacques Sakarovitch +1
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Logic, programming, and type systems #semigroups and automata theory
paper · doi:10.48550/arxiv.1301.2691
openalex publication_date 2013/01/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is decidable if a set of numbers, whose representation in a base b is a regular language, is ultimately periodic. This was established by Honkala in 1986. We give here a structural description of minimal automata that accept an ultimately periodic set of numbers. We then show that it can verified in linear time if a given minimal automaton meets this description. This thus yields a O(n log(n)) procedure for deciding whether a general deterministic automaton accepts an ultimately periodic set of numbers.