Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improved support for left pushforward data migration #436

Open
epatters opened this issue Jun 21, 2021 · 3 comments
Open

Improved support for left pushforward data migration #436

epatters opened this issue Jun 21, 2021 · 3 comments

Comments

@epatters
Copy link
Member

epatters commented Jun 21, 2021

Thanks to @slibkind's PR #433, we now have a first implementation of the left pushforward data migration functor for C-sets. Given a functor F: C -> D between schemas, the algorithm assumes that the graph generating D has no cycles (it performs a topological sort on D). This means that we cannot, for example, create the free reflexive graph on a graph because the schema for reflexive graphs has cycles.

In general, computing left Kan extensions is a challenging problem. The state of the art seems to be Fast Left Kan Extensions using the Chase by Spivak and Wisnesky. For a next step, I think we should just do the simplest thing that would cover standard examples like symmetric and/or reflexive graphs.

@epatters
Copy link
Member Author

epatters commented Jun 21, 2021

A question to get started. I think the current implementation explicitly constructs the comma categories F/d, but perhaps we should be constructing presentations of them instead? As a point of comparison, the cited paper shows how, assuming C, D, and F are finitely presented, to finitely present the collage of F (meaning the collage of the profunctor represented by F). The collage contains essentially the same data as all the comma categories used in the formula for Sigma_F (see Proposition 1 and Lemma 2).

@kris-brown
Copy link
Contributor

This is being addressed in #615

@epatters
Copy link
Member Author

Great! I was hoping that you would work on this stuff.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants