Reference : A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems
Scientific journals : Article
Engineering, computing & technology : Computer science
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/15910
A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems
English
Bell, Jason [Simon Fraser University - SFU > Department of Mathematics >]
Charlier, Emilie mailto [Université de Liège - ULg > 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 mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
2009
International Journal of Algebra & Computation
World Scientific Publishing Company
19
809-839
Yes (verified by ORBi)
International
0218-1967
[en] Decision problem ; Utilmately periodic set ; recognizable set of integers ; automatic sequence ; numeration system
[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.
Researchers ; Professionals ; Students
http://hdl.handle.net/2268/15910
10.1142/S0218196709005330

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Restricted access
bcfr.pdfNo commentaryAuthor preprint275.5 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.