Ultimate periodicity problem for linear numeration systems

Charlier, Emilie; Massuir, Adeline; Rigo, Michel; Rowland, E.

doi:10.1142/S0218196722500254

Download

Article (Scientific journals)

Ultimate periodicity problem for linear numeration systems

Charlier, Emilie; Massuir, Adeline; Rigo, Michel et al.

2022 • In International Journal of Algebra and Computation, 32, p. 561-596

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/290293

DOI
10.1142/S0218196722500254

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

2007.08147.pdf

Author preprint (679.41 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

automata theory; Decision problem; linear recurrent sequence; numeration system; p-adic valuation; Mathematics (all); General Mathematics

Abstract :

[en] We address the following decision problem. Given a numeration system U and a U-recognizable subset X of N, i.e. the set of its greedy U-representations is recognized by a finite automaton, decide whether or not X is ultimately periodic. We prove that this problem is decidable for a large class of numeration systems built on linear recurrence sequences. Based on arithmetical considerations about the recurrence equation and on p-adic methods, the DFA given as input provides a bound on the admissible periods to test.

Disciplines :

Mathematics

Author, co-author :

Charlier, Emilie ; Université de Liège - ULiège > Mathematics

Massuir, Adeline ; Université de Liège - ULiège > Mathematics

Rigo, Michel ; Université de Liège - ULiège > Département de mathématique

Rowland, E.; Department of Mathematics, Hofstra University, Hempstead, United States

Language :

English

Title :

Ultimate periodicity problem for linear numeration systems

Publication date :

2022

Journal title :

International Journal of Algebra and Computation

ISSN :

0218-1967

Publisher :

World Scientific

Volume :

Pages :

561-596

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://www.worldscientific.com/doi/pdf/10.1142/S0218196722500254

Available on ORBi :

since 05 May 2022

Statistics

Number of views

71 (8 by ULiège)

Number of downloads

39 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

S. Almagor, B. Chapman, M. Hosseini, J. Ouaknine and J. Worrell, Effective divergence analysis for linear recurrence sequences, in 29th Int. Conf. on Concurrency Theory, Vol. 118, eds. S. Schewe et al., (Beijing, China, 2018), pp. 15.
J. Bell, E. Charlier, A. Fraenkel and M. Rigo, A decision problem for ultimately periodic sets in nonstandard numeration system, Internat. J. Algebra Comput. 19(6) (2009) 809-839.
A. Bertrand-Mathis, Comment ecrire les nombres entiers dans une base qui n'est pas entiere, Acta Math. Hungar. 54 (1989) 237-241.
V. Berthe and M. Rigo (eds.), Combinatorics, Automata, and Number Theory, Encycl. Math. and its Appl., Vol. 135 (Cambridge University Press, 2010).
B. Boigelot, I. Mainz, V. Marsault and M. Rigo, An efficient algorithm to decide periodicity of b-recognisable sets using MSDF convention, in 44th Int. Colloquium on Automata, Languages, and Programming, Vol. 80, (Warsaw, 2017), p. 14.
V. Bruyere and G. Hansel, Bertrand numeration systems and recognizability, Theor. Comput. Sci. 181 (1997) 17-43.
V. Bruyere, G. Hansel, Ch. Michaux and R. Villemaire, Logic and p-recognizable sets of integers, Bull. Belg. Math. Soc. Simon Stevin 1 (1994) 191-238.
Y. Bugeaud and G. Kekec, On Mahler's classification of p-adic numbers, Bull. Aust. Math. Soc. 98 (2018) 203-211.
A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata, Math. Syst. Theory 3 (1969) 186-192.
F. Durand, Decidability of the HD0L ultimate periodicity problem, RAIRO Theor. Inform. Appl. 47 (2013) 201-214.
F. Durand and M. Rigo, On Cobham's theorem, in Handbook of Automata, vol. II, Automata in Mathematics and Selected Applications, ed. J.-E. Pin (EMS Press, Berlin, 2021).
A. S. Fraenkel, Systems of numeration, Amer. Math. Mon. 92 (1985) 105-114.
Ch. Frougny, Representations of numbers and finite automata, Math. Systems Theory 25 (1992) 37-60.
Ch. Frougny, On the sequentiality of the successor function, Inform. Comput. 139 (1997) 17-38.
F. Q. Gouvea, p-adic Numbers: An Introduction, 2nd edn., Universitext (Springer-Verlag, Berlin, 1997).
M. Hollander, Greedy numeration systems and regularity, Theory Comput. Syst. 31 (1998) 111-133.
J. Honkala, A decision method for the recognizability of sets defined by number systems, Theor. Inform. Appl. 20 (1986) 395-403.
A. Lacroix, N. Rampersad, M. Rigo and E. Vandomme, Syntactic complexity of ultimately periodic sets of integers and application to a decision procedure, Fund. Inform. 116 (2012) 175-187.
P. B. A. Lecomte and M. Rigo, Numeration systems on a regular language, Theory Comput. Syst. 34 (2001) 27-44.
N. Loraud, β-shift, systemes de numeration et automates, J. Theor. Nombres Bordeaux 7 (1995) 473-498.
M. Marden, The Geometry of the Zeros of a Polynomial in a Complex Variable, Mathematical Surveys, Vol. 3 (American Mathematical Society, New York, 1949).
V. Marsault, An efficient algorithm to decide periodicity of b-recognisable sets using LSDF convention, Log. Methods Comput. Sci. 15 (2019) Paper No. 8, 30.
V. Marsault and J. Sakarovitch, Ultimate periodicity of b-recognisable sets: A quasi-linear procedure, in Developments in Language Theory, Lecture Notes in Computer Science, Vol. 7907 (Springer, Heidelberg, 2013), pp. 362-373.
A. Massuir, Positional numeration systems: Ultimate periodicity, complexity and automatic sequences, Ph.D. thesis, University of Liège (2021), https://orbi.uliege.be/handle/2268/258492.
I. V. Mitrofanov, Almost periodicity of morphic words, Dokl. Math. 93 (2016) 207-210.
J. Ouaknine and J. Worrell, Positivity problems for low-order linear recurrence sequences, in Proc. 25th Annual ACM-SIAM Symp. Discrete Algorithms (ACM, New York, 2014), pp. 366-379.
J. Ouaknine and J. Worrell, Ultimate positivity is decidable for simple linear recurrence sequences, in Automata, Languages, and Programming, Part II, Lecture Notes in Computer Science, Vol. 8573 (Springer, Heidelberg, 2014), pp. 318-329.
M. Rigo, Formal Languages, Automata and Numeration Systems: Applications to Recognizability and Decidability, Networks and Telecommunications Series, Vol. 2 (ISTE-Wiley, 2014).
E. Rowland and R. Yassawi, p-adic asymptotic properties of constant-recursive sequences, Indag. Math. 28 (2017) 205-220.
J. Sakarovitch, Elements of Automata Theory (Cambridge University Press, Cambridge, 2009).
A. Salomaa and M. Soittola, Automata-Theoretic Aspects of Formal Power Series, Texts and Monographs in Computer Science (Springer-Verlag, New York, 1978).
J. Shallit, Numeration systems, linear recurrences and regular sets, Inform. Comput. 113 (1994) 331-347.