Reference : Monoïde syntaxique et numérations
Scientific congresses and symposiums : Unpublished conference
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/125589
Monoïde syntaxique et numérations
English
[en] Syntactic monoid and numeration systems
Charlier, Emilie mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
Jun-2012
No
Yes
International
Journées Machines à états finis et Combinatoire, 5èmes Journées du groupe de travail SDA2
du 11 juin 2012 au 13 juin 2012
LITIS
Rouen
France
[fr] complexité en nombre d'états ; complexité syntaxique ; numération
[en] ensemble d'entiers périodique
[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.
Researchers
http://hdl.handle.net/2268/125589

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
Charlier-expose-Rouen2012.pdfAuthor preprint370.06 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.