Structured Decompositions Skill

Sheaves on tree decompositions with bidirectional navigation

Version: 1.1.0 Trit: 0 (Ergodic - coordinates decomposition)

bmorphism Contributions

"Compositional Algorithms on Compositional Data: Deciding Sheaves on Presheaves" — ACT 2023, Benjamin Merlin Bumpus et al.

"any computational problem which can be represented as a sheaf with respect to these topologies can be decided in linear time on classes of inputs which admit decompositions of bounded width" — arXiv:2302.05575

Key Insight: Structured decompositions define Grothendieck topologies on categories of data (adhesive categories). This leads to algorithms on objects of any C-set category - structures such as: symmetric graphs, directed graphs, hypergraphs, databases, simplicial complexes, port graphs.

Implementation: Concrete implementations in the AlgebraicJulia ecosystem.

Related to bmorphism's work on:

plurigrid/act - cognitive category theory building blocks
Towards Foundations of Categorical Cybernetics - cybernetic systems via parametrised optics

Core Concept

StrDecomp = Functor d: ∫G → C where:

∫G = category of elements of shape graph
C = target category (Graph, FinSet, etc.)

using StructuredDecompositions

# Create decomposition from graph
d = StrDecomp(graph)

# Access components
bags(d)           # Local substructures
adhesions(d)      # Overlaps (shared boundaries)
adhesionSpans(d)  # Span morphisms

The 𝐃 Functor

Lifts decision problems to decomposition space:

# Define problem as functor
k_coloring(G) = homomorphisms(G, K_k)

# Lift and solve
solution = 𝐃(k_coloring, decomp, CoDecomposition)
(answer, witness) = decide_sheaf_tree_shape(k_coloring, decomp)

Specter-Style Navigation for Decompositions

Bidirectional paths for navigating decomposition structures:

using SpecterACSet

# Navigate bags
select([decomp_bags, ALL, acset_parts(:V)], decomp)

# Navigate adhesions with bidirectional transform
transform([decomp_adhesions, ALL], 
          adh -> reindex_adhesion(adh, mapping), 
          decomp)

Decomposition Navigators

Navigator	Select	Transform
`decomp_bags`	All bag ACSets	Update bags
`decomp_adhesions`	All adhesion ACSets	Update adhesions
`decomp_spans`	Span morphisms	Reindex spans
`adhesion_between(i,j)`	Specific adhesion	Update specific

FPT Complexity

Runtime: O(f(width) × n) where width = max adhesion size

The sheaf condition ensures local solutions glue to global:

# Sheaf condition: sections over overlaps must agree
function verify_sheaf_condition(decomp, local_solutions)
    for (i, j) in adhesion_pairs(decomp)
        adh = adhesion(decomp, i, j)
        s_i = restrict(local_solutions[i], adh)
        s_j = restrict(local_solutions[j], adh)
        s_i == s_j || return false
    end
    return true
end

Integration with lispsyntax-acset

Serialize decompositions to S-expressions for inspection:

# Decomposition → Sexp
sexp = sexp_of_strdecomp(decomp)

# Navigate sexp representation
bag_names = select([SEXP_CHILDREN, pred(is_bag), SEXP_HEAD, ATOM_VALUE], sexp)

# Roundtrip
decomp2 = strdecomp_of_sexp(GraphType, sexp)

Adhesion as Colored Boundary

With Gay.jl deterministic coloring:

using Gay

struct ColoredAdhesion
    left_bag::ACSet
    right_bag::ACSet
    adhesion::ACSet
    color::String  # Deterministic from seed + index
end

function color_decomposition(decomp, seed)
    [ColoredAdhesion(
        bags(decomp)[i],
        bags(decomp)[j],
        adhesion(decomp, i, j),
        Gay.color_at(seed, idx)
    ) for (idx, (i, j)) in enumerate(adhesion_pairs(decomp))]
end

GF(3) Triads

dmd-spectral (-1) ⊗ structured-decomp (0) ⊗ koopman-generator (+1) = 0 ✓
sheaf-cohomology (-1) ⊗ structured-decomp (0) ⊗ colimit-reconstruct (+1) = 0 ✓

Time-Varying Data (Brunton + Spivak Integration)

For DMD/Koopman analysis on decomposed data:

@present SchTimeVaryingDecomp(FreeSchema) begin
    Interval::Ob
    Snapshot::Ob
    State::Ob
    
    timestamp::Hom(Snapshot, Interval)
    observable::Hom(Snapshot, State)
    
    Time::AttrType
    Value::AttrType
end

# Colimit reconstructs dynamics
# DMD = colimit of snapshot diagram over intervals

Julia Scientific Package Integration

From julia-scientific skill - related Julia packages:

Package	Category	Integration
StructuredDecompositions.jl	Core	Sheaves on tree decomps
Catlab.jl	ACSets	Schema definitions
AlgebraicRewriting.jl	Rewriting	Local transformations
Graphs.jl	Networks	Graph decomposition
MetaGraphs.jl	Networks	Attributed graphs
ITensors.jl	Quantum	Tensor network decomp
COBREXA.jl	Bioinformatics	Metabolic network decomp
GraphNeuralNetworks.jl	ML	Message passing on decomps

Cross-Domain Decomposition Patterns

# Metabolic network decomposition
using StructuredDecompositions, COBREXA
model = load_model("ecoli.json")
decomp = tree_decomposition(reaction_graph(model))
local_fba = [fba(submodel) for submodel in bags(decomp)]

# Molecular graph decomposition for ML
using StructuredDecompositions, MolecularGraph, AtomicGraphNets
mol = smilestomol("c1ccccc1")  # benzene
mol_decomp = tree_decomposition(mol)
features = [featurize(bag) for bag in bags(mol_decomp)]

# Quantum tensor network
using StructuredDecompositions, ITensors
tn = tensor_network(circuit)
decomp = mps_decomposition(tn)

References

Bumpus et al. "Structured Decompositions" arXiv:2207.06091
algebraicjulia.github.io/StructuredDecompositions.jl
Nathan Marz: Specter inline caching patterns

Scientific Skill Interleaving

This skill connects to the K-Dense-AI/claude-scientific-skills ecosystem:

Tree Decomposition

etetoolkit [○] via bicomodule

Bibliography References

algorithms: 19 citations in bib.duckdb

Cat# Integration

This skill maps to Cat# = Comod(P) as a bicomodule in the equipment structure:

Trit: 0 (ERGODIC)
Home: Prof
Poly Op: ⊗
Kan Role: Adj
Color: #26D826

GF(3) Naturality

The skill participates in triads satisfying:

(-1) + (0) + (+1) ≡ 0 (mod 3)

This ensures compositional coherence in the Cat# equipment structure.

structured-decomp