Systèmes de réécritures orthogonaux non effacants et linéaires droite : application au problème de Zantema

Résumé : Nous étudions les systèmes de réécriture orthogonaux, non effaçants et linéaires droite. On montre que si un terme clos est normalisable alors il est fortement normalisable et que toutes ses normalisations ont le même longueur. On définit ensuite la linéarité pour des redex internes et la sortie d'un redex interne, on montre que si telles sorties ont une taille bornée alors la linéarité pour des redex internes est équivalente à la linéarité. Ces résultats permettent de donner une preuve inductive et élémentaire la linéarité du système de Zantema. On montre, ensuite, par une technique de dichotomie par marquage en avant, la conjecture de Zantema à savoir que le système de Zantema a un facteur de linéarité 2.
Type de document :
Rapport
[Rapport de recherche] RR-2202, INRIA. 1994
Liste complète des métadonnées

https://hal.inria.fr/inria-00074468
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 15:22:13
Dernière modification le : samedi 17 septembre 2016 - 01:06:53
Document(s) archivé(s) le : mardi 12 avril 2011 - 17:06:11

Fichiers

Identifiants

  • HAL Id : inria-00074468, version 1

Collections

Citation

Elias Tahhan Bittar. Systèmes de réécritures orthogonaux non effacants et linéaires droite : application au problème de Zantema. [Rapport de recherche] RR-2202, INRIA. 1994. 〈inria-00074468〉

Partager

Métriques

Consultations de la notice

152

Téléchargements de fichiers

52