Document Open Access Logo

An Efficient Algorithm to Decide Periodicity of b-Recognisable Sets Using MSDF Convention

Authors Bernard Boigelot, Isabelle Mainz, Victor Marsault, Michel Rigo



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.118.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Bernard Boigelot
Isabelle Mainz
Victor Marsault
Michel Rigo

Cite AsGet BibTex

Bernard Boigelot, Isabelle Mainz, Victor Marsault, and Michel Rigo. An Efficient Algorithm to Decide Periodicity of b-Recognisable Sets Using MSDF Convention. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 118:1-118:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICALP.2017.118

Abstract

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.
Keywords
  • integer-base systems
  • automata
  • recognisable sets
  • periodic sets

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Jean-Paul Allouche, Narad Rampersad, and Jeffrey Shallit. Periodicity, repetitions, and orbits of an automatic sequence. Theoret. Comput. Sci, 410:2795-2803, 2009. Google Scholar
  2. Jean-Paul Allouche and Jeffrey Shallit. Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, 2003. Google Scholar
  3. 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. Google Scholar
  4. 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. Google Scholar
  5. Valérie Berthé and Michel Rigo, editors. Combinatorics, Automata and Number Theory. Number 135 in Encyclopedia Math. Appl. Cambridge University Press, 2010. Google Scholar
  6. Bernard Boigelot and Julien Brusten. A generalization of Cobham’s theorem to automata over real numbers. Theor. Comput. Sci., 410(18):1694-1703, 2009. Google Scholar
  7. 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. Google Scholar
  8. Bernard Boigelot, Isabelle Mainz, Victor Marsault, and Michel Rigo. An efficient algorithm to decide periodicity of b-recognisable sets using MSDF convention, 2017. Preprint URL: https://arxiv.org/abs/1702.03715.
  9. 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. Google Scholar
  10. 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. Google Scholar
  11. Emilie Charlier, Narad Rampersad, and Jeffrey Shallit. Enumeration and decidable properties of automatic sequences. Int. J. Found. Comput. Sci., 23(5):1035-1066, 2012. Google Scholar
  12. Alan Cobham. On the base-dependence of sets of numbers recognizable by finite automata. Mathematical Systems Theory, 3(2):186-192, 1969. URL: http://dx.doi.org/10.1007/BF01746527.
  13. Fabien Durand. Decidability of the HD0L ultimate periodicity problem. RAIRO - Theor. Inf. and Applic., 47(2):201-214, 2013. Google Scholar
  14. Juha Honkala. A decision method for the recognizability of sets defined by number systems. ITA, 20(4):395-403, 1986. Google Scholar
  15. 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. Google Scholar
  16. 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. Google Scholar
  17. Ivan Mitrofanov. A proof for the decidability of HD0L ultimate periodicity (in Russian). Preprint arXiv:1110.4780, 2011. Google Scholar
  18. Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009. Google Scholar
  19. Robert E. Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput., 1(2):146-160, 1972. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail