Global Transformations: Synchronicity and Locality when Rewriting Graphs and other Spaces

Orateur: Luidnel Maignan
Localisation: Université Paris-Est - Créteil, France
Type: Colloquium de Créteil
Site: UPEC
Salle: P1 021
Date de début: 02/06/2022 - 13:45
Date de fin: 02/06/2022 - 14:45

Two problems happen to lead to the same solution.

First, imagine a dynamical system with states described as graphs.
The evolution is therefore a local update of this graph but what does
that even mean in a synchronous deterministic setting ?
As a node of the graph changes its connection to its neighbors, these
neighbors might decide to disappear for example.
Modification of neighboring nodes, usually considered mutually
exclusive, seems to require extreme care for this to work.
How to formalize the coherence between arbitrary kind of local update of
graphs ?

Second, consider the triangular mesh refinement.
This is indeed a synchronous deterministic evolution of a graph-like
object but how to specify this evolution as local rules ?
It is usually shown with just one rule: a triangle gives a refined group
of 4 triangles.
But programming a framework trying to take such rules as input reveals
that there is in fact a lot of ambiguity in this single rule.
How to formalize the missing information to distinguish between the
different possible interpretations ?

The answer to this last question uncovers the notion of mutual agreement
in systems of local rules on graphs with enough generality to answer the
first question.
The solution applies to any kind of space, this fact being captured
(surprisingly directly) by basic category theory constructions.
This allows to transport intuitions from cellular automata and
Lindenmayer systems to new highly dynamical landscapes.

References sur :
- Accretive Computation of Global Transformations. RAMiCS 2021: 159-175
- Cellular Automata and Kan Extensions. AUTOMATA 2021: 7:1-7:12
- Lindenmayer Systems and Global Transformations. UCNC 2019: 65-78
- Global Graph Transformations. GCM@ICGT 2015: 34-49