9 papers
Causal graph rewriting
Pablo Arrighi, Marin Costes, Luidnel Maignan
We introduce causal graph rewriting, a model of computation in which local rules are applied on directed acyclic graphs in an asynchronous manner. The non-determinism arising from…
Space-time reversible graph rewriting
Pablo Arrighi, Marin Costes, Luidnel Maignan
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…
Space-time deterministic graph rewriting
Pablo Arrighi, Marin Costes, Gilles Dowek +1
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. O…
Causal Graph Dynamics and Kan Extensions
Luidnel Maignan, Antoine Spicher
On the one side, the formalism of Global Transformations comes with the claim of capturing any transformation of space that is local, synchronous and deterministic. The claim has b…
Millions of 5-State n^3 Sequence Generators via Local Mappings
Tien Nguyen, Luidnel Maignan
In this paper, we come back on the notion of local simulation allowing to transform a cellular automaton into a closely related one with different local encoding of information. In…
Cellular Automata and Kan Extensions
Alexandre Fernandez, Luidnel Maignan, Antoine Spicher
In this paper, we formalize precisely the sense in which the application of cellular automaton to partial configuration is a natural extension of its local transition function thro…
Accretive Computation of Global Transformations
Alexandre Fernandez, Luidnel Maignan, Antoine Spicher
Global transformations form a categorical framework adapting graph transformations to describe fully synchronous rule systems on a given data structure.In this work we focus on dat…
The Bicategory of Open Functors
Alexandre Fernandez, Luidnel Maignan, Antoine Spicher
We want to replace categories, functors and natural transformations by categories, open functors and open natural transformations. In analogy with open dynamical systems, the adjec…
Exploring Millions of 6-State FSSP Solutions: the Formal Notion of Local CA Simulation
Tien Thao Nguyen, Luidnel Maignan
In this paper, we come back on the notion of local simulation allowing to transform a cellular automaton into a closely related one with different local encoding of information. Th…