Causal graph rewriting

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 asynchrony is disciplined by the oriented edges, which must be understood as both computational dependencies and locality constraints—and are themselves subject to the rewriting. We illustrate the model through two examples: a particle system, and a time-dilation example—reminiscent of general relativity. We study the well-definedness and properties of induced subgraphs and graph composition, which isolate and recombine the region affected by a rewrite. We then study locality with respect to these constructions, showing how a local rewrite preserves positions, borders, and context. Our main result concerns sequential composition: locality extends from single rule applications to arbitrary valid sequences, as any local rule is automatically $\ast$-local and $\ast$-extensive. We also formalise and prove the simulation of any one-dimensional cellular automaton.