Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 10 min ago
PreprintCC BY 4.0arXiv

Causal graph rewriting

  • Pablo Arrighi
  • Marin Costes
  • Luidnel Maignan
Open at sourcePDFDOICite

Abstract

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 *-local and *-extensive. We also formalise and prove the simulation of any one-dimensional cellular automaton.

Related

  1. Epidemiological Causal Graph Identification: Challenges, Identifiability and Algorithms
    Sambit Mishra, Yingying Wang, Christine K. Johnson +1
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  2. CausalGrade: Evidence-Guided Causal Graph Scoring with Jev
    Jiangming Zhong, Jiawei Zhu, Guanting Wu +3
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  3. Graph-Split Bayesian Causal Forest for Spatial Heterogeneous Treatment Effect Estimation
    Shuren He, Huiyan Sang, Ligang Lu
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  4. The tableaux monoid: a rewriting-theoretic approach
    Nohra Hage
    arXivPreprintCC BY-NC-SA 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  5. Extended Frege proofs, circuits and rewriting
    Jan Krajicek
    arXivPreprintCC BY 4.0Full textLogic & foundationsarXiv

Cite

BibTeXRIS
BibTeX
@misc{arrighi2026causal,
  title = {{Causal graph rewriting}},
  author = {Pablo Arrighi and Marin Costes and Luidnel Maignan},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.25188},
  eprint = {2609.25188},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.25188},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Causal graph rewriting
AU  - Pablo Arrighi
AU  - Marin Costes
AU  - Luidnel Maignan
PY  - 2026
DA  - 2026/09/21
PB  - arXiv
DO  - 10.48550/arxiv.2609.25188
UR  - https://arxiv.org/abs/2609.25188
AB  - 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 *-local and *-extensive. We also formalise and prove the simulation of any one-dimensional cellular automaton.
ER  -