système de numération; problème de décision; ensemble ultimement périodique
Abstract :
[fr] Nous utilisons constamment des nombres entiers. Pour les manipuler facilement, nous les représentons par des mots. Dans ce cadre, nous pouvons voir un système de numération comme une bijection rep : N → L entre l'ensemble des naturels N et un ensemble de mots L, appelé langage. Étant donné un ensemble X de naturels tel que le langage rep(X) de ses représentations gloutonnes dans ce système de numération est accepté par un automate fini, nous considérons le problème de décider si X est ultimement périodique ou non ; c'est-à-dire si X est une union finie de progressions arithmétiques. Nous obtenons une procédure de décision pour ce problème sous une hypothèse concernant le système de numération considéré.
Disciplines :
Mathematics
Author, co-author :
Vandomme, Elise ; Université de Liège > Département de mathématique > Mathématiques discrètes
Language :
French
Title :
Problème de décision pour les ensembles ultimement périodiques dans un système de numération non-standard
Alternative titles :
[en] Decision problem for ultimately periodic sets in a non-standard numeration system
Defense date :
25 June 2010
Institution :
ULiège - Université de Liège
Degree :
Master en sciences mathématiques à finalité approfondie
Promotor :
Rigo, Michel ; Université de Liège - ULiège > Département de mathématique