Aspects algorithmiques et implémentation dans des calculs locaux

Abstract

Dans cette thèse nous nous intéressons aux aspects algorithmiques des calculs locaux dans les domaines de la synchronisation et du contrôle de l’exécution. Nous introduisons, entre autre, deux synchroniseurs dont l'un se base sur l'utilisation de l'algorithme de Y. Shi, B. Szymanski et N. Prywest et l'autre sur l'application des marches aléatoires dans les graphes. Ensuite, nous utilisons le concept des réductions de graphes pour présenter un algorithme capable de reconnaitre des propriétés de graphes a l'aide des calculs locaux. Cette étude introduit la notion de systèmes de réduction pratiques (handy reduction systems) qui nous permet de démontrer que toutes les propriétés de graphes de largeur arborescente bornée, définissable en logique monadique du second ordre, peuvent être reconnues par les calculs locaux. Nous établissons un lien directe entre les systèmes de réduction pratiques et le concept de reconnaisseurs de graphes avec connaissance structurelle (labeled graph recognizers). Ce lien nous permet de donner les conditions nécessaires pour qu'une propriété caractérisée par un système de réduction pratique soit reconnue au moyen de calculs locaux. Enfin, nous introduisons le langage de programmation des calculs locaux (Lidia). Ce langage est base sur un système de transition a deux niveaux ou les préconditions de chaque transition sont exprimées par la logique Gam. En se servant des propriétés descriptives de Gam, nous établissons la complétude du langage Lidia.