From Border-Agnosticism to Causal Rewrite Systems

From Border-Agnosticism to Causal Rewrite Systems Pablo Arrighi1 , Marin Costes2 , and Luidnel Maignan3 Université Paris-Saclay, Inria, CNRS, LMF, 91190 Gif-sur-Yvette, France pablo.arrighi@universite-paris-saclay.fr 2 Centre for Quantum Information and Communication, École polytechnique de Bruxelles, Université libre de Bruxelles, 1050 Brussels, Belgium marin.costes@ens-paris-saclay.fr 3 LACL, Univ Paris Est Creteil, 94000 Créteil, France luidnel.maignan@u-pec.fr

arXiv:2610.23351v1 [cs.DM] 16 Oct 2026

1

Abstract. Causal Graph Rewriting was recently introduced as an evolution of Causal Graph Dynamics to allow for a controlled form of asynchronism in these dynamical systems with dynamical graphs. In this context, the notion of borders—akin to dangling edges—has gained increasing importance. In this paper, we re-examine these borders, interpreting them as missing information. This perspective adds structural rigor to the framework, allowing border-agnostic causal graph rewriting to be reformulated as a rewriting system rather than a dynamical system. This shift represents a crucial step toward facilitating the treatment of reversibility. Keywords: Graph rewriting · Local graph dynamics · Neighbourhood schemes · Causality · Renaming invariance

1

Introduction

In a rewrite system, locality is visible in the syntax: a left-hand side is matched and replaced while the context is retained . In the dynamical-systems tradition, on the other hand, locality is often axiomatic. For instance, cellular automata are global maps induced by a uniform local map; causal graph dynamics extend this viewpoint to spaces whose graph structure may itself evolve [2, 8]. This axiomatic presentation is also classical in their quantum extensions [4, 3]. Causal graph rewriting, introduced recently, stands between these two traditions [1, 7]. Updates are asynchronous, and directed edges encode both connectivity and dependencies between events. Vertices carry time tags, and a local rule consumes a ready event and rewrites a neighbourhood. Graphs may be partial views, represented by border edges and border vertices. The link with rewrite theory is the asynchronous regime itself, in which each update may be scheduled freely. The definition of local rules, however, borrows from the axiomatic side: a local rule acting at x on a graph G is a global function of the form Ax G = Ax (GNx ) ⊔ GN x , where GNx is the neighbourhood of x in G and

2

P. Arrighi, M. Costes, L. Maignan

GN x the rest of the graph. The neighbourhood scheme N is only required to be extensive [1, 7] (called extensibility in [3]): restricting a graph to an intermediate view that still contains the selected neighbourhood should produce the same neighborhood. This condition implies idempotence (the neighborhood of a neighborhood is that neighborhood), which is needed to pass to the quantum setting, and it sufficed for the results obtained so far. Taking borders seriously. The main point of this paper is that being careful with the meaning of borders provides a first solid ground to unify causal graph rewriting with traditional graph rewriting and rewrite systems. A border vertex should read as missing information, i.e. a part of the graph that is not known, rather than the end of the graph, in the same spirit as [13]. Extensivity does not respect this reading: it only compares a graph with its subgraphs, so a neighbourhood selected on a partial view may still change when information is revealed beyond its borders. Taking the missing-information reading seriously, we restrict to border-agnostic neighbourhood schemes, which select the same neighbourhood whatever is revealed around it. This restriction is natural: it is equivalent to a safety principle, stating that a local rule cannot act with less information than a neighbourhood. It also yields the two properties needed to present local rules as rewrite systems. First, disk uniqueness: a graph contains at most one disk at each position, so that matching a left-hand side is unambiguous. Second, disk-completability: every disk is the neighbourhood of its position in a graph where all its vertices are internal, so that the structural properties of [7], and in particular the preservation of border edges, hold on every disk. As in graph rewriting, where border edges must be preserved by pattern substitution for the global transformation to be well defined, this allows a uniform description of the action of local rules on disks. Building on these two properties, we show that local rules are exactly the actions of causal rewrite systems, families of pattern substitutions subject to conditions that can mostly be checked rule by rule. Contributions. 1. We introduce border-agnosticism (Def. 9), separate it from extensivity (Ex. 1), and show that it is equivalent to the safety principle (Prop. 1). 2. We show that border-agnosticism is equivalent to disk uniqueness (Lem. 1) and, on border-completable sets of graphs, implies disk-completability (Lem. 2, Ex. 2). The latter removes the extendability premise from the structural properties of local rules of [7]. 3. Our main result is a representation theorem: border-agnostic neighbourhood schemes correspond exactly to mutex sets of cones (Prop. 2), and local rules correspond exactly to causal rewrite systems (Thm. 1). Sec. 2 recalls causal graph rewriting. Sec. 3 introduces border-agnosticism and its consequences. Sec. 4 proves the representation theorem, and Sec. 5 discusses related work.

From Border-Agnosticism to Causal Rewrite Systems

2

3

Causal graphs and local rules

We briefly recall the formalism of causal graph rewriting; a gentler introduction can be found in [7]. 2.1

Graphs and locality

We work with directed acyclic labelled port graphs: edges are attached to ports of the vertices, and each internal vertex carries a state. Labelled port graphs are standard in distributed computing [15, 12, 11], where ports distinguish neighbouring processes and labels represent their states; directed acyclic graphs commonly capture dependencies between processes [10, 14]. A vertex t.x is an event: a process at position x with time tag t. Graphs may be partial views, with border edges linking internal vertices to border vertices, whose states are unknown. Definition 1 (Positions, names, ports, states). Fix a countably infinite set X of positions. Let us denote V := { t.x | (t, x) ∈ Z × X } and call its elements names. We say that u = t.x ∈ V is at position x and denote t′ .u := (t′ + t).x for any t′ ∈ Z. For any subset U ⊆ V, we denote ⌊U ⌋ := { x ∈ X | ∃t ∈ Z, t.x ∈ U } the set of underlying positions. For any X ⊆ X , let us denote X := X \ X. Finally, fix a finite sets of ports π and states Σ. Definition 2 (Graphs). A graph G is given by a tuple (IG , BG , EG , σG ) where: – IG ⊆ V is the set of internal vertices of G, – BG ⊆ V \ IG is the set of border vertices of G, – EG ⊆ (VG : π)2 \ (BG : π)2 is the set of (oriented) edges, and – σG : IG → Σ maps each internal vertex to its state. where we denote by VG := IG ∪ BG the set of all vertices of the graph, and by (V : π) := {v : p | v ∈ V, p ∈ π} the set of ports of some set of vertices V . Moreover the tuple has to be such that: acyclicity: the graph has no cycles. border-attachment: ∀u ∈ BG , ∃(v : a, v ′ : a′ ) ∈ EG , u ∈ { v, v ′ }, i.e. border vertices are connected to at least one edge. port-saturation: ∀(u : a, v : b), (u′ : a′ , v ′ : b′ ) ∈ EG , u : a ̸= v ′ : b′ ∧ (u : a = u′ : a′ ⇔ v : b = v ′ : b′ ), i.e. ports are used only once—so as to distinguish each neighbour. unicity of positions: ∀u, v ∈ VG , ⌊u⌋ = ⌊v⌋ =⇒ u = v, i.e. each position is carried by at most one vertex. finite chains: the graph only contains paths of finite length. We denote by Past(G) ⊆ IG the vertices with no incoming edges and by G the set of all graphs. We call border edges the elements of EG \ (IG : π)2 .

4

P. Arrighi, M. Costes, L. Maignan t5 .x5

t6 .x6

:a

:a :a

:a

t4 .x4

:d

:b

:c

:c

:a t1 .x1

:c

t7 .x7

t6 .x6 :a

t4 .x4

:a

:c

:a :d

:a

:c

:b

t3 .x3

t3 .x3

t0 .x0 :a

:b :a

t2 .x2

t7 .x7

:a t1 .x1

:a

t2 .x2

:b

G

G{x2 ,x3 ,x7 }

Fig. 1. A graph G (left) and its induced subgraph G{x2 ,x3 ,x7 } (right). Border vertices and border edges are dashed. Note how internal vertices of G{x2 ,x3 ,x7 } are exactly x2 , x3 , and x7 . Its border vertices are vertices of the original graph (internal and border) in the immediate vaccinity of x2 ,x3 , and x7 .

The local evolution of these graphs is governed by three main operations. First, for U ⊆ V, the induced subgraph GU has internal vertices IG ∩U and all edges touching one of them; adjacent vertices outside U become border vertices (Fig. 1). We write H ⊑ G when H is an induced subgraph of G. For X ⊆ X , GX denotes induction on names at positions in X. Second, the partial composition G ⊔ H is defined when both are induced subgraphs of a common graph, and is then their least common supergraph; in particular G = GX ⊔ GX for every X ⊆ X . Applications usually restrict to a family of graphs S ⊆ G, which must be closed under the operations used throughout the paper. Finally, names only serve as a description tool; their particular choice in a graph should be immaterial. We therefore consider renamings, and will require considered subset of graphs, neighbourhood schemes and local rules to commute with them. Definition 3 (Renaming). A renaming is a function R : V → V such that R(t.u) = t.R(u) and whose restriction to positions ⌊R(0.−)⌋ : X → X is a bijection of X . It is fully specified by this restriction, and acts on the graphs of Def. 2 by renaming their vertices. Based on these operations, one can restrict evolutions to a subset of graphs, as long as appropriate closure properties preserve their semantics. Definition 4 (Closed subset of graphs). A subset of graphs S ⊆ G is closed if it respects the following three properties. renaming inclusion disjoint-union

If G ∈ S implies R(G) ∈ S where R is a renaming. If G ∈ S implies ∀H ⊑ G, H ∈ S. If G, H ∈ S and ⌊VG ⌋ ∩ ⌊VH ⌋ = ∅ implies G ⊔ H ∈ S.

These are the standard hypotheses of [7]. From now on we fix a closed subset of graphs S, relative to which every statement below is made.

From Border-Agnosticism to Causal Rewrite Systems

2.2

5

Neighbourhood schemes and local rules

A neighbourhood scheme returns the positions considered close to a position x. These positions are not arbitrary: they form a cone of x, much as an event in relativity can only signal within its future light-cone, or as a process sends its result to the processes that depend on it. Definition 5 (Cones). A cone of x is a graph C ∈ S such that x ∈ ⌊Past(C)⌋ and, for every v ∈ IC , there exists a directed path from the vertex at position x to v that lies entirely in IC , a.k.a. accessibility. We denote by Cx the set of cones of x, and by C the set of all cones. Definition 6 ((Extensive) neighbourhood scheme). An (extensive) neighbourhood scheme N is a function which maps any position x ∈ X to a function Nx : Γx → P(X ) on some domain Γx ⊆ S such that for any H ∈ S and G ∈ Γx we have: cone: Nx (G) ⊆ ⌊IG ⌋ and GNx is in Cx . stability: GNx ⊑ H implies H ∈ Γx . extensivity: GNx ⊑ H ⊑ G implies GNx = HNx . renaming-invariance: for all renaming R, we have R(G) ∈ Γ⌊R(x)⌋

and

N⌊R(x)⌋ (R(G)) = ⌊R(Nx (G))⌋.

where we introduced GNx as a shorthand for GNx (G) . We denote SNx := {GNx | G ∈ Γx } the set of disks of x. The disks SNx are the neighbourhoods that can be extracted from graphs of S; they are the building blocks on which local rules are defined. By extensivity, the neighbourhood scheme leaves them unchanged (Rem. 1). Remark 1 (Extensivity implies idempotence). For any disk GNx ∈ SNx , we have (GNx )Nx = GNx . Indeed, stability places GNx in Γx , and extensivity applied to GNx ⊑ GNx ⊑ G then gives Nx (GNx ) = Nx (G). A local rule A(−) acts at x by replacing the disk GNx with Ax GNx , leaving the rest of the graph unchanged. Definition 7 (Local rule). Given some neighbourhood scheme N, an N-local operator A(−) is an operator from X × S to S such that ∀x ∈ X and ∀G ∈ S, A⌊R(x)⌋ (R(G)) = R(Ax G) for every renaming R, and ( Ax G :=

(Ax GNx ) ⊔ GN x G

if G ∈ Γx , otherwise,

where the action of Ax on GNx must preserve the border—i.e. BGNx = BAx GNx . By idempotence, Ax is determined by its action on disks.

6

3

P. Arrighi, M. Costes, L. Maignan

Borders as missing information

We want to read border vertices as missing information, and nothing more: they record edges whose continuation has not been explored, not the end of the graph. To a large extend, this is already the case with the above definition. But taking this reading seriously requires two adjustments of the framework. The first concerns the subset of graphs: missing information should always be possible to fill in. Definition 8 (Border-completable subset of graphs). A subset of graphs S is border-completable when every G ∈ S has a completion, i.e. some H ∈ S such that VG ⊆ IH and G ⊑ H. From now on, S is assumed to be border-completable. The second adjustment concerns neighbourhoods: whatever lies beyond the border vertices of a disk, the neighbourhood should stay the same. Definition 9 (Border-agnostic neighborhood scheme). A neighbourhood scheme N is border-agnostic if and only if for all G ∈ Γx , for all H ∈ S, we have that GNx ⊑ H implies HNx = GNx . This condition looks close to extensivity of Def. 6, but extensivity only compares a graph with its subgraphs, whereas border-agnosticism compares a disk with every graph that contains it. The example below show that the difference matters: an extensive neighbourhood may depend on information added beyond its borders (Sec. 3.1), and may have disks that are selected only when their borders are borders of the whole graph, on which local rules may behave arbitrarily (Sec. 3.2). This example and the following one use the same border-completable closed subset of graphs already considered in [5]. Take ports π = {l, r}, standing for the left and right directions, and let L be the set of infinite line graphs: every edge goes from a port : l to a port : r or from : r to : l, so that the vertices form an infinite line without borders. We let S be the smallest closed subset of graphs containing L; it is border-completable, since the borders of its graphs can always be completed into lines. 3.1

Stability under added information

A first issue with neighbourhoods that are not border-agnostic is that completing a disk may change the neighbourhood. Example 1 (Rounded neighbourhood). Consider the following neighbourhood scheme. Nx attempts to select all vertices in the cone in front of x, but only keeps an even number of vertices (other than x) in each direction (left and right). For instance, in the graph G shown in Fig. 2, Nx selects only x, since there are not enough vertices on the right to form an even number larger than 0. In contrast, on the larger graph H, Nx can select two vertices on the right. This neighbourhood is extensive but not border-agnostic: GNx ⊑ H, but HNx ̸= GNx .

From Border-Agnosticism to Causal Rewrite Systems

G

GNx

H

7

HNx

Fig. 2. The rounded neighbourhood of Ex. 1, is not border-agnostic. In G, x has a single internal vertex on its right, which is therefore not selected: GNx only contains x. In H, which contains GNx , there are two internal vertices on the right of x, and both are selected, whereas the single one on its left is not. Dashed vertices are borders. We do not represent ports here, but they allow us to distinguish between left and right neighbours.

In Ex. 1, completing GNx into H changes the neighbourhood: HNx selects more vertices, so the neighbourhood computed on G depended on information that was missing there. Put differently, once HNx is known to be a neighbourhood, a smaller graph G that contains only part of it cannot know what its border vertices hide, so the neighbourhood should remain undefined on G. We call this requirement the safety principle, and show that it is equivalent to borderagnosticism. Definition 10 (Safety principle). An extensive neighbourhood scheme N obeys the safety principle if, for all G ∈ Γx and all H ⊑ G, GNx ̸⊑ H

=⇒

H∈ / Γx .

That is, if the neighbourhood computed on a larger graph is not yet present in the smaller graph, then the smaller graph is not enough for computing the neighbourhood. Proposition 1 (Border-agnosticism is equivalent to the safety principle). An extensive neighbourhood scheme N is border-agnostic if and only if it obeys the safety principle. Proof. Border-agnosticism implies the safety principle. We prove the contrapositive. Suppose H ∈ Γx and H ⊑ G. Then border-agnosticism gives HNx = GNx , which implies GNx ⊑ H. The safety principle implies border-agnosticism. Let G ∈ Γx and H ∈ S such that GNx ⊑ H. Stability makes HNx defined. Apply the contrapositive of safety to the inclusion GNx ⊑ H. Since GNx is in the domain by stability, it follows that HNx ⊑ GNx . Hence HNx ⊑ GNx ⊑ H, and extensivity applied to H gives HNx = (GNx )Nx . Idempotence concludes that HNx = GNx . ⊔ ⊓ The rounded neighbourhood violates precisely this principle: its stopping decision treats a border as a wall, although the border only denotes missing information.

8

3.2

P. Arrighi, M. Costes, L. Maignan

Structural consequences

The previous section shows how to translate the desire to treat borders as missing information into formal contraints guaranteeing stability under addition of information. The first constraints is on closed subset of graphs that need to be border-completable, and the second one is on neighborhood schemes that need to be border-agnostic. Under these constraints, the framework acquire more structure around the notion of disks. The first two properties that we discuss now are disk uniqueness and disk-completability. Together, they ultimately lead to the study, in the next sections, of local rules from the point of view of rewrite systems. Disk uniqueness states that a graph contains at most one disk at each position, which is readily crucial to the notion of matching a left hand side graph as required by rewrite systems. More interestingly, under border-completion, disk uniqueness is actually equivalent to border-agnosticism. Lemma 1. Border-agnosticism is equivalent to disk uniqueness, i.e. for any border-agnostic neighbourhood scheme N and graph G ∈ Γx , there exists at most one disk D ∈ SNx such that D ⊑ G. Proof. For the first direction, suppose border-agnosticism of the neighborhood scheme, and consider two disks D1 and D2 contained in G. By idempotence i we have DN = Di . Then border-agnosticism gives GNx = Di , which proves x 1 2 D =D . In the other direction, disk uniqueness and the premise of the borderagnonisticism property, namely GNx ⊑ H. By stability, Nx (H) is defined. Since HNx ⊑ H, disk uniqueness concludes that GNx = HNx . As an illustration, the reader can check that Ex. 1, which is not border agnostic, do not have disk uniqueness property. Indeed, in Fig. 2, GNx and HNx are two different disks included in H. Disk-completability In the same way that border-completability asks for every graph to be induced from a bigger graph in which it is completely internal, asking for border-agnocism implies that every disk is a neighborhood at some position of a bigger graph in which it is completely internal. Lemma 2 (Border-agnosticism implies disk-completability). Let N be a border-agnostic neighbourhood scheme. For every disk D ∈ SNx there exists H ∈ S such that VD ⊆ IH and D = HNx . Proof. Closure under inclusion of S gives D ∈ S, and border-completability gives a completion H ∈ S of D, i.e. D ⊑ H and VD ⊆ IH . Idempotence gives DNx = D, and border-agnosticism gives HNx = D.

From Border-Agnosticism to Causal Rewrite Systems

G = GNx

H

9

HNx

Fig. 3. Ex. 2: the graph G = GNx (left), a completion H of G (middle) and its disk HNx (right). The disk HNx is disk-completable: its border vertices are internal in H. The disk GNx is not: in any completion of G, both neighbours of x become internal and are selected.

This implication is not an equivalence. Indeed, Ex. 1 is not border-agnostic but is disk-completable. In the same vain, the following example shows, however, that not all neighborhood schemes are disk-completable. This second kind of behaviour only shows up at global borders, i.e. borders of the whole graph under consideration, beyond which nothing is known. Such borders can always be completed, but some disks are selected only as long as their borders are global: in any completion, the neighbourhood selects something else. If borders only denote missing information, these disks are artefacts, and local rules should not be able to behave specially on them. We illustrate this on the way a local rule acting on a disk handles its border edges, which causal graph rewriting does not force to be preserved. Example 2 (Neighbours if possible). Consider the neighbourhood scheme where Nx selects x together with those of its two neighbours that are internal vertices of the graph. In the graph G of Fig. 3, both neighbours of x are border vertices, so Nx selects only x and GNx = G. In the completion H of G, both neighbours are internal, and Nx selects them as well. This neighbourhood is extensive: if GNx ⊑ H ′ ⊑ G, the selected neighbours are still internal in H ′ , and the others ′ are still border vertices of H ′ , so HN = GNx . It is not disk-completable: in any x ′ ′ completion H of G, both neighbours of x are internal, so HN contains them x and differs from GNx . By Lem. 2, it is therefore not border-agnostic. Other disks are disk-completable, such as HNx , whose border vertices are internal in H.

4

From neighbourhoods to rewrite patterns

4.1

Mutex sets of cones

Our goal is to present local rules as rewrite systems. Their left-hand sides are what the neighbourhood scheme selects, that is, the disks. We therefore characterise the families of graphs Dx that arise as the disks SNx of some borderagnostic neighbourhood scheme. Three conditions are needed. First, Dx contains only cones of x, reflecting the cone condition. Second, a graph contains at most one element of Dx : this unambiguity condition reflects border-agnosticism, which we proved equivalent to having at most one disk at x in any graph (Rem. 1). Third, the family is invariant under renaming, reflecting renaming-invariance.

10

P. Arrighi, M. Costes, L. Maignan

Definition 11 (Mutex). A map D : X → P(C), x 7→ Dx defines a mutex set of cones iff it is conic: Dx ⊆ Cx . unambiguous: ∀x ∈ X , ∀G ∈ S, |{D ∈ Dx | D ⊑ G}| ≤ 1. renaming-invariant: for every renaming R, D⌊R(x)⌋ = {RD | D ∈ Dx }. The disks of a neighbourhood scheme indeed form a mutex set of cones. Lemma 3 (From neighbourhoods to mutex cones). Let N be a borderagnostic neighbourhood scheme. Then the function SN : X → P(C), x 7→ SNx is a mutex set of cones. Proof. By the cone condition, each GNx lies in Cx , so SN is conic . Renaming invariance follows from that of N and from the closure of S under renaming. Unambiguity is Rem. 1, since by stability any graph of S containing a disk at x lies in Γx . Conversely, a mutex set of cones D defines a neighbourhood scheme: in a graph G, the neighbourhood of x is the element of Dx contained in G, when there is one. Definition 12 (Induced neighbourhood scheme). We call ΓxD = {G ∈ S | ∃D ∈ Dx , D ⊑ G} the set of graphs containing some D ∈ Dx . Given a graph G ∈ ΓxD , unambiguity makes this D unique. This allows us to define N D : x 7→ NxD ,

NxD : ΓxD → P(X ),

NxD (G) = ⌊ID ⌋.

The induced scheme is indeed a neighbourhood scheme. Lemma 4 (From mutex cones to neighbourhoods). Let D be a mutex set of cones. Then N D is a well-defined border-agnostic neighbourhood scheme. Proof. Renaming-invariance. Suppose D ∈ Dx and D ⊑ G. Renaming invariance of D and closure of S give RD ∈ D⌊R(x)⌋ and RD ⊑ RG. Unambiguity makes these selected patterns unique, hence RGNxD = RD = (RG)N D

⌊R(x)⌋

.

Cone. The selected D lies in Cx by the cone condition of mutex. Borderagnosticism. If GNxD = D ⊑ H, then H ∈ ΓxD ; unambiguity makes D its unique selected pattern. Thus HNxD = D. The two constructions are inverse of one another.

From Border-Agnosticism to Causal Rewrite Systems

11

Proposition 2 (Equivalence between neighbourhood schemes and mutex sets of cones). The function mapping any border-agnostic neighbourhood scheme N to SN (see Lem. 3) is a bijection between border-agnostic neighbourhood schemes on the one hand, and mutex sets of cones on the other. The inverse associates, to any mutex set of cones D, the neighbourhood scheme N D (see Lem. 4). Proof. Right inverse. Let B be a neighbourhood scheme, we want B = N SB . Let S x ∈ X be a position. First we prove that Γx the domain of Bx is equal to Γx B SB SB the domain of Nx . Let us unravel the definitions. On one side Γx is the set of all graph G such that there exists D ∈ SBx such that D ⊑ G. For all G ∈ Γx S we have GNx ⊑ G and so Γx ⊆ Γx B . Next, by border-agnosticism B is defined S on all graphs containing a disk, so that we also have Γx B ⊆ Γx . SB Then we consider G ∈ Γx = Γx . By definition there exists D ∈ SBx such that D ⊑ G. We then have, by border-agnosticism, G SB = D = GBx from which Nx

B = N SB follows. Left inverse. Now we consider D : x 7→ Dx a mutex set of cones, and we prove that SN D = D. First we check that Dx ⊆ SNxD . By definition of NxD , we have DNxD = D which implies D ∈ SNxD . The reverse inclusion SNxD ⊆ Dx is by definition. 4.2

Rewrite system

By idempotence (Rem. 1), a local rule Ax is determined by the rules {D → Ax D}D∈SNx . Conversely, we want to recover a local rule from such rules alone. But a local rule is defined as a global function on S, so the cup Ax GNx ⊔ GN x is well defined by assumption; a rewrite system only provides the rules, and must instead guarantee that replacing a left-hand side by its right-hand side within any graph yields a well-defined graph. This is the role of context preservation, a local condition checked on each rule alone: it makes the cup of the right-hand side with any context of the left-hand side well defined, up to acyclicity and finite chains, which are global and required separately. Functionality and a mutex domain (Prop. 2) guarantee that at most one update applies at each position; renaming-invariance makes the rules independent of the choice of names; and S-preservation, keeps the result in S. Definition 13 (Causal rewrite system). A set of rewrite rules {Dxj → Gjx }x∈X ,j∈J specifies a causal rewrite system over S iff it is functional: Dxj = Dyk implies (x, j) = (y, k), so that f : Dxj 7→ Gjx is a function; renaming-invariant: f (RDxj ) = R(Gjx ) for every renaming R; mutex-domain: D : x 7→ {Dxj | j ∈ J} defines a mutex set of cones; context-preserving: ⌊IGjx ⌋ ⊆ ⌊IDxj ⌋, BGjx = BDxj , and EGjx \ (IGjx : π)2 = EDxj \ (IDxj : π)2 ;

12

P. Arrighi, M. Costes, L. Maignan

acyclicity and finite chains: whenever Dxj ⊔ H is well defined and lies in S, the union of the edge sets of Gjx and H is acyclic and contains only finite chains; S-preserving: whenever Dxj ⊔ H and Gjx ⊔ H are well defined, Dxj ⊔ H ∈ S =⇒ Gjx ⊔ H ∈ S. To show that the rules {D → Ax D} form a CRS, the main point is context preservation, which follows from the structural properties of local rules established in [7]. Border vertices are preserved by Def. 7, and positions by [7, Lemma 3.26]. Border edges require more: [7, Lemma 3.28] only preserves them on disk-completable disks, and we saw in Sec. 3.2 that some disks with global borders are not. Lem. 2 rules out such disks, so the lemma applies to every disk. Lemma 5 (From local rules to CRS). For any border-agnostic neighbourhood scheme N and N-local rule A(−) , the family of rules {D → Ax D}D∈SNx , x∈X is a causal rewrite system. Proof. It is functional by definition. Prop. 2 gives the mutex domain, and renaming invariance comes from A(−) . Def. 7 preserves border vertices. [7, Lemma 3.26] gives ⌊IAx D ⌋ ⊆ ⌊ID ⌋, and border edges are preserved: Lem. 2 provides H ∈ S with VD ⊆ IH and HNx = D, and applying [7, Lemma 3.28] to H gives EAx D \ (IAx D : π)2 = ED \ (ID : π)2 . Finally, whenever D ⊔ H is well defined and lies in S, border-agnosticism selects D as the neighbourhood of D ⊔ H, so the locality equation reads Ax (D ⊔ H) = Ax D ⊔ H. The left-hand side is a graph in S, hence Ax D ⊔ H is defined, acyclic, of finite chains, and in S because Ax sends S into S. This proves acyclicity, finite chains, and S-preservation. Conversely, a CRS acts at x on a graph G by replacing the left-hand side Dxj contained in G, which is unique by unambiguity, with Gjx ; when G contains no left-hand side at x, it is left unchanged. Definition 14 (Rewriting a graph using a CRS). Consider a causal rewrite R system R = {Dxj → Gjx }x∈X ,j∈J . We define AR (−) : x 7→ Ax , with ∀G ∈ S, ( AR x G=

Gjx ⊔ G⌊I j ⌋

if ∃j ∈ J, G = Dxj ⊔ G⌊I j ⌋ ,

G

otherwise.

Dx

Dx

The conditions of Def. 13 are exactly what is needed for this replacement to be a well-defined graph of S, so that the action is a local rule. Lemma 6 (From CRS to local rules). For any causal rewrite system R = D j {Dxj → Gjx }x∈X ,j∈J , the function AR (−) is a N -local rule, where D : x 7→ {Dx | j ∈ J}.

From Border-Agnosticism to Causal Rewrite Systems

13

Proof. We first show that Def. 14 is well defined. If G ∈ S contains no disk of D at x, the definition returns G. Otherwise, functionality and the mutex condition give a unique image Gjx . Let C = G⌊I j ⌋ , so G = Dxj ⊔ C and the Dx

definition returns Gjx ⊔ C. It remains to prove that this cup is well defined. Context preservation gives ⌊IGjx ⌋ ⊆ ⌊IDxj ⌋, and the decomposition of G gives IDxj ∩ IC = ∅, so the internal vertices of Gjx and of C are disjoint. [7, Lemma 3.10] then characterises well-definedness, with its position clause read as distinct positions (Def. 2). Distinct positions hold as well: by context preservation, every position of Gjx is a position of Dxj , so a position shared with C is carried in Dxj ⊔C by a vertex of both Dxj and C. Either it is a border vertex of Dxj , kept by Gjx since borders are preserved; or it is an internal vertex of Dxj on a border edge, kept by Gjx since border edges are preserved. In both cases Gjx and C carry the same vertex at that position. Dangling coherence and unsaturated ports are the rest of context preservation. Border vertices are unchanged and EGjx \(IGjx : π)2 = EDxj \(IDxj : π)2 , so a border edge of Gjx that meets an internal vertex of C is already a border edge of Dxj , hence lies in C, and symmetrically. The ports used on those common border vertices are the ports of Dxj ⊔ C. Acyclicity and finite chains are the remaining clause of [7, Lemma 3.10]. They are the corresponding hypothesis of Def. 13: since Dxj ⊔ C ∈ S, the union of the edge sets of Gjx and C is acyclic and contains only finite chains. The four clauses hold, so Gjx ⊔ C is well defined. D Finally, AR a border-agnostic neighbourhood (−) is a local rule. Lem. 4 makes N scheme, and the first case of Def. 14 is the locality equation for the disk it selects; outside that domain the action is the identity. The signature S → S follows: on a graph with no disk the value is the graph itself, and once Gjx ⊔ C is well defined, S-preservation yields Gjx ⊔C ∈ S. Renaming invariance is inherited from the rule family, since S is closed under renaming and N D is renaming-invariant. Context preservation gives BGjx = BDxj , so the action preserves the border. Finally, the constructions of Lem. 5 and Def. 14 are inverse of one another. This establishes a formal correspondence between the local rules of causal graph rewriting and rewrite systems in the traditional sense of pattern replacement. Theorem 1 (Equivalence between local operators and causal rewrite systems). The function mapping any pair of a border-agnostic neighbourhood scheme N and a N-local rule A(−) , to the causal rewrite system {D → Ax D}D∈SNx , x∈X is a bijection, whose inverse associates to any causal rewrite system R = {Dxj → Gjx }x∈X ,j∈J the pair formed by N D , with D : x 7→ {Dxj | j ∈ J}, and the N D -local operator AR (−) . Proof. The two constructions are well defined by Lems. 5 and 6. Starting with (N, A), Prop. 2 gives N SN = N. For all x ∈ X and G = Dxj ⊔ GN x , j j AR x G = Gx ⊔ GN = Ax Dx ⊔ GN x

= Ax GNx ⊔ GN = Ax G. x

x

14

P. Arrighi, M. Costes, L. Maignan

j j Starting with R, its induced local rule satisfies AR x Dx = Gx , while the disks D of N are exactly the elements of D. Reconstructing the rule family therefore returns exactly R.

5

Related work and discussion

The graph-dynamics lineage motivating this work starts from causal graph dynamics [2], including reversible and quantum variants [8, 4]. Quantum Network Theory [3] isolates extensibility and idempotence as conditions under which neighbourhood restrictions can be promoted to the quantum setting. Spacetime deterministic graph rewriting [6] replaces synchronous global evolution by asynchronous local updates on dependency DAGs. The present paper does not change that operational model; it strengthens the conditions on neighbourhoods on which they are built. Traditional graph rewriting starts from syntactic rules and formalises their application by constructions such as double-pushout rewriting; modern compositional accounts make interfaces and contexts explicit [9]. Our direction is converse: we start from the axiomatic local rules used for graph dynamics and identify when they admit a pattern-replacement presentation. Causal rewrite systems are a first step towards a double-pushout characterisation of causal graph rewriting: their rules are given by explicit left- and right-hand sides, and context preservation fixes the borders along which they are glued to the context, much as the interface of a double-pushout rule. A first extension would be to replace the acyclicity and finite-chains conditions of causal rewrite systems by local criteria, yielding a fully constructive definition: which pattern substitutions are guaranteed to map DAGs to DAGs? A second extension is reversibility. The present characterisation should be useful there. First, unique pattern matching around each position, which is what border-agnosticism provides, seems a natural requirement in a reversible setting. Second, the local conditions defining causal rewrite systems could lead to local, constructive criteria for reversibility.

6

Summary and Conclusion

We studied neighbourhood schemes in causal graph rewriting, and introduced border-agnosticism (Def. 9): the neighbourhood selected in a disk is the one selected in any graph of S containing it. Extensivity alone does not imply it (Ex. 1). We justified border-agnosticism in three ways. First, it is equivalent to the safety principle, which reads borders as missing information (Prop. 1). Second, it is equivalent to disk uniqueness: any graph contains at most one disk at each position (Rem. 1). Third, it rules out disks whose borders are global, on which local rules may destroy border edges (Ex. 2): on a border-completable subset of graphs (Def. 8), every border-agnostic scheme is disk-completable ( Lem. 2), so the structural properties of [7] hold on every disk.

From Border-Agnosticism to Causal Rewrite Systems

15

Building on these results, we gave a representation of local rules by pattern replacement. Border-agnostic neighbourhood schemes are in bijection with mutex sets of cones (Def. 11, Prop. 2), the unambiguity condition being the counterpart of disk uniqueness. Local rules are in bijection with causal rewrite systems (Def. 13, Thm. 1): every local rule induces one (Lem. 5), and every causal rewrite system defines a local rule (Lem. 6). In the latter direction, context preservation guarantees, up to acyclicity and finite chains, that replacing a pattern in any graph is well defined. Ordinary extensivity is thus sufficient for idempotence, but not for interpreting borders as missing information, nor disks as context-independent left-hand sides; border-agnosticism closes this gap. Data Availability Statement No data are associated with this paper.

References 1. Arrighi, P., Costes, M., Maignan, L., Dowek, G.: Space-time deterministic graph rewriting. In: Proceedings of WRLA 2026, 10 pages. Springer, to appear in LNCS (2026) 2. Arrighi, P., Dowek, G.: Causal graph dynamics. In: Proceedings of ICALP 2012, LNCS. vol. 7392, pp. 54–66 (2012) 3. Arrighi, P., Durbec, A., Wilson, M.: Quantum networks theory. Quantum 8 (2024), pre-print arXiv:2110.10587 4. Arrighi, P., Martiel, S.: Quantum causal graph dynamics. Physical Review D. 96(2), 024026 (2017), pre-print arXiv:1607.06700 5. Arrighi, P., Nesme, V., Werner, R.F.: One-dimensional quantum cellular automata. IJUC 7(4), 223–244 (2011) 6. Arrighi, P., Costes, M., Dowek, G., Maignan, L.: Space-time deterministic graph rewriting (2024), https://arxiv.org/abs/2404.05838 7. Arrighi, P., Costes, M., Maignan, L.: Causal graph rewriting (2026), https:// arxiv.org/abs/2609.25188 8. Arrighi, P., Martiel, S., Perdrix, S.: Reversible causal graph dynamics: invertibility, block representation, vertex-preservation. Natural Computing 19(1), 157–178 (2020), pre-print arXiv:1502.04368 9. Behr, N., Harmer, R., Krivine, J.: Fundamentals of compositional rewriting theory. Journal of Logical and Algebraic Methods in Programming 135, 100893 (2023) 10. Bombelli, L., Lee, J., Meyer, D., Sorkin, R.D.: Space-time as a causal set. Physical review letters 59(5), 521 (1987) 11. Boutillier, P., Maasha, M., Li, X., Medina-Abarca, H.F., Krivine, J., Feret, J., Cristescu, I., Forbes, A.G., Fontana, W.: The kappa platform for rule-based modeling. Bioinformatics 34(13), i583–i592 (2018) 12. Chalopin, J., Das, S., Widmayer, P.: Deterministic symmetric rendezvous in arbitrary graphs: overcoming anonymity, failures and uncertainty. In: Search Theory, pp. 175–195. Springer (2013) 13. Maignan, L., Spicher, A.: Causal graph dynamics and kan extensions. In: Harmer, R., Kosiol, J. (eds.) Graph Transformation - 17th International Conference, ICGT 2024, Held as Part of STAF 2024, Enschede, The Netherlands, July

16

P. Arrighi, M. Costes, L. Maignan

10-11, 2024, Proceedings. Lecture Notes in Computer Science, vol. 14774, pp. 77–96. Springer (2024). https://doi.org/10.1007/978-3-031-64285-2\_5, https: //doi.org/10.1007/978-3-031-64285-2\_5 14. Nishimura, N.: Efficient asynchronous simulation of a class of synchronous parallel algorithms. Journal of Computer and System Sciences 50(1), 98–113 (1995) 15. Papazian, C., Remila, E.: Hyperbolic recognition by graph automata. In: Automata, languages and programming: 29th international colloquium, ICALP 2002, Málaga, Spain, July 8-13, 2002: proceedings. vol. 2380, p. 330. Springer Verlag (2002)

Related documents

• Consistency Without a Global Clock#706740
• Epistemic Infrastructure: Maintained Orders of Actionable Disclosure Under Constraint#95203
• Refutation of “The Impossibility of an Actually Infinite Future” (Wakil Ahmad Hakimi)#165092
• Dialectic of contradiction#87083
• Non-Domination as Error-Correction: Why Independent Reference Preserves Reality-Contact#697146