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.
keorn (May 29 2020 at 11:04):I would like something similar to shortest path/k-shortest paths algorithm, but with support for product and coproduct types. First question is probably how can such problem be framed category theoretically and secondly are there already some fields where similar algorithms have been worked out?
Thinking about it in wiring diagrams the question is roughly.
Given: input wires, output wires, boxes with weight/cost and with ports which accept wires of specific types
Looking for an arrangement of boxes that gets me from input wires to output wires with the least cost. Boxes can accept products or coproducts of wires.
Sorry if things are not precise here, just learning.
Fabrizio Genovese (May 29 2020 at 11:42):keorn said:
I would like something similar to shortest path/k-shortest paths algorithm, but with support for product and coproduct types. First question is probably how can such problem be framed category theoretically and secondly are there already some fields where similar algorithms have been worked out?
Thinking about it in wiring diagrams the question is roughly.
Given: input wires, output wires, boxes with weight/cost and with ports which accept wires of specific types
Looking for an arrangement of boxes that gets me from input wires to output wires with the least cost. Boxes can accept products or coproducts of wires.Sorry if things are not precise here, just learning.
Well, you can define a functor $F$ to the monoid of natural numbers, that is, the category that has only one object *, and natural numbers as morphisms. Identity is 0, while composition is addition. This functor maps every box to its cost, and functorial laws tell you that:
Then your question becomes "given objects A, B, find the morphisms A -> B such that $F(A -> B)$ is minimized." I don't think saying things like I did can help you in any way practically, but it's probably a "less messy way" to formulate what you want
keorn (May 30 2020 at 09:27):Thanks, makes sense. Now the question is about an algorithm. Seems to me that such problem would be fairly useful in any process optimisation.
Pastel Raschke (May 31 2020 at 10:13):alexander gray has described a (somewhat) general solution to generalized n-body problems, one class of which is proximity search/various nearest neighbor problems. not sure how applicable
keorn (May 31 2020 at 11:06):Nice, will read around.
Of course I would be also interested in a similar problem by just for a monoidal category with products.