AlgebraicJulia / AlgebraicJulia/Catlab.jl

Homomorphism search extensibility

Aberta
#608 0 comentários 0 reações 0 responsáveis Ver no GitHub
acsets enhancement
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

Abrir o guia de contribuição

Avaliação

Esta issue ainda não foi avaliada.

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.