problème de décison; complexité syntaxique; ensemble ultimement périodique
Abstract :
[fr] Nous calculons la cardinalité du monoïde syntaxique du langage 0*rep_b (mN) composé des représentations en base b des multiples d’un entier m. Nous donnons aussi des bornes inférieures sur la complexité syntaxique de tout ensemble (ultimement) périodique d’entiers écrits en base b. Nous appliquons nos résultats à un problème très étudié : décider si un ensemble d’entiers reconnaissable en base b est ultimement périodique ou non. (Travail réalisé avec M. Rigo de l'Université de Liège)
Disciplines :
Mathematics
Author, co-author :
Vandomme, Elise ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
