# Efficient algorithm to decide the periodicity of b-recognisable sets using MSDF convention

Submitted by sleroux on Wed, 18/01/2017 - 12:32

Victor Marsault

University of Liège

Friday, 24 February, 2017 - 16:00

Salle Solvay (NO, 5th floor)

language over {0,1,...,b-1}. The set is said b-recognisable if its

representation is a regular language. It is known that eventually periodic sets

are b-recognisable in every base b, and Cobham theorem imply the converse:

no other set is b-recognisable in every base b.

We are interested here in deciding whether a b-recognisable set of integers

(given as a finite automaton) is eventually periodic. Honkala first showed this

problem decidable in 1986 and recent developments give efficient decision

algorithms. However, they only work when the integers are written with the

least significant digit first.

On the contrary, we consider here the natural order of digits (Most Significant

Digit First) and give a quasi-linear algorithm to solve the problem in this

case.