One-rule length-preserving rewrite systems and rational Transductions
Résumé
We address the problem to know whether the relation induced by a one-rule length-preserving rewrite system is rational. We partially answer to a conjecture of Éric Lilin who conjectured in 1991 that a one-rule length-preserving rewrite system is a rational transduction if and only if the left-hand side u and the right-hand side v of the rule of the system are not quasi-conjugate or are equal, that means if u and v are distinct, there do not exist words x, y and z such that u=xyz and v=zyx. We prove the only if part of this conjecture and identify two non trivial cases where the if part is satisfied.
Nous étudions le problème de la caractérisation des systèmes de réécriture à une règle préservant les longueurs pour lesquels la relation re réécriture associée est rationnelle. Nous répondons partiellement à une conjecture d'Éric Lilin de 1991 stipulant qu'un système de réécriture à une règle préservant les longueurs est une transduction rationnelle si et seulement si la partie gauche u et la partie droite v de l'unique règle de réécriture du système ne sont pas quasi-conjugués ou u et v sont égaux, c'est à dire que si u et v sont différents, il n'existe pas trois mots x, y et z tels que u = xyz et v = zyx. Nous montrons que la condition est nécessaire et nous identifions deux cas significatifs pour lesquels la condition est suffisante.