• Langue : Français
• Discipline : Informatique
• Identifiant : Inconnu
• Type de thèse : Doctorat
• Date de soutenance : 01/01/1984

Résumé en langue originale

Les systèmes de réécriture s'imposent comme un modèle simple et général pour les "règles de calcul", donc pour définir et étudier la sémantique des langages de programmation, leur implémentation, les calculs dans les types d'objets. Les règles linéaires ont de nombreuses bonnes propriétés que n'ont pas les règles générales (travaux de Huet, Guttag, Dershowitz, Jouannaud). Nous définissons ici deux notions de simulation (forte et faible) d'un système de réécriture S par un autre S'. Nous montrons que tout système de réécriture peut être simulé, même au sens fort, par un système de réécriture linéaire, mais que l'on perd alors soit la confluence, soit l'uniforme terminaison. Dualement, nous introduisons une mesure de complexité sur les système de réécriture qui met en évidence le "trou de complexité" séparant un système de réécriture quelconque d'un système de réécriture linéaire qui le simule.