Université Lille1 - Sciences et Technologies Simulation linéaire de systèmes de réécriture 005.13 Arbres (théorie des graphes) Réécriture, Systèmes de (informatique) Text Electronic Thesis or Dissertation fr 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. application/pdf 1 : 1 Mo https://pepite-depot.univ-lille.fr/LIBRE/Th_Num/1984/50376-1984-321.pdf Comité Francesco, De 1900-01-01 11340929X 1984-01-01 Informatique Université Lille1 - Sciences et Technologies 026404184 Doctorat non oui ddc:000 ASCII PDF 9999