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

[en] Given an integer base b>1, a set of integers is represented in base b by a language over {0,1,...,b-1}. The set is said to be 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's theorem implies the converse: no other set is b-recognisable in every base b. We are interested in deciding whether a $b$-recognisable set of integers (given as a finite automaton) is eventually periodic. Honkala showed that this problem is 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. In this work, we consider the natural order of digits (Most Significant Digit First) and give a quasi-linear algorithm to solve the problem in this case.

Research center :

Mathématiques
Montefiore Institute - Montefiore Institute of Electrical Engineering and Computer Science - ULiège

Disciplines :

Mathematics
Computer science

Author, co-author :

Boigelot, Bernard ; Université de Liège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique

Mainz, Isabelle ; Université de Liège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Dép. d'électric., électron. et informat. (Inst.Montefiore)

Marsault, Victor ; Université de Liège > Département de mathématique > Mathématiques discrètes

Rigo, Michel ; Université de Liège > Département de mathématique > Mathématiques discrètes

Language :

English

Title :

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

Publication date :

August 2017

Event name :

The 44th International Colloquium on Automata, Languages, and Programming

Event organizer :

University of Warsaw

Event place :

Warsaw, Poland

Event date :

Du 10 juillet 2017 au 14 juillet 2017

Audience :

International

Journal title :

Leibniz International Proceedings in Informatics

ISSN :

1868-8969

Publisher :

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Germany

Volume :

Peer reviewed :

Peer Reviewed verified by ORBi

Funders :

European Union. Marie Skłodowska-Curie Actions [BE]

Commentary :

Long version at : https://arxiv.org/abs/1702.03715

Available on ORBi :

since 23 June 2017

Statistics

Number of views

173 (36 by ULiège)

Number of downloads

83 (21 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

Jean-Paul Allouche, Narad Rampersad, and Jeffrey Shallit. Periodicity, repetitions, and orbits of an automatic sequence. Theoret. Comput. Sci, 410:2795-2803, 2009.
Jean-Paul Allouche and Jeffrey Shallit. Automatic Sequences: Theory, Applications, Generalizations.Cambridge University Press, 2003.
Marie-Pierre Béal and Maxime Crochemore. Minimizing local automata. In M. Fossorier G. Caire, editor, IEEE Int. Symp. on Information Theory, pages 1376-1380, 2007.
Jason Bell, Emilie Charlier, Aviezri S. Fraenkel, and Michel Rigo. A decision problem for ultimately periodic sets in nonstandard numeration systems. IJAC, 19(6):809-839, 2009.
Valérie Berthé and Michel Rigo, editors. Combinatorics, Automata and Number Theory.Number 135 in Encyclopedia Math. Appl. Cambridge University Press, 2010.
Bernard Boigelot and Julien Brusten. A generalization of Cobham's theorem to automata over real numbers. Theor. Comput. Sci., 410(18):1694-1703, 2009.
Bernard Boigelot, Sébastien Jodogne, and Pierre Wolper. An effective decision procedure for linear arithmetic over the integers and reals. ACM Trans. Comput. Log., 6(3):614-633, 2005.
Bernard Boigelot, Isabelle Mainz, Victor Marsault, and Michel Rigo. An efficient algorithm to decide periodicity of b-recognisable sets using MSDF convention, 2017. Preprint arXiv:1702.03715.
V. Bruyère and G. Hansel. Recognizable sets of numbers in nonstandard bases. In R. Baeza- Yates, E. Goles, and P. V. Poblete, editors, LATIN'95: Theoretical Informatics, volume 911 of Lect. Notes Comput. Sci., pages 167-179. Springer, 1995.
V. Bruyère, G. Hansel, C. Michaux, and R. Villemaire. Logic and p-recognizable sets of integers. Bull. Belg. Math. Soc., 1:191-238, 1994. Corrigendum, Bull. Belg. Math. Soc. 1 (1994), 577.
Emilie Charlier, Narad Rampersad, and Jeffrey Shallit. Enumeration and decidable properties of automatic sequences. Int. J. Found. Comput. Sci., 23(5):1035-1066, 2012.
Alan Cobham. On the base-dependence of sets of numbers recognizable by finite automata.Mathematical Systems Theory, 3(2):186-192, 1969. doi:10.1007/BF01746527.
Fabien Durand. Decidability of the HD0L ultimate periodicity problem. RAIRO - Theor.Inf. and Applic., 47(2):201-214, 2013.
Juha Honkala. A decision method for the recognizability of sets defined by number systems.ITA, 20(4):395-403, 1986.
Jérôme Leroux. A polynomial time Presburger criterion and synthesis for number decision diagrams. In LICS 2005, pages 147-156. IEEE Comp. Soc. Press, 2005.
Victor Marsault and Jacques Sakarovitch. Ultimate Periodicity of b-Recognisable Sets: A Quasilinear Procedure. In DLT 2013, number 7907 in Lect. Notes Comput. Sci., pages 362-373. Springer, 2013.
Ivan Mitrofanov. A proof for the decidability of HD0L ultimate periodicity (in Russian).Preprint arXiv:1110.4780, 2011.
Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009.
Robert E. Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput., 1(2):146-160, 1972.