Causal graph rewriting: Space-time determinism and reversibility
Tuesday 2 December 2025 at 10h30
Amphi building 660 and online
Abstract: We study non-terminating graph rewriting models, whose local rules are applied non-deterministically---and yet enjoy a strong form of determinism, namely space-time determinism. For terminating computation, it is well-known that the property of confluence may ensure a deterministic end result. In the context of distributed, non-terminating computation however, confluence alone is too weak a property. In this thesis we provide sufficient conditions so that asynchronous local rule applications produce well-determined events in the space-time unfolding of the graph, regardless of their application orders.
Then we move to the question of reversibility, which is an essential property to have in the quantum setting. In the mathematical tradition, reversibility requires that the evolution of a dynamical system be a bijective function. In the context of graph rewriting, however, the evolution is not even a function, because it is not even deterministic---as the rewrite rules get applied at non-deterministically chosen locations. Physics, by contrast, suggests a more flexible understanding of reversibility in space-time, whereby any two closeby snapshots (aka `space-like cuts'), must mutually determine each other. We formalise this notion of space-time reversibility, and then study reversible graph rewriting. We establish sufficient, local conditions on the rewrite rules so that they be space-time reversible.
Throughout this talk, we give examples that are asynchronous simulations of dynamical systems, and other which feature time dilation, in the spirit of general relativity, as a prime illustration of a phenomenon that is fundamentally asynchronous yet gives rise to a consistent space-time.
The defense will be in English.
Jury:
- Enrico FORMENTI, University of Nice-Sophia Antipolis - Reviewer
- Cyril BRANCIARD, University Grenoble Alpes - Reviewer
- Évelyne CONTEJEAN, University Paris-Saclay
- Sara RIVA, University of Lille
- Simon PERDRIX, University of Loraine
- Vilasini VENKATESH, University Grenoble Alpes
- Pablo ARRIGHI, University Paris-Saclay - Supervisor
- Luidnel MAIGNAN, University Paris-East Créteil - Supervisor