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.
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.
