Présentation de l'atelier

Liste des membres permanents de l'atelier

Guesnet Yannick , Maître de Conférence, Université de Rouen
Néraud Jean , Professeur, Université de Rouen
Selmi Carla Maître de Conférence, Université de Rouen

Objectifs

En Informatique Théorique, la recherche autour du concept de mot peut se concevoir selon deux niveaux :
- Le premier niveau consiste en une étude des propriétés des mots menée de manière interactive avec les problématiques des domaines applicatifs : les mots comme outil de modélisation. Se rattachent en particulier à cette méthodologie, les travaux menés en algorithmique du texte et en comparaison des chaînes de caractères, les questions de complexité liées à l'implantation des automates.
- Le second niveau conduit à une investigation plus formelle, plus conceptuelle de la structure des mots. L'objet algébrique de base pour les ensembles de mots est le monoïde libre. Il s'agit de contribuer au développement d'une théorie autonome, la théorie du monoïde libre, au moyen d'une approche mathématique : c'est là l'objectif de l'atelier.
Il est clair que le bien fondé d'une telle recherche ne repose pas sur une stratégie d'inférence immédiate dans les domaines applicatifs. Au contraire, des résultats théoriques forts sont indispensables au développement de tout travail de recherche où les mots sont utilisés comme modèles. Afin de mieux préciser quels peuvent être les enjeux d'une telle recherche, il est utile d'effectuer quelques considérations d'ordre historique.
C'est au début du XX^ème siècle qu'il faut faire remonter les premières études systématiques du concept de mot, avec la publication de trois papiers par le norvégien Axel Thue (1906, 1912, 1914). Quelques décennies plus tard, la notion de mot interviendra comme un des concepts fondamentaux au travers de la théorie combinatoire des groupes (avec le problème de Burnside), de la théories des nombres (le théorème de Van der Waerden's), et de la théorie des semigroupes. Il y a une vingtaine d'années, Marcel Paul Schützenberger formule une série de questions concernant les mots. Par leur spécificité, leur diversité, et leur difficulté, ces questions confirment l'existence d'une théorie du monoïde libre.
Les recherches se poursuivront dans des domaines célèbres : codes, variétés, mots sturmiens, monoïde de traces... La théorie du monoïde libre est un domaine de recherche d'actualité prometteur quant à son avenir scientifique. Évidemment, l'essort d'une telle théorie ne peut être que bénéfique au développement de la recherche appliquée.