AlgebraicJulia / AlgebraicJulia/Catlab.jl

Homomorphism search extensibility

Open
#608 0 comments 0 reactions 0 assignees View on GitHub
acsets enhancement
Dominant language
Julia
Stars
724
Forks
73
PR merge metrics
No merged PRs in 30d

Description

Many times you'd want a single homomorphism (if any exists) under some constraints. We currently support this for monic, iso, partially initialized homomorphisms, and (soon) surjective homomorphisms, but really the list could go on. Three examples:

1. Automatic DPO search needs a single homomorphism _that satisfies the dangling condition_. The only way to get this presently is to generate all homomorphisms and filter.
2. It is standard in DPO to have negative application conditions (the rule has an additional morphism `L->N`, and we also forbid matches `L->G` such that there exists a homomorphism `N->G` making the triangle commute). Again, this is something that could hypothetically be added to the algorithm as a keyword, but this is unsustainable.
3. One can use the negative application condition to say something like "match a pair of labeled parallel edges but only if their edge values are _not_ equal to each other", but implementing this requires search for homomorphisms where the `monic` constraint is required only for specific edges in the domain.

As generating all homomorphisms is also not feasible, we could think of how to make the search more extensible. I suspect a visitor pattern style for homomorphism search or making the process return a lazy iterator are potential solutions.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.