PROBLEME DU MOT DES MONOIDES PRÉSENTÉS PAR UN SEUL RELATEU

G. Watier

IBP-Litp 1996/Th/01: THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 Litp / Litp research reports
99 pages - Février/February 1996 - French document.

PostScript : Ko /Kb

Titre / Title: PROBLEME DU MOT DES MONOIDES PRÉSENTÉS PAR UN SEUL RELATEU

Résumé :
€ Soit un monoïde admettant une présentation à un seul relateur
€ < A; u=v >
€ où u et v sont des mots sur l'alphabet A. Il n'a pas encore été montré que le problème du mot d'un tel monoïde soit décidable en toute généralité, bien qu'une conjecture existe dans ce sens.
€ Nous présentons le problème, les approches utiliséeés dans la littératures et celles envisageables. Nous dégageons ensuite des propriétés générales sur certaines factorisations de mots, propriétés qui ont leur intérêt propre dans la combinatoire des mots. Enfin nous appliquons ces dernières à notre problème dans le cas où le mot u est un mot qui ne se chevauche pas avec lui-même. Pour ce cas - qui, nous le verrons, concerne une très large classe de présentations - la meilleure contribution apportée jusqu'ici autorise à décider le problème si le mot u apparaît en facteur dans le mot v. Nous étendons ce résultat en supprimant la contrainte "u apparaît en facteur dans v" sous réserve que la longueur de v soit au moins le carré de celle de u.

Abstract : Let M be a monoid having a single relator presentation
€ < A; u=v >
€ where u and v are words on the alphabet A. Generally speaking, the word problem for M has not yet been proved decidable, though there is a conjecture in this direction.
€ We introduce the problem, the way it has formerly been handled and how it ccould now be treated. Then, we show general properties about some factorisatons of words, properties that have their own interest in combinatorics of words. We apply them to our problem in the case when the word u is not self-overlapping. In this case - which, as we shall show, concerns a large class of presentations - the best contribution up to now states that the word problem is decidable if the word u is a factor of v. We extend this result by suppressing the condition "u is a factor of v" provided that the length of v is at least the square of the length of u.

Publications internes Litp 1996 / Litp research reports 1996