AlgebraicJulia / AlgebraicJulia/Catlab.jl
Homomorphism search extensibility
- Linguagem predominante
- Julia
- Estrelas
- 724
- Forks
- 73
- Métricas de merge de PRs
- Nenhum PR com merge em 30d
Descrição
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.
Guia de contribuição
Avaliação
Esta issue ainda não foi avaliada.