A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems

Bell, Jason; Charlier, Emilie; Fraenkel, Aviezri; Rigo, Michel

doi:10.1142/S0218196709005330

Reference : A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems


	Document type :	Scientific journals : Article
	Discipline(s) :	Engineering, computing & technology : Computer science Physical, chemical, mathematical & earth Sciences : Mathematics
	To cite this reference:	http://hdl.handle.net/2268/15910

Title :	A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems
Language :	English
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 >]
Publication date :	2009
Journal title :	International Journal of Algebra and Computation
Publisher :	World Scientific Publishing Company
Volume :	19
Pages :	809-839
Peer reviewed :	Yes (verified by ORBi)
Audience :	International
ISSN :	0218-1967
Keywords :	[en] 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.
Target :	Researchers ; Professionals ; Students
Permalink :	http://hdl.handle.net/2268/15910
DOI :	10.1142/S0218196709005330

File(s) associated to this reference

Fulltext file(s):

	File	Commentary	Version	Size	Access
Restricted access	bcfr.pdf	No commentary	Author preprint	275.5 kB	Request copy

All documents in ORBi are protected by a user license.

Dspace v1.5