Scientific conference in universities or research centers (Scientific conferences in universities or research centers)
A decision problem for ultimately periodic sets in non-standard numeration systems
Charlier, Emilie
2008
 

Files


Full Text
exposé Louvain 12-08.pdf
Author preprint (380 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Linear numeration system; Decidability
Abstract :
[en] Given a linear numeration system U and a set X (include in N) such that repU(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? Honkala showed that this problem turns out to be decidable for the usual b-ary numeration system (b greater than 2) defined by U_n = bU_{n-1} for n greater than 1 and U_0 = 1. In this work, we give a decision procedure for this problem for a large class of linear numeration systems.
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 :
December 2008
Event name :
Séminaire du groupe de recherche "Large graphs and Networks" de l'UCL
Event place :
Louvain-la-Neuve, Belgium
Event date :
12 décembre 2008
Available on ORBi :
since 20 June 2012

Statistics


Number of views
29 (1 by ULiège)
Number of downloads
90 (1 by ULiège)

Bibliography


Similar publications



Contact ORBi