Skip to Main content Skip to Navigation
Reports

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.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074468
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 3:22:13 PM
Last modification on : Thursday, February 11, 2021 - 2:48:31 PM
Long-term archiving on: : Tuesday, April 12, 2011 - 5:06:11 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

168

Files downloads

69