Search

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. Of course in the case of terminating computation it is well-known that the mess introduced by asynchronous rule applications may not matter to the end result, as confluence conspires to produce a unique normal form. In the context of non-terminating computation however, confluence is a very weak property, and (almost) synchronous rule applications is always preferred e.g. when it comes to simulating dynamical systems. Here we provide sufficient conditions so that asynchronous local rule applications conspire to produce well-determined events in the space-time unfolding of the graph, regardless of their application orders. Our first example is an asynchronous simulation of a dynamical system. Our second example features time dilation, in the spirit of general relativity.

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 been proven for different classes of models such as mesh refinements from computer graphics, Lindenmayer systems from morphogenesis modeling and cellular automata from biological, physical and parallel computation modeling.The Global Transformation formalism achieves this by using category theory for its genericity, and more precisely the notion of Kan extension to determine the global behaviors based on the local ones.On the other side, Causal Graph Dynamics describe the transformation of port graphs in a synchronous and deterministic way and has not yet being tackled.In this paper, we show the precise sense in which the claim of Global Transformations holds for them as well.This is done by showing different ways in which they can be expressed as Kan extensions, each of them highlighting different features of Causal Graph Dynamics.Along the way, this work uncovers the interesting class of Monotonic Causal Graph Dynamics and their universality among General Causal Graph Dynamics.

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 data structures that can be captured as presheaves and study the computational aspects of such synchronous rule systems.To obtain an online algorithm, a complete study of the sub-steps within each synchronous step is done at the semantic level.This leads to the definition of accretive rule systems and a local criterion to characterize these systems.Finally an online computation algorithm for theses systems is given.

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 a previous paper, we applied it to the Firing Squad Synchronization Problem. In this paper, we show that the approach is not tied to this problem by applying it to the class of Real-Time Sequence Generation problems. We improve in particular on the generation of n 3 sequence by using local mappings to obtain millions of 5state solution, one of them using 58 transitions. It is based on the solution of Kamikawa and Umeo that uses 6 states and 74 transitions. Then, we explain in which sense even bigger classes of problems can be considered.

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 through the categorical notion of Kan extension. In fact, the two possible ways to do such an extension and the ingredients involved in their definition are related through Kan extensions in many ways. These relations provide additional links between computer science and category theory, and also give a new point of view on the famous Curtis-Hedlung theorem of cellular automata from the extended topological point of view provided by category theory. These relations provide additional links between computer science and category theory. No prior knowledge of category theory is assumed.

We want to replace categories, functors and natural transformations by categories, open functors and open natural transformations. In analogy with open dynamical systems, the adjective open is added here to mean that some external information is taken into account. For the particular use of the authors, such an open functor is described by two components: a presheaf representing the possible external influences for each input, and a classical functor from the category of elements of this presheaf to the category of results. Considering the appropriate notion of composition then leads to a bicategory. This report describes this bicategory with as little auxiliary constructions as possible and gives all the details of all the proofs needed to establish the bicategory, as explicitly as possible. Subsequent reports will give other presentations of this bicategory and compare it to other existing constructions, e.g. spans, fibrations, pseudoadjunctions, Kleisli bicategories of pseudo-monads, and profunctors (or distributors).

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. This notion is used to explore solutions of the Firing Squad Synchronization Problem that are minimal both in time (2n -- 2 for n cells) and, up to current knowledge, also in states (6 states). While only one such solution was proposed by Mazoyer since 1987, 718 new solutions have been generated by Clergue, Verel and Formenti in 2018 with a cluster of machines. We show here that, starting from existing solutions, it is possible to generate millions of such solutions using local simulations using a single common personal computer.