Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Algorithms for finding arrows in free categories?

Ignat Insarov (May 15 2025 at 07:18):

Many problems in life can be formulated as «find an arrow in a free category».

• Given knowledge of possible manufacturing and trade events, we can construct a place/transition net and freely generate a symmetric monoidal category out of it. Then, the problem of finding a profitable business opportunity is the problem of finding an arrow $\operatorname {\$}^n → \operatorname {\$}^m, m > n$.
• Given a hole of type $X → Y$ in a typed computer program, we can promote all definitions available in the context of this hole to edges in a graph and freely generate an appropriate category out of it. Then, the problem of finding a sub-program that would fit in this hole is the problem of finding an arrow $X → Y$ such that the program passes the test suite.

Is there any literature discussing algorithms that efficiently find such arrows?

Ignat Insarov (May 15 2025 at 07:48):

There is a book Computational Category Theory, but I do not think it says anything specifically about free categories or about finding arrows. Although, it talks about transitive closure of graphs as an adjunction, in section 6.5.3.

Mike Shulman (May 15 2025 at 13:56):

All those problems can also be formulated as find a directed path in a directed graph, and for that phrasing of the problem there are well-known algorithms like depth-first search and breadth-first search.

Ignat Insarov (May 15 2025 at 19:18):

I am concerned with the underlying graphs being too big to handle.

For instance, in a category with products (that is certain to turn up in the example with computer programs), there is an infinity of arrows of form $X → X^n$. Breadth first search will take infinite time processing all these arrows, unless we equip it with a rule for when to stop and investigate the current branch in depth. Similarly, depth first search is sure to go on a wild goose chase unless we equip it with a rule for when to stop and restart from an earlier point in a different direction.

I do not know much about search in infinite, infinitely branching graphs. But certainly the search should be informed by the categorial structure of the problem. For instance, if we need to find $X → Y$ in a category with products, we can search from $X$ forward and from $Y$ backwards, and once we reach $A^n$ on our forward search and $A^m$ on our backwards search, we are done, no matter what $n$ and $m$ are.

We can also simplify some problems using the categorial structure of the problem. For instance, if our goal is $X → Y × Z$ in a category with products, then we can instead solve two simpler problems $X → Y$ and $X → Z$. This way, we can avoid generating an infinity of arrows arising from the product structure and reduce the search space to a finitely branching graph.

In a symmetric monoidal category without any other structure that could generate infinity of edges starting at one vertex, a simple search may work. We can even say that our interest is exactly to find situations where simple search starts going out of hand in a non-trivial way — any non-looping infinite trading path that involves only a finite variety of goods must involve increasing the quantity of some of these goods indefinitely, which is where our profit will be. But simple search will be far from an optimal algorithm.

Consider an example: $\text {bag of flour} → 10 ⊗ \text {bun}, \text {bun} ⊕ \text {patty} → \text {burger}$, and assume that everything is traded at fixed price. Then, if you want to make 100 burgers, it is never the case that you should buy 5 bags of flour and 50 buns — either the buns are cheaper, and then you should buy 100 buns, or the flour is cheaper, and then you should buy 10 bags of flour. But a simple search algorithm does not know this — it will have to try all possible combinations, of everything, every time. And rightly so: if you want to make only 15 burgers, you may be better off buying 15 buns, or 2 bags of flour, or 1 bag of flour and 5 buns, depending on the exact prices.

It seems there should be a way to set this problem up as some combination of search and convex optimization…

Ryan Wisnesky (May 15 2025 at 19:58):

sounds like maybe the notion of 'presentation' of a category would help formalize your intuition? One may use presentations to manipulate infinite categories on a computer for example.