algebraic-rewriting

name	algebraic-rewriting
description	Category-theoretic graph rewriting with DPO, SPO, and SqPO pushouts for C-Sets. Declarative transformation of acset data structures.
metadata	{"trit":-1,"color":"#0BAD20"}

Algebraic Rewriting

Overview

AlgebraicRewriting.jl is a Julia library for performing category-theoretic rewrites over C-Sets and other Catlab.jl data structures.

Rewriting Approaches

Type	Description	Use Case
DPO	Double Pushout	Safe deletion (no dangling edges)
SPO	Single Pushout	Greedy deletion
SqPO	Sesqui-Pushout	Cloning + deletion

Core Concepts

Rewrite Rules

A rewrite rule consists of:

• L (left) - Pattern to match
• K (interface) - What to preserve
• R (right) - Replacement pattern

using AlgebraicRewriting

# Define a rule: merge two vertices
L = @acset Graph begin V=2; E=1; src=[1]; tgt=[2] end
K = @acset Graph begin V=1 end
R = @acset Graph begin V=1 end

rule = Rule(L, K, R)

Apply Rewriting

G = @acset Graph begin
    V = 4
    E = 3
    src = [1, 2, 3]
    tgt = [2, 3, 4]
end

# Find matches and rewrite
matches = homomorphisms(L, G)
G′ = rewrite(rule, G, matches[1])