diegosouzapw 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])
Double Pushout (DPO)
L ←─ K ─→ R
↓ ↓ ↓
G ←─ D ─→ H
The context D ensures no "dangling edges" after deletion.
Sesqui-Pushout (SqPO)
Supports cloning via the final pullback complement:
# Clone a vertex
L = @acset Graph begin V=1 end
K = @acset Graph begin V=1 end
R = @acset Graph begin V=2 end
clone_rule = Rule(L, K, R; type=:SqPO)
Gay.jl Integration
# sRGB boundary learning with rewriting seed
gay_seed!(0xabfca37b6b4bc699)
# Forward mode autodiff
∂params = Enzyme.gradient(Forward, loss, params, seed)
Documentation
- Full Documentation
- Brown 2022 - Theoretical foundation
Repository
- Source: plurigrid/AlgebraicRewriting.jl (fork of AlgebraicJulia)
- Seed:
0xabfca37b6b4bc699 - Index: 496/1055
- Color: #c25d0b
GF(3) Triad
algebraic-rewriting (-1) ⊗ acsets-hatchery (0) ⊗ gay-monte-carlo (+1) = 0 ✓
Related Skills
acsets-hatchery- ACSet data structurestopos-adhesive-rewriting- Adhesive categoriesdpo-rewriting- Graph transformationworld-a- AlgebraicJulia ecosystem
SDF Interleaving
This skill connects to Software Design for Flexibility (Hanson & Sussman, 2021):
Primary Chapter: 3. Variations on an Arithmetic Theme
Concepts: generic arithmetic, coercion, symbolic, numeric
GF(3) Balanced Triad
algebraic-rewriting (+) + SDF.Ch3 (○) + [balancer] (−) = 0
Skill Trit: 1 (PLUS - generation)
Secondary Chapters
- Ch4: Pattern Matching
- Ch10: Adventure Game Example
Connection Pattern
Generic arithmetic crosses type boundaries. This skill handles heterogeneous data.