Unpublished conference/Abstract (Scientific congresses and symposiums)
Autour des systèmes de numération abstraits
Rigo, Michel
2012Journées Machines à états finis et Combinatoire (GDR-IM SDA2)
 

Files


Full Text
RigoSDA2.pdf
Author preprint (668.15 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Numeration system; Formal language theory; Combinatorics on words
Abstract :
[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.
Disciplines :
Computer science
Mathematics
Author, co-author :
Rigo, Michel  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Autour des systèmes de numération abstraits
Alternative titles :
[en] Around abstract numeration systems
Publication date :
12 June 2012
Event name :
Journées Machines à états finis et Combinatoire (GDR-IM SDA2)
Event organizer :
LITIS (Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes)
Event place :
Rouen, France
Event date :
from 11-06-2012 to 13-06-2012
By request :
Yes
Audience :
International
Available on ORBi :
since 03 June 2012

Statistics


Number of views
151 (12 by ULiège)
Number of downloads
105 (9 by ULiège)

Bibliography


Similar publications



Contact ORBi