One-rule length-preserving rewrite systems and rational Transductions

Résumé : 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.
Type de document :
Article dans une revue
RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), EDP Sciences, 2014, 48 (2), pp.149-171. 〈10.1051/ita/2013044〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00934621
Contributeur : Yves Roos <>
Soumis le : mercredi 22 janvier 2014 - 12:59:02
Dernière modification le : jeudi 11 janvier 2018 - 06:20:12

Identifiants

Collections

Citation

Michel Latteux, Yves Roos. One-rule length-preserving rewrite systems and rational Transductions. RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), EDP Sciences, 2014, 48 (2), pp.149-171. 〈10.1051/ita/2013044〉. 〈hal-00934621〉

Partager

Métriques

Consultations de la notice

97