Article (Scientific journals)
A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems
Bell, Jason; Charlier, Emilie; Fraenkel, Aviezri et al.
2009In International Journal of Algebra and Computation, 19, p. 809-839
Peer Reviewed verified by ORBi
 

Files


Full Text
bcfr.pdf
Author preprint (282.11 kB)
Request a copy

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
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
Publication date :
2009
Journal title :
International Journal of Algebra and Computation
ISSN :
0218-1967
Publisher :
World Scientific Publishing Company
Volume :
19
Pages :
809-839
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 02 July 2009

Statistics


Number of views
181 (40 by ULiège)
Number of downloads
16 (14 by ULiège)

Scopus citations®
 
12
Scopus citations®
without self-citations
5
OpenCitations
 
8

Bibliography


Similar publications



Contact ORBi