Réécriture causale de graphe : Déterminisme spatio-temporel et réversibilité

Dans cette thèse, nous proposons un modèle de réécriture de graphes non-terminant, dont les règles locales sont appliquées de manière non déterministe — mais qui bénéficie d’une forme de déterminisme, dit spatio-temporel. Pour les calculs terminants, il est bien connu que la propriété de confluence garantit un résultat final déterministe. En revanche, dans le cadre du calcul distribué et non-terminant qui nous occupe, la confluence seule est une propriété bien trop faible. Nous fournissons des conditions suffisantes pour que les applications locales de règles asynchrones produisent des événements bien déterminés dans le dépliement spatio-temporel du graphe, indépendamment de l’ordre dans lequel elles sont appliquées. Nous abordons ensuite la question de la réversibilité, propriété essentielle dans le cadre quantique. Dans la tradition mathématique, la réversibilité exige que l’évolution d’un système dynamique soit une fonction bijective. Dans le contexte de la réécriture de graphes, cependant, l’évolution n’est même pas une fonction, car elle n’est pas déterministe --- les règles de réécriture étant appliquées en des lieux choisis de façon non déterministe. La physique, en revanche, suggère une compréhension plus flexible de la réversibilité en espace-temps, selon laquelle deux configurations proches doivent se déterminer mutuellement. Nous formalisons cette notion de réversibilité espace-temps, puis nous étudions ses propriétés. Nous finissons par établir des conditions locales suffisantes sur les règles de réécriture pour qu’elles soient réversibles en espace-temps. Tout au long de ce travail, nous donnons des exemples de simulations asynchrones de systèmes synchrone d'une part, et d'autre part des exemples authentiquement asynchrones mettant en évidence une dilatation temporelle, dans l’esprit de la relativité générale.