Unpublished conference/Abstract (Scientific congresses and symposiums)
A decision problem for ultimately periodic sets in non-standard numeration systems
Charlier, Emilie
2008Journées de Numération
 

Files


Full Text
abstact Pragues 5-08.pdf
Author preprint (66.29 kB)
Download
Annexes
exposé JN Prague 2008.pdf
Publisher postprint (315.73 kB)
slides de la communication
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Non-standard numeration system; Decidability; Ultimate periodicity
Abstract :
[en] We consider the following decidability problem: Given a linear numeration system U and a set X ⊆ N such that rep_U(X) is recognized by a (deterministic) finite automaton. Is it decidable whether or not X is ultimately periodic, i.e., whether or not X is a finite union of arithmetic progressions? In this work, we give a decision procedure for this problem whenever U is a linear numeration system such that N is U -recognizable and satisfying a relation of the form U_{i+k} = a_1 U_{i+k−1} + · · · + a_k U_i with a_k = ±1 (the main reason for this assumption is that 1 and −1 are the only two integers invertible modulo n for all n ≥ 2).
Disciplines :
Mathematics
Author, co-author :
Charlier, Emilie  ;  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 :
May 2008
Event name :
Journées de Numération
Event place :
Prague, Czechia
Event date :
du 26 mai 2008 au 30 mai 2008
Audience :
International
Available on ORBi :
since 21 June 2012

Statistics


Number of views
36 (4 by ULiège)
Number of downloads
124 (5 by ULiège)

Bibliography


Similar publications



Contact ORBi