Source-linked AI summary
From Border-Agnosticism to Causal Rewrite Systems
Pablo Arrighi, Marin Costes, Luidnel Maignan
TL;DR
Causal graph rewriting uses asynchronous local updates on evolving graphs, but its local-rule definition retains an axiomatic dynamical-systems style. This paper treats borders as missing information and establishes border-agnostic conditions under which local rules can be represented as causal rewrite systems; it also identifies remaining global conditions and future questions for reversibility.
Problem
Extensivity alone does not ensure that a neighbourhood selected on a partial graph remains unchanged when information beyond its borders is revealed.
Source: §1 · p. 2Method
The paper imposes border-agnostic neighbourhood schemes and uses their structural properties to represent local rules by pattern substitutions in causal rewrite systems.
Source: §1 · p. 2, §6 · p. 15Results
Border-agnostic neighbourhood schemes correspond exactly to mutex sets of cones, and local rules correspond exactly to causal rewrite systems.
Source: §1 · p. 2, §6 · p. 15Takeaways & Limitations
The characterization provides a basis for studying reversibility through unique pattern matching and possible local, constructive reversibility criteria.
Source: §5 · p. 14Causal rewrite systems still require acyclicity and finite-chain conditions that the paper identifies as candidates for replacement by local criteria.
Source: §5 · p. 14
Abstract
from arXiv · showhide
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.
1 Introduction
Causal graph rewriting combines asynchronous updates with local rules defined in an axiomatic, dynamical-systems style. Reading borders as missing information motivates border-agnostic neighbourhoods, which provide structure for representing local rules as causal rewrite systems.
Taking borders seriously
- Causal graph rewriting uses asynchronous updates, directed edges for connectivity and event dependencies, and time-tagged vertices representing events.A local rule consumes a ready event and rewrites a neighbourhood; updates may be scheduled freely.Source: §1 · p. 1
- Its neighbourhood schemes require extensivity, which implies idempotence but does not ensure that selections remain stable as information is revealed beyond borders.The paper argues that this earlier condition alone does not provide the structure needed for its rewriting-system formulation.Source: §1 · p. 2
- Border-agnostic neighbourhood schemes select the same neighbourhood when a graph containing the selected disk reveals more information.This restriction is equivalent to a safety principle and yields disk uniqueness and, on border-completable graph sets, disk-completability.Source: §1 · p. 2
- Local rules correspond exactly to causal rewrite systems, while border-agnostic neighbourhood schemes correspond exactly to mutex sets of cones.The results are stated as a representation theorem for neighbourhood schemes and local rules.Source: §1 · p. 2
2 Causal graphs and local rules
Causal graph rewriting operates on directed acyclic labelled port graphs, which can represent partial views of events and their dependencies. Its local rules act on neighbourhood disks and preserve the rest of the graph as context.
2.1 Graphs and locality
- Graphs are directed acyclic labelled port graphs whose internal vertices carry states and whose border vertices have unknown states.A vertex t.x represents an event: a process at position x with time tag t.Source: §2.1 · p. 3
- Induced subgraphs retain edges touching internal vertices, while adjacent vertices outside the selected set become border vertices.Partial composition, when defined, forms the least common supergraph of two induced subgraphs.Source: §2.1 · p. 4, Figure 1 · p. 4
- The graph family is closed under renaming, induced-subgraph inclusion, and disjoint union, supporting the operations used in the framework.Renamings make vertex names immaterial and are required to commute with the considered graph structures and rules.Source: §2.1 · p. 4
2.2 Neighbourhood schemes and local rules
- A neighbourhood scheme selects a cone around a position; its disks are the neighbourhoods extracted from graphs in the scheme’s domain.Extensivity makes a disk unchanged when the scheme is applied to it again.Source: §2.2 · p. 5
- A local rule replaces the selected disk while leaving the rest of the graph unchanged, preserving the disk’s border and commuting with renamings.Idempotence means the rule is determined by its action on disks.Source: §2.2 · p. 5
3 Borders as missing information
The paper treats border vertices as markers of missing information, requiring graph families to admit completions and neighbourhoods to remain stable when information beyond a disk becomes available. These constraints yield safety, disk uniqueness, and disk-completability results that support the later rewriting-system treatment.
3 Borders as missing information
- Border vertices represent unexplored edge continuations, not graph endpoints; the framework therefore assumes graphs can be completed and neighbourhoods are border-agnostic.Border-agnosticism requires any graph containing a selected disk to select that same disk at the position.Source: §3 · p. 6
3.1 Stability under added information
- Completing a disk can change an extensive neighbourhood, as the rounded-neighbourhood example selects additional vertices in the larger graph.The safety principle excludes a smaller graph from the scheme’s domain when it does not yet contain the neighbourhood selected in a larger view; it is equivalent to border-agnosticism.Source: §3.1 · pp. 6–7
3.2 Structural consequences
- Under border-completion, border-agnosticism is equivalent to disk uniqueness, which ensures at most one disk at each position for unambiguous pattern matching.Border-agnosticism also implies disk-completability: every disk is a neighbourhood in a graph where all its vertices are internal.Source: §3.2 · p. 8
- Disk-completability does not imply border-agnosticism; neighbourhoods selected only at global borders can change in every completion.In the example, a disk selected at the global border omits neighbours that become internal and selected in any completion.Source: §3.2 · p. 9, Figure 3 · p. 9
4 From neighbourhoods to rewrite patterns
The section characterizes border-agnostic neighbourhood schemes through mutex sets of cones, then uses that representation to relate local rules to causal rewrite systems. The two constructions between local operators and causal rewrite systems are inverse.
4.1 Mutex sets of cones
- A border-agnostic neighbourhood scheme corresponds bijectively to a mutex set of cones, whose patterns are conic, unambiguous in any graph, and renaming-invariant.Conversely, a mutex set defines a neighbourhood scheme by selecting its contained pattern when one exists.Source: §4.1 · pp. 10–11
4.2 Rewrite system
- Rules extracted from a border-agnostic local rule form a causal rewrite system; context preservation follows from local-rule structure, with Lemma 2 extending border-edge preservation to every disk.The rule for each disk is determined by the local rule's action on that disk.Source: §4.2 · pp. 11–12
- Conversely, a causal rewrite system induces a local rule that applies the unique matching rewrite and otherwise leaves the graph unchanged; the two constructions are inverse.The replacement conditions ensure the result is a well-defined graph in S.Source: §4.2 · pp. 12–13
Theorem 1 (Equivalence between local operators and causal rewrite
- Theorem 1 gives a bijection between pairs of border-agnostic neighbourhood schemes and local rules, and causal rewrite systems, with the inverse recovering the same rule family.The neighbourhood scheme's disks are exactly the rule patterns.Source: Theorem 1 (Equivalence between local… · pp. 13–14
5 Related work and discussion
The paper connects causal graph rewriting’s axiomatic local rules to traditional pattern-replacement systems. It identifies possible constructive extensions and explains how the characterization may inform reversibility.
5 Related work and discussion
- The paper retains the operational model of asynchronous local updates on dependency DAGs, rather than synchronous global evolution, and strengthens the neighbourhood conditions on which those updates are built [6].Source: §5 · p. 14
- The paper takes the converse route from traditional graph rewriting: it identifies when axiomatic local rules admit explicit pattern-replacement presentations, akin to double-pushout interfaces.Context preservation fixes the borders along which patterns are glued to the surrounding context.Source: §5 · p. 14
- Future work could replace acyclicity and finite-chain conditions with local criteria, and use the characterization to develop constructive reversibility criteria.The authors identify unique pattern matching around each position as a natural reversible-setting requirement.Source: §5 · p. 14
6 Summary and Conclusion
The conclusion establishes border-agnosticism as a condition for context-independent neighbourhoods and connects local rules to causal rewrite systems. This gives causal graph rewriting a pattern-replacement representation, subject to stated structural conditions.
6 Summary and Conclusion
- Border-agnosticism means a disk selects the same neighbourhood in any graph of the set containing it, unlike ordinary extensivity alone.It is equivalent to safety and disk uniqueness; on border-completable graph sets, it also implies disk-completability.Source: §6 · pp. 14–15
- Local rules are in bijection with causal rewrite systems, with context preservation making pattern replacement well defined up to acyclicity and finite chains.The correspondence works in both directions: every local rule induces a system, and every causal rewrite system defines a local rule.Source: §6 · p. 15
- Border-agnostic neighbourhood schemes are in bijection with mutex sets of cones, whose unambiguity corresponds to disk uniqueness.This representation links neighbourhood selection to the paper’s pattern-replacement account of local rules.Source: §6 · p. 15