complexité en nombre d'états; complexité syntaxique; numération; ensemble d'entiers périodique
Abstract :
[fr] La complexité en nombre d'états (state complexity) d'un langage régulier est le nombre d'états de son automate minimal. La complexité syntaxique est le cardinal du monoïde syntaxique associé. La première ne prend en compte que le contexte à droite alors la seconde considère les contextes à gauche et à droite.
Nous nous intéressons aux liens entre les nombres et leurs représentations. Dans le système décimal, un nombre est pair si sa représentation se termine par 0, 2, 4, 6 ou 8, ce qui donne lieu à ensemble de représentations simple, c'est-à-dire reconnu par automate. Plus généralement, dans une base entière, tout critère de divisibilité se traduit par un automate.
Etant donné un ensemble d'entiers, nous voulons répondre aux questions suivantes. Quel est le nombre d'états de l'automate minimal associé. Quelle est la complexité syntaxique associée ? Ces questions s'étendent à des numérations plus générales.
Ces problèmes sont motivés par des problèmes de décidabilité. Par exemple : étant donné un automate reconnaissant un ensemble d'entiers, décider si cet ensemble est ou non ultimement périodique.
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 :
Monoïde syntaxique et numérations
Alternative titles :
[en] Syntactic monoid and numeration systems
Publication date :
June 2012
Event name :
Journées Machines à états finis et Combinatoire, 5èmes Journées du groupe de travail SDA2
