Terminaison des systèmes concurrents / Romain Demangeon ; sous la dir. de Daniel Hirschkoff et de Davide Sangiorgi

Date :

Editeur / Publisher : [S.l.] : [s.n.] , 2010

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : anglais / English

Statistique

Méthodes formelles (informatique)

Hirschkoff, Daniel (19..-.... ; chercheur en informatique) (Directeur de thèse / thesis advisor)

Sangiorgi, Davide (1964-....) (Directeur de thèse / thesis advisor)

École normale supérieure de Lyon (2010-...) (Organisme de soutenance / degree-grantor)

École doctorale en Informatique et Mathématiques de Lyon (Ecole doctorale associée à la thèse / doctoral school)

Università degli studi (Bologne, Italie) (Organisme de cotutelle / degree co-grantor)

Résumé / Abstract : Cette thèse propose une étude de la terminaison dans les systèmes concurrents. La terminaison est une propriété désirable pour les programmes en elle même et comme prérequis pour d'autres propriétés. La cadre du pi calccul est présente dans la section 2. Dans la section 3, des systèmes de types de bases sur le poids sont présentés. Dans la section 4, on montre comment utiliser des approches pour aborder la question de la terminaison des langages concurrents d'ordre supérieur. Dans la section 5, on propose une étude de la complexité du problème de l'inférence pour les analyses basées sur le poids. La section 6 présente brièvement des analyses sémantiques de la terminaison. La section 7 s'intéresse à l'étude de la terminaison d'un pi-calcul impur composé d'un noyau fonctionnel et de constructions impératives. Une nouvelle technique de preuve par élagage est développée. Enfin, on illustre l'efficacité de cette technique en montrant comment elle peut-être appliquée à un lambda calcul avec références.

Résumé / Abstract : This thesis proposes a study of termination for concurrent languages. Termination is a key-property for concurrent programs. It is useful in itself and as a prerequisite for other properties. The framework of the pi-calculus is presented in section 2. Some existing weight-based type systems as well as new refinments are presented in Section 3. Section 4 is dedicated to results about termination in higher-order concurrent calculi where the [m]essages exchanges are pieces of code. Section 5, we propose a study of the complexity of the inference problem for the weight-based type systems. In section 6, termination techniques based on logical relations are presented. Section 7 contained results about the termination of an impure pi-calculus where a functional core is distinguished from the imperative constructs. A new pruning technique is used for the soundness proof. A last chapter illustrates the efficiency of this new method by ensuring terrmination in a impure lambda-calculi.