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: community: general

Topic: finding a paper on premonoidal categories

Cole Comfort (Oct 19 2020 at 12:11):

Hi, does anyone have a copy of the paper ``Premonoidal categories and a graphical view of programs''? It appears that the author Alan Jeffrey published the paper on his website, but it has 404ed. I guess this is why people ought to use the arxiv.

The paper without appendices appears to be found at the following website: https://www.researchgate.net/publication/228639836_Premonoidal_categories_and_a_graphical_view_of_programs

Reading the paper from the wayback machine is practically illegible.

Alternatively, does anyone have the author's email?

Sam Staton (Oct 19 2020 at 12:31):

Hi @Cole Comfort, I managed to get https://asaj.org/papers/premonA.pdf and the appendix at https://asaj.org/papers/premonB.pdf . It's a nice paper! Pity the Java applet seems to be down :smile:

Cole Comfort (Oct 19 2020 at 12:33):

@Sam Staton

Thank you so much!!! It probably seemed like a good idea to write the paper in HTML at the time, but it didn't age well.

Cole Comfort (Oct 19 2020 at 12:33):

I'm happy that most people use the arxiv now

Alan Jeffrey (Oct 29 2020 at 18:07):

:wave:

Alan Jeffrey (Oct 29 2020 at 18:09):

What can I say, it was the 1990s, applets seemed really cool at the time. There's no way that application could have been implemented in the JS that existed then.

Cole Comfort (Oct 30 2020 at 04:33):

Alan Jeffrey said:

What can I say, it was the 1990s, applets seemed really cool at the time. There's no way that application could have been implemented in the JS that existed then.

Do you still have the applet by chance? So that it isn't truly lost to time...

Sam Staton (Oct 30 2020 at 13:28):

Hi @Alan Jeffrey ! I don't think the paper/appendix is linked from your web page anymore, maybe that was intentional, but I found it by being crafty with the urls

Alan Jeffrey (Oct 30 2020 at 14:38):

Oops, the link 404s, that's not good.

Jules Hedges (Oct 30 2020 at 14:44):

Alan Jeffrey said:

What can I say, it was the 1990s, applets seemed really cool at the time. There's no way that application could have been implemented in the JS that existed then.

I have in mind to try to foster a sort of "movement" of hackers in applied category theory. I talked about it a bit in #general > category theory software. Recreating something with equivalent functionality to that applet, but as part of a modern ecosystem, would definitely be an interesting thing to do

Alan Jeffrey (Oct 31 2020 at 18:49):

The wayback machine to the rescue! http://web.archive.org/web/*/http://fpl.cs.depaul.edu/ajeffrey/premon/*

Alan Jeffrey (Oct 31 2020 at 19:02):

Downloading it now, with https://github.com/hartator/wayback-machine-downloader

Alan Jeffrey (Oct 31 2020 at 19:43):

I restored it to https://asaj.org/premon/ now we just need a browser which displays applets :/

Cole Comfort (Oct 31 2020 at 19:44):

Nice!

Cole Comfort (Oct 31 2020 at 19:51):

This thread is probably a good place to ask, before I work out the gory details. Is there any literature out there on the premonoidal structure of $({\sf Cospan}({\sf FinSet}), \times)$?

Jules Hedges (Oct 31 2020 at 22:42):

Surely it's properly monoidal?

Cole Comfort (Oct 31 2020 at 22:43):

Jules Hedges said:

Surely it's properly monoidal?

No it isn't. Bruni and Gadducci give a counterexample in their paper:
https://www.sciencedirect.com/science/article/pii/S157106610480937X

Cole Comfort (Oct 31 2020 at 22:43):

$({\sf Cospan}({\sf FinSet}), +)$, $({\sf Span}({\sf FinSet}), \times)$ and $({\sf Span}({\sf FinSet}), +)$ are all symmetric monoidal, but not this one.

Jules Hedges (Oct 31 2020 at 22:45):

Wow..... the universe is definitely haunted. It's so obviously monoidal I definitely wouldn't have bothered to check

Cole Comfort (Oct 31 2020 at 22:49):

It's an interesting question imo

Fabrizio Genovese (Nov 01 2020 at 00:17):

Jules Hedges said:

Wow..... the universe is definitely haunted. It's so obviously monoidal I definitely wouldn't have bothered to check

If @Dan Marsden taught me something during my PhD is that "bothering to check" is just not an admissible scientific practice. I know that sometimes things are obvious, but when you develop the habit of checking everything you get quickly surprised by how many stuff doesn't go through for "trivial" reasons

Fabrizio Genovese (Nov 01 2020 at 00:18):

Personally, I've been working with free symmetric strict monoidal categories A LOT in the last years, and it's basically just manipulating strings all the time. One would expect things to work out trivially, and instead there's ALWAYS a circumstance of diagrams not commuting strictly, but only up to some stupid permutation of something that gets in the way. It's the epitome of frustration. :grinning:

Cole Comfort (Nov 01 2020 at 00:21):

Fabrizio Genovese said:

Jules Hedges said:

Wow..... the universe is definitely haunted. It's so obviously monoidal I definitely wouldn't have bothered to check

If Dan Marsden taught me something during my PhD is that "bothering to check" is just not an admissible scientific practice. I know that sometimes things are obvious, but when you develop the habit of checking everything you get quickly surprised by how many stuff doesn't go through for "trivial" reasons

Most things just work out, but it is the very few things that don't that really don't.

Fabrizio Genovese (Nov 01 2020 at 01:31):

Yeah. In any case "presuming" that something works out can be an act of hubrys. Personally I try to avoid that as much as I can, even if it's more work.

John Baez (Nov 01 2020 at 02:17):

Cole Comfort said:

Most things just work out, but it is the very few things that don't that really don't.

Is there a nice way to summarize the problem? Composing cospans uses pushouts, so presumably there's something bad about pushouts and products... for example, when you've got two pushout diagrams in Set, the product of their pushouts isn't the pushout of their product, or something like that.

John Baez (Nov 01 2020 at 02:23):

I looked at the paper by Bruni and Gadducci, and their counterexample is in Section 4.3, but it talks about the "discharger and codischarger of the monoidal structure given by disjoint union", and while I think I can guess what that means I don't have the energy to parlay that clue into a calculation right this minute.

Jules Hedges (Nov 01 2020 at 12:39):

I would think of $(Span(FinSet), \times)$ as a model of nondeterministic computation. I wonder if there's a corresponding intuition for $(Cospan(FinSet), \times)$ as a category of computational processes, that gives some intuition for why the interchange law fails

Jules Hedges (Nov 01 2020 at 12:44):

Please tell me $(FinCorel, \times)$ is monoidal? I think of $(Span(FinSet), \times)$ as a proof-relevant version of $(FinRel, \times)$ but the corresponding relationship between $(Cospan(Finset), \times)$ and $(FinCorel, \times)$ must go wrong somehow...?

Cole Comfort (Nov 01 2020 at 12:54):

$({\sf Cospan}({\sf FinSet}), +)$ gives a semantics for equivalence relations with scalars.

$({\sf Span}({\sf FinSet}), +)$ gives a semantics for nondeterministic circuits weighted by natural numbers, because it is a presentation for natural number matrices under the disjoint union.

$({\sf Span}({\sf FinSet}), \times)$ is like the nonlinear version of $({\sf Span}({\sf FinSet}), +)$, because you have the multiplication gate and its unit which is like an affine shift; as well as the transpose of these things. Although, I only really have intuition about the full subcategory of this category generated by $[2^n]$.

Because of this result that premonoidal categories embed in the Kleisli category of a state monad, I imagine that perhaps this exotic category gives a semantics for something like stateful equivalence relations? I am not so sure.

I am not sure if $({\sf Corel}({\sf FinSet}), \times)$ is monoidal, and I don't have any reason to believe it is. In the case of $({\sf Span}({\sf FinSet}), +)$, the quotient taking you to relations imposes the equation $2=1$, giving a semantics for nondeterministic circuits. Similarly the quotient on $({\sf Cospan}({\sf FinSet}), +)$ taking you to corelations just removes the extra scalars, and gives you actual equivalence relations. The case of $({\sf Span}({\sf FinSet}), \times)$ is a bit more interesting. At least in the full subcategory generated by objects $[2^n]$, then the quotient involves some nontrivial identity involving the multiplication gate, which doesn't really have a very nice categorical interpretation, as well as the extraness of one of the Frobenius algebras (the latter, as in $({\sf Corel}({\sf FinSet}), +)$). This other quotient is like saying that $t^2=t$, where $t$ is the $2\times 2$ upper triangular matrix containing 1s. I guess this is the bit that removes the proof relevance.

dusko (Nov 01 2020 at 18:54):

Cole Comfort said:

Because of this result that premonoidal categories embed in the Kleisli category of a state monad, I imagine that perhaps this exotic category gives a semantics for something like stateful equivalence relations? I am not so sure.

sorry if i am missing a reference somewhere earlier in the thread, but where is the result that all premonoidal categories embed in the kleisli category of a state monad?

Cole Comfort (Nov 01 2020 at 18:56):

dusko said:

Cole Comfort said:

Because of this result that premonoidal categories embed in the Kleisli category of a state monad, I imagine that perhaps this exotic category gives a semantics for something like stateful equivalence relations? I am not so sure.

sorry if i am missing a reference somewhere earlier in the thread, but where is the result that all premonoidal categories embed in the kleisli category of a state monad?

This is in @Alan Jeffrey's paper linked earlier in the thread, unless I am misinterpreting the paper.

Cole Comfort (Nov 01 2020 at 19:00):

It is in the appendix.

Cole Comfort (Nov 01 2020 at 19:01):

https://asaj.org/papers/premonB.pdf

dusko (Nov 01 2020 at 19:13):

Cole Comfort said:

It's an interesting question imo

it is a very interesting question. Re Jules' haunted universe, i think it is haunted by our requirements of comfort. why is the monster group there? sure, there is that vertex algebra. but reconstructing the structure of the universe back from it seems like the pythagorean religion all over again. it is of course a good religion, maybe the best of all possible religions, but it is a religion. nothing wrong with that, but i think it would be even a better religion if it confessed that it is.

i don't know if this link will survive (ask me if it doesn't) but i think you guys might like it: https://www.youtube.com/watch?v=Ojr8294tzmA

Alan Jeffrey (Nov 04 2020 at 00:37):

IIRC (it's been a while!) the result is that if you take the free symmetric monoidal category (i.e. flow graphs) then take the free Kleisli category for a state monad (i.e. flow graphs with control edges ) then that is the free premonoidal category. This might give you an embedding, but I don't think that's in the paper.

Alan Jeffrey (Nov 04 2020 at 00:38):

Also, hi Dusko!

dusko (Nov 05 2020 at 08:47):

hey alan. i have been keeping the appendix of your paper on the screen, to not forget to read it, but still didn't have a chance. but i am expecting to understand what i am misunderstanding from the statement. embedding every kleisli category into the kleisli category of the state monad would say that every computational side-effect can be captured by mealy machines. that cannot be right. that would sound like a non-hilbert-space version of the church of higher hilbert space theology from quantum --- if we were not in kleisli. the church of higher hilbert space requires projectors...

dusko (Nov 05 2020 at 08:49):

incidentally, if you get fed up of the chicago winter come visit honolulu. you'll find us easily: last house before the jungle. there is in the meantime a 14yo gentleman whom you i think didn't meet :)

dusko (Nov 05 2020 at 08:54):

my addy is my name at hawaii.edu or my name at my name dot org