Activités de l'atelier

Thèmes de recherche

Une théorie du rang d'un langage

J. Néraud a constitué une théorie du rang d'un langage. Ce concept désigne en fait le nombre minimal de mots pouvant permettre le codage par concaténation de tous les mots du langage.
Cette théorie contient des résultats tant algorithmiques que purement combinatoires [N90, N90.1, N92, N93]. On y établit en particulier la NP-complétude du calcul du rang dans le cas général. Un algorithme très efficace est présenté pour décider si un ensemble est de rang au plus deux.
On étudie également les propriétés du rang, entre autres celles qui sont en liaison avec les opérations entre ensembles.

Localisation d'images homomorphes dans un mot

Après s'être attaché au problème qui consiste à détecter les occurrences d'un motif rationnel dans un mot, J. Néraud étudie le cas plus général de la détection de motifs "avec variables". Le domaine des équations en mots est évidemment directement concerné par une telle recherche. En fait, avant 1994, en dehors de l'Algorithme de Makanin, seule la détection des périodicités dans un mot, c'est-à-dire de facteurs de la forme Xⁿ ou, plus généralement, (XY)ⁿX avait donné matière à publication.
J. Néraud a d'autre part élaboré des algorithmes particulièrement efficaces pour résoudre une classe particulière d'équations en mots [N94]. D'autres algorithmes permettent la détection de toutes les occurrences de motifs arbitraires ayant au plus deux variables [N95]. Ces algorithmes reposent sur une étude particulièrement délicate des propriétés combinatoires des images homomorphes. Dans tous les cas toutes les solutions sont fournies.
Dans le cas d'un motif arbitraire, J. Néraud introduit un second concept de rang, afin de mesurer la complexité de la reconstruction d'un mot en terme de périodicités. Ceci lui a permis des améliorations substantielles de l'algorithme général [N95.1, N97].

Localisation de motifs rationnels dans un texte

On sait que pour détecter des motifs rationnels dans un texte, les algorithmes de complexité les plus faibles appliquent une phase de prétraitement qui concerne exlusivement le motif. La machine ainsi construite permet alors, au cours de la phase de traitement appliquée au texte, de localiser toutes les occurrences du motif.
Jusqu'alors, une telle stratégie a surtout été mise en oeuvre pour détecter un mot, ou plus généralement un ensemble fini de mots (voir les algorithmes de Knuth Morris et Pratt, ou Aho et Corasick).

Y. Guesnet s'attache à la détection de motifs concernant les ensembles rationnels infinis. Il obtient en particulier un algorithme efficace pour détecter des motifs de la forme X*, où X est un code bipréfixe à trois élements. L'élaboration de cet algorithme, utilise lui aussi une phase de prétraitement et repose sur des propriétés théoriques fortes des "X-interprétations". Il prolonge en cela une méthode proposée par J. Néraud en 1992 [NC92].

Description combinatoire de la variété des langages testables

C. Selmi a orienté ses travaux de recherche vers une description combinatoire et syntaxique de la variété des langages qui sont à la fois localement testables et testables par morceaux [S96] et d'une sous variété stricte de cette variété [S99]. Le problème de la décidabilité de l'appartenance d'un semigroupe fini à une variété de semigroupes finis se révèle d'une importance fondamentale lorque l'on veut traduire les propriétés combinatoires d'un langage en propriétés algébriques de son semigroupe syntaxique. Ce problème est très difficile à résoudre si la variété ne possède pas d'objet libre ou si elle n'est pas décrite par un ensemble d'équations. La théorie des opérations implicites introduite par Banaschewski et Reiterman permet de résoudre parfois ce problème de décidabilité. On associe à chaque variété un semigroupe topologique, dit des opérations implicites, qui joue le rôle de l'objet libre de la variété. La variété est alors décrite par un ensemble d'identités entre opérations implicites et la famille des langages reconnue par la variété peut être caractérisée en utilisant les ouverts-fermés du semigroupe topologique associé.

Théorie des codes

Une des questions essentielles de cette théorie est de caractériser la maximalité d'une famille de codes. Dans ce domaine, on connaît l'importance des travaux de Marcel Paul Schützenberger en ce qui concerne les codes préfixes, bipréfixes et à délai de déchiffrage fini. Pour de tels codes, s'il sont finis, la maximalité est équivalente à la complétude.

Structure des mots incomplétables

Si un code n'est pas complet, on ne sait pas caractériser la structure des mots qui ne sont pas complétables. J. Néraud et C. Selmi répondent à cette question dans le cas des codes à délai de déchiffrage fini [NS01].

Sur les ensembles localement complets

Un sous-ensemble X du monoïde libre A*, est localement complet si il existe un code Y qui vérifie la propriété suivante : Y* est un sous-ensemble de F(X*) (l'ensemble des facteurs de X*), et Y n'est ni X ni A.

J. Néraud et C. Selmi établissent une caractérisation particulièrement efficace des ensembles très coupants localement complets (c'est à dire ceux pour lesquels il existe un mot de X qui n'est pas facteur F(X)). Cette caractérisation conduit à un algorithme de décision polynomial pour la complétude locale d'un ensemble fini. On en déduit un algorithme polynomial pour décider la décomposabilité des codes finis maximaux. [NS02].

Maximalité d'un code dans un sous-monoï de arbitraire de A*

Soit un sous-monoïde M de A* , les notions de M-maximalité, M-complétude, etc.. généralisent de manière très naturelles les notions qui sont introduites dans le monoïde libre A*.

C. Selmi et J. Néraud établissent une extension à ces notions du résultat de Schützemberger :
Étant donné un code M-coupant X, X est M-complet si et seulement si il est M-maximal.
Notre preuve permet, en particulier, une nouvelle démonstration du résultat de Schützemberger, et qui ne fait pas usage de la notion de mesure de Bernoulli [NS03].

C. Selmi et J. Néraud établissent également la caractérisation suivante des codes préfixes (resp. bifixes) M-complets:
Étant donné un code préfixe (resp bifixe) X M-coupant, inclus dans M. X est M-complet si, et seulement si il est complet sur le plus petit sous-monoïde unitaire à gauche (resp. bi-unitaire) qui le contient.

Codes d.i.f.

Y. Guesnet s'intéresse ici à l'étude d'une nouvelle famille de codes satisfaisant des propriétés fortes relatives aux interprétations. Ces familles ne doivent cependant pas être trop restrictives quant aux codes qu'elles permettent d'engendrer.

C'est dans ce cadre que Y. Guesnet introduit les codes à délai d'interprétation fini (ou codes d.i.f.). Il s'attache à montrer que cette nouvelle famille de codes satisfaisait les propriétés classiques des codes déjà introduits dans la littérature comme le théorème du défaut [G00]. Cette recherche débouche sur un algorithme de calcul de l'enveloppe d.i.f. d'un ensemble quelconque. Il situe les codes d.i.f. par rapport à quelques familles de codes bien connues comme les codes circulaires et les codes uniformément synchronisant.

Codes maximaux.

Une part très importante de la théorie des codes consiste en l'étude des codes maximaux.
Y. Guesnet montre que les codes d.i.f. satisfont de très intéressantes propriétés permettant de relier les codes d.i.f. complets aux codes d.i.f. maximaux [G02].
Ceci amène naturellement Y. Guesnet à considérer les propriétés des codes maximaux selon les différentes classes de codes déjà connues. En particulier il répond à une question posée par A. De Luca et A. Restivo, concernant l'existence d'un code circulaire maximal dans la classe des codes circulaires et non maximal dans la classe des codes [G01.3]. Y. Guesnet donne également des exemples répondant à la question dans le cas des codes bifixes, préfixes et suffixes [G01.2].

Thèses

Yannick Guesnet a soutenu sa thèse de Doctorat le 18 mai 2001 [G01.1].
Composition du Jury :
Rapporteurs : Véronique Bruyère (Univ. Mons, Belgique), Christian Choffrut (Univ. Paris 7), Michel Latteux (Univ. Lille 1).
Examinateurs : Jean Berstel (Univ. Marne la Vallée), Jean-Paul Allouche (Univ. Orsay), Jean-Pierre Duval (Univ. Rouen), Pavel Goralcik (Univ. Rouen).
Directeur : Jean Néraud.

Relations avec les autres universités

Organisation des Conférences "WORDS".

Le cycle des conférences biennales "WORDS" a été inauguré à Rouen, en Septembre 1997, regroupant ainsi une soixantaine de chercheurs. L'objet principal de ces colloques est de considérer les différentes thématiques de la Théorie des Mots, en insistant sur les aspect mathématiques de base relatifs à la structure, aux propriétés combinatoires et à la complexité des mots. La démarche scientifique que s'est fixé notre atelier s'inscrit donc tout particulièrement dans les objectifs de "WORDS". Une seconde conférence a eu lieu en septembre 1999, une nouvelle fois à Rouen et a regroupé environ 80 participants. Ces deux conférences ont été organisées par Jean Néraud.

Les comptes rendus des conférences de 1997 et 1999 ont étés publiés dans le bulletin de l'EATCS (European Association for Theoretical Computer Science).

Édition de deux numéros spéciaux de la revue Theoretical Computer Science

À l'issue de chacune des conférences "WORDS", Jean Néraud a organisé la publication d'un numéro spécial de la revue Theoretical Computer Science, exclusivement consacré aux thématiques de recherche présentées dans la conférence.
Après référage, 14 articles ont ainsi été sélectionnés en 1998, et 18 en 2000.