Reference : Autour des systèmes de numération abstraits
Scientific congresses and symposiums : Unpublished conference
Engineering, computing & technology : Computer science
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/124195
Autour des systèmes de numération abstraits
English
[en] Around abstract numeration systems
Rigo, Michel mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
12-Jun-2012
No
Yes
International
Journées Machines à états finis et Combinatoire (GDR-IM SDA2)
from 11-06-2012 to 13-06-2012
LITIS (Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes)
Rouen
France
[en] Numeration system ; Formal language theory ; Combinatorics on words
[fr] Un système de numération, comme notre système décimal usuel, peut être vu comme une bijection entre l'ensemble des entiers naturels et le langage formé des représentations de ces entiers. Lorsque l'on considère, de façon générale, une numération basée sur une suite strictement croissante d'entiers et pour laquelle les représentations sont obtenues par un algorithme glouton, la bijection qui à un entier associe sa représentation préserve l'ordre naturel. Ainsi, un système de numération abstrait est la donnée d'un langage L infini (le plus souvent régulier) ordonné par ordre généalogique croissant. L'entier n est alors représenté par le n-ième mot du langage L.
L'introduction, il y a une dizaine d'années, de ces systèmes abstraits a été motivée par le théorème de Cobham de 1969 qui s'intéresse aux ensembles reconnaissables d'entiers. Un ensemble X d'entiers est dit S-reconnaissable, pour une numération fixée S, si l'ensemble des représentations dans le système S des éléments de X forme un langage régulier. Ainsi les ensembles S-reconnaissables sont, d'un certain point de vue, particulièrement simples puisque décrits par un automate fini. Le théorème de Cobham stipule que les seuls ensembles d'entiers simultanément reconnaissables pour deux bases entières k et l suffisamment indépendantes, à savoir multiplicativement indépendantes, sont exactement les unions finies de progressions arithmétiques. Ce théorème a été le point de départ de nombreux travaux de recherche au cours de ces quarante dernières années (généralisations à des numérations non standards, à plusieurs dimensions, formalisme logique,... ).
Dans ce survol liant théorie élémentaire des nombres et théorie des automates, nous nous proposons de présenter quelques questions et développements en lien directe avec cette question générale : existe-t-il un lien entre les propriétés arithmétiques des nombres (e.g., carré parfait, nombre premier, critère de divisibilité, ...) et les propriétés syntaxiques de leurs représentations ? Les propriétés décrites par automates finis sont-elles, par exemple, stables en appliquant des opérations arithmétiques élémentaires comme l'addition ou la multiplication par une constante ? Les automates permettent également de tracer des liens avec la combinatoire des mots (suites automatiques au sens d'Allouche et Shallit et plus généralement mots morphiques engendrés par substitution) ou d'exprimer certains problèmes de décision dont la solution revient à étudier la complexité en nombre d'états (state complexity) de certaines familles de langages.
Researchers
http://hdl.handle.net/2268/124195

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
RigoSDA2.pdfAuthor preprint652.49 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.