Decision problem; Utilmately periodic set; recognizable set of integers; automatic sequence; numeration system
Abstract :
[en] Consider a non-standard numeration system like the one built over the Fibonacci sequence where nonnegative integers are represented by words over {0,1} without two consecutive 1. Given a set X of integers such that
the language of their greedy representations in this system is accepted by a finite automaton, we consider the problem of deciding whether or not X is a finite union of arithmetic progressions. We obtain a decision procedure for this problem, under some hypothesis about the considered numeration system. In a second part, we obtain an analogous decision result for a particular class of abstract numeration systems built on an infinite regular language.
Disciplines :
Computer science Mathematics
Author, co-author :
Bell, Jason; Simon Fraser University - SFU > Department of Mathematics
Charlier, Emilie ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Fraenkel, Aviezri; Weizmann Institute of Science (Israël) > Department of Computer Science & Applied Mathematics
Rigo, Michel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
B. Alexeev, Minimal DFAS for testing divisibility, J. Comput. Syst. Sci. 69 (2004) 235-243.
J.-P. Allouche and J. Shallit, Automatic sequences, Theory, Applications, Generalizations (Cambridge University Press, Cambridge, 2003).
J.-P. Allouche, N. Rampersad and J. Shallit, Periodicity, repetitions, and orbits of an automatic sequence, Theoret. Comput. Sci. 410 (2009) 2795-2803.
A. Bertrand-Mathis, Comment ́ecrire les nombres entiers dans une base qui n'est pas entìere, Acta Math. Acad. Sci. Hungar. 54 (1989) 237-241.
P. B. Bhattacharya, S. K. Jain and S. R. Nagpaul, Basic Abstract Algebra, 2nd edn. (Cambridge University Press, Cambridge, 1994).
J. Bonin, L. Shapiro and R. Simion, Some q-analogues of the Schr̈oder numbers arising from combinatorial statistics on lattice paths, J. Statist. Plann. Inference 34 (1993) 35-55.
V. Bruỳere and G. Hansel, Bertrand numeration systems and recognizability, Latin American Theoretical INformatics (Valparáí so, 1995), Theoret. Comput. Sci. 181 (1997) 17-43.
E. Charlier and M. Rigo, A decision problem for ultimately periodic sets in nonstandard numeration systems, Mathematical Foundations of Computer Science 2008 (Torún), Lecture Notes Comput. Sci.5162 (Springer-Verlag, 2008), pp. 241-252.
E. Charlier, M. Rigo and W. Steiner, Abstract numeration systems on bounded languages and multiplication by a constant, INTEGERS: Elec. J. of Combin. Number Theory 8(1) (2008) A35.
F. R. K. Chung and R. L. Graham, On irregularities of distribution of real sequences, Proc. Nat. Acad. Sci. USA 78 (1981) 4001.
F. R. K. Chung and R. L. Graham, On irregularities of distribution, Finite and Infinite SetsI, II (Eger, 1981), pp. 181-222.
A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata, Math. Systems Theory 3 (1969) 186-192.
F. Durand, A theorem of Cobham for non primitive substitution, Acta Arithmetica 104 (2002) 225-241.
H. T. Engstrom, On sequences defined by linear recurrence relations, Trans. AMS 33 (1931) 210-218.
G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence sequences, Mathematical Surveys and Monographs104 (American Mathematical Society, Providence, RI, 2003).
A. S. Fraenkel, Systems of numeration, Amer. Math. Monthly 92 (1985) 105-114.
A. S. Fraenkel, On the recurrence fm+1 = bmfm - fm-1 and applications, Discrete Math. 224 (2000) 273-279.
A. S. Fraenkel, Arrays, numeration systems and Frankenstein games, Theoret. Comput. Sci. 282 (2002) 271-284.
A. S. Fraenkel and S. T. Klein, Novel compression of sparse bit-strings - preliminary report, Proc. NATO Advanced Research Workshop on Combinatorial Algorithms on Words, eds. A. Apostolico and Z. Galil, Maratea, Italy, June 1984 (Springer-Verlag, Heidelberg, 1985), pp. 169-183.
C. Frougny, On the sequentiality of the successor function, Inform. Comput. 139 (1997) 17-38.
C. Frougny, Representations of numbers and finite automata, Math. Systems Theory 25 (1992) 37-60.
C. Frougny and B. Solomyak, On the representation of integers in linear numeration systems, in Ergodic theory of Zd actions (Warwick, 1993-1994), London Math. Soc. Lecture Note Ser.228 (Cambridge Univ. Press, Cambridge, 1996), pp. 345-368.
F. Q. Gouv̂ea, p-Adic Numbers: An Introduction, 2nd edn. (Springer, 1997).
T. Harju and M. Linna, On the periodicity of morphisms on free monoids, RAIRO Inform. Th́eor. Appl. 20 (1986) 47-54.
M. Hollander, Greedy numeration systems and regularity, Theory Comput. Syst. 31 (1998) 111-133. (Pubitemid 128342341)
J. Honkala, A decision method for the recognizability of sets defined by number systems, Theoret. Inform. Appl. 20 (1986) 395-403.
J. Honkala, M. Rigo, Decidability questions related to abstract numeration systems, Discrete Math. 285 (2004) 329-333.
N. Koblitz, p-Adic Numbers, p-adic Analysis, and Zeta-Functions (Springer-Verlag, New York, 1977).
P. B. A. Lecomte and M. Rigo, Numeration systems on a regular language, Theory Comput. Syst. 34 (2001) 27-44.
J. Leroux, A polynomial time presburger criterion and synthesis for number decision diagrams, 20th IEEE Symposium on Logic in Computer Science (LICS 2005), Chicago, IL, USA, IEEE Computer Society (2005), pp. 147-156.
M. Lothaire, Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications90 (Cambridge University Press, Cambridge, 2002).
A. A. Muchnik, The definable criterion for definability in Presburger arithmetic and its applications, Theoret. Comput. Sci 290 (2003) 1433-1444.
J.-J. Pansiot, Decidability of periodicity for infinite words, RAIRO Inform. Th́eor. Appl. 20 (1986) 43-46.
G. Rauzy, Relations de ŕecurrence modulo m, Śeminaire Delange-Pisot-Poitou, Th. Nombres 5 (1963-1964).
M. Rigo, Numeration systems on a regular language: Arithmetic operations, recognizability and formal power series, Theoret. Comput. Sci. 269 (2001) 469-498.
M. Rigo and A. Maes, More on generalized automatic sequences, J. Autom. Lang. Comb. 7 (2002) 351-376.
J. Sakarovitch, ́ Elements de th́eorie des automates, Vuibert (2003). English translation: Elements of Automata Theory (Cambridge University Press), to appear.
C. D. Savage and A. J. Yee, Euler's partition theorem and the combinatorics of -sequences, J. Combinat. Theory, Ser. A 155 (2008) 967-996.
J. Shallit, Numeration systems, linear recurrences and regular sets, Inform. Comput. 113 (1994) 331-347.
M. Ward, The arithmetical theory of linear recurring series, Trans. Amer. Math. Soc. 35 (1933) 600-628.
E. Zeckendorf, Repŕesentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Lìege 41 (1972) 179-182.
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
