Reference : An efficient algorithm to decide periodicity of b-recognisable sets using MSDF convention
Scientific congresses and symposiums : Paper published in a journal
Engineering, computing & technology : Computer science
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/212135
An efficient algorithm to decide periodicity of b-recognisable sets using MSDF convention
English
Boigelot, Bernard mailto [Université de Liège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique >]
Mainz, Isabelle mailto [Université de Liège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Dép. d'électric., électron. et informat. (Inst.Montefiore) >]
Marsault, Victor mailto [Université de Liège > Département de mathématique > Mathématiques discrètes >]
Rigo, Michel mailto [Université de Liège > Département de mathématique > Mathématiques discrètes >]
Aug-2017
Leibniz International Proceedings in Informatics
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
80
Yes
No
International
1868-8969
Germany
The 44th International Colloquium on Automata, Languages, and Programming
Du 10 juillet 2017 au 14 juillet 2017
University of Warsaw
Warsaw
Pologne
[en] Integer-base systems ; Automata ; Recognisable sets ; Periodic sets
[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.
Mathématiques ; Montefiore Institute of Electrical Engineering and Computer Science - Montefiore Institute
European Union -- Marie Sklodowska-Curie fellowship
Researchers
http://hdl.handle.net/2268/212135
10.4230/LIPIcs.ICALP.2017.118
Long version at : https://arxiv.org/abs/1702.03715

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
HonkalaMSDF_v5.pdfAuthor preprint520.88 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.