Drag Rewriting

Nachum Dershowitz (1, 2) , Jean-Pierre Jouannaud (3, 4) , Fernando Orejas (5)

1 TAU-CS - School of Computer Science
2 TAU - Tel Aviv University
3 DEDUCTEAM - Deduction modulo, interopérabilité et démonstration automatique
4 Université Paris-Saclay
5 UPC - Universitat Politècnica de Catalunya = Université polytechnique de Catalogne [Barcelona]

We present a new and powerful algebraic framework for graph rewriting, based on drags, a class of graphs enjoying a novel composition operator. Graphs are embellished with roots and sprouts, which can be wired together to form edges. Drags enjoy a rich algebraic structure with sums and products. Drag rewriting naturally extends graph rewriting, dag rewriting, and term rewriting models.

Mots clés: Graph rewriting; drags; cyclic composition; rewriting; drag morphisms

Domaines: Informatique [cs]; Mathématiques [math]

Nachum Dershowitz, Jean-Pierre Jouannaud, Fernando Orejas. Drag Rewriting. 2023. ⟨hal-04143346v4⟩