Séminaire APRRSS

Complexité Causale des Processus

12/04/2018
Intervenant(s) : Romain Demangeon (APR)
On étudie la complexité des processus du pi-calcul en termes de quantité de transitions causée par un message initial, en fonction du contenu de ce message.
D'abord, on intègre la caractérisation des fonctions récursives de la classe Polytime de Bellantoni-Cook au système de types de Deng-Sangiorgi pour la terminaison dans le pi-calcul. Ensuite, on définit une notion de complexité pour les processus basée sur une sémantique causale (à la Degano-Priami) qui identifie des dépendances entre des transitions entrelacées. Enfin, on applique une analyse de flot d'information aux processus typés pour s'assurer d'une borne de complexité polynomiale sur les messages produits.
Le système est décidable (et partiellement implémenté en OCaml), correct (une requête reçue par un processus typé cause un nombre de messages borné par un polynôme en le contenu de la requête) et complet (chaque fonction récursive de Polytime peut être calculée par un processus typable).
L'exposé introduit le pi-calcul asynchrone, la terminaison en pi-calcul et la caractérisation des fonctions récursives polytime avant de présenter les résultats susmentionnés.

romain.demangeon (at) nulllip6.fr
Mentions légales
Carte du site