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.
John Baez (Apr 28 2020 at 01:06):Okay, folks! In the fifth talk of the ACT@UCR seminar, Gershom Bazerman will tell us about a localic approach to the semantics of dependency, conflict, and concurrency!
He'll give his talk on Wednesday April 29th at 5 pm UTC, which is 10 am in California, or 1 pm on the east coast of the United States, or 6 pm in England. It will be held online via Zoom, here:
https://ucr.zoom.us/j/607160601
You can see his talk slides here.
• Gershom Bazerman, A localic approach to the semantics of dependency, conflict, and concurrency.
Abstract. Petri nets have been of interest to applied category theory for some time. Back in the 1980s, one approach to their semantics was given by algebraic gadgets called "event structures." We use classical techniques from order theory to study event structures without conflict restrictions (which we term "dependency structures with choice") by their associated "traces", which let us establish a one-to-one correspondence between DSCs and a certain class of locales. These locales have an internal logic of reachability, which can be equipped with "versioning" modalities that let us abstract away certain unnecessary detail from an underlying DSC. With this in hand we can give a general notion of what it means to "solve a dependency problem" and combinatorial results bounding the complexity of this. Time permitting, I will sketch work-in-progress which hopes to equip these locales with a notion of conflict, letting us capture the full semantics of general event structures in the form of homological data, thus providing one avenue to the topological semantics of concurrent systems. This is joint work with Raymond Puzio.
Gershom (Apr 29 2020 at 18:13):I should mention that some of the questions about related work were about the "event structures for petri nets with persistence" paper and related. that's cited in the arxiv paper of ours (https://arxiv.org/abs/2004.05688) as related work, since it has a similar notion of a "splitting" construction, though we go somewhat different places with it.
John Baez (Apr 29 2020 at 18:14):Hi!
John Baez (Apr 29 2020 at 18:15):I just grabbed some coffee.
sarahzrf (Apr 29 2020 at 18:16):wish i could discuss the talk here but im running up VERY close to some deadlines on some stuff i need to get done lately so i should probably go work on that :T
sarahzrf (Apr 29 2020 at 18:16):cool stuff though :>
John Baez (Apr 29 2020 at 18:16):The part of your talk I liked the best, @Gershom, was the part connecting Petri nets and various kinds of posets, since those are two things I've thought about a bit, but not much together.
John Baez (Apr 29 2020 at 18:17):Let me just blab about that a bit.
Gershom (Apr 29 2020 at 18:17):Ok sarah, looking forward to thoughts from you at your leisure. As I mentioned, there's a _lot_ of the "depleted" perspective thats run through our work :-)
John Baez (Apr 29 2020 at 18:17):Any Petri net gives a commutative monoidal category where the objects are markings and the morphisms are generated by transitions: roughly, the morphisms are ways to go from one marking to another, allowed by the transitions.
John Baez (Apr 29 2020 at 18:18):The commutative monoidal structure comes from adding markings, i.e. adding numbers of tokens in each place.
John Baez (Apr 29 2020 at 18:19):We can then "deplete" (=decategorify) this commutative monoidal category and get a commutative monoidal poset, which I'd call the "reachability poset".
John Baez (Apr 29 2020 at 18:19):So this seems to be a basic ingredient in some of these discussions, though as you mention people then tend to restrict the class of Petri nets they consider.
John Baez (Apr 29 2020 at 18:20):Then another fun thing to do is take the set of downsets of your commutative monoidal poset and get a commutative quantale!
Gershom (Apr 29 2020 at 18:20):@John Baez I'm glad. I added that especially for you and your "crowd" :-P
I should add that I didn't give the full definition of conflict in a general event structure. Its something called a context, which is also P(P(E)), and it is downward closed. It is thought of as the set of "nonconflicting" collections of events. So if a,b,c don't conflict, then a,b don't conflict. To a topologist this is immediately the same data as a simplicial complex, which also helps motivate applying algebraic topological methods.
John Baez (Apr 29 2020 at 18:23):I think I'll need to re-read your slides a few times to organize my thoughts about what you said: how various restricted kinds of Petri nets correspond, or can be turned into, various kinds of posets and other structures...
John Baez (Apr 29 2020 at 18:24):So far I've just been doing things with all Petri nets, since that seems mathematically natural.
Gershom (Apr 29 2020 at 18:25):I will say that what you've sketched is in a sense "simpler" than the constructions given by Winskel et al. They have a whole collection of "unfoldings" of petri nets into this subclass of occurence nets, which then map to event structures, which then gives rise to "families of configurations" which is where they find the order-theoretic structure.
My slides don't given enough detail to explain this all formally, but the papers they reference are very nice and readable, so they were intended as an "invitation" to that stuff. The Winskel 86 paper is really the best place to start, since it is lengthy and rich...
John Baez (Apr 29 2020 at 18:26):I'd known about it but somehow not dared to read it.
John Baez (Apr 29 2020 at 18:26):Being a mathematician I like "simpler", of course...
John Baez (Apr 29 2020 at 18:27):But now I feel the need for more territory to explore, and you've just pointed me to a lot of it.
Gershom (Apr 29 2020 at 18:28):Anyway, somewhere along the way, you get the elements of your posets not simply corresponding to markings at one point in time, but, I believe, corresponding to markings over markings and where they "come from"
I will say that if I could read that paper, you certainly could :-P. There's also a lot of categories of petri nets flying about in that paper, but I don't know how to relate them to your setup, because they necessarily contain initial markings.
Joe Moeller (Apr 29 2020 at 18:29):You can take a subcategory of the category of markings and executions that we usually work with which contains everything reachable from an initial marking.
Joe Moeller (Apr 29 2020 at 18:30):Do you think that would be related to any of these categories you're talking about?
Gershom (Apr 29 2020 at 18:30):It sounds very plausible!
John Baez (Apr 29 2020 at 18:31):Gershom said:
Anyway, somewhere along the way, you get the elements of your posets not simply corresponding to markings at one point in time, but, I believe, corresponding to markings over markings and where they "come from"
Okay, that's interesting already. Not just markings but "paths of markings", which I guess are called something like "firing sequences" in the Petri net literature.
Joe Moeller (Apr 29 2020 at 18:32):What is meant by "markings over markings"? Maybe I'm misreading that part
John Baez (Apr 29 2020 at 18:33):In the commutative monoidal category firing sequences give morphisms, but different firing sequences can give the same morphism, for example if you can do A and then B or do B and then A, and they don't cause any conflict, those count as the same morphism.
Gershom (Apr 29 2020 at 18:33):typo, I meant something like "markings over time"
John Baez (Apr 29 2020 at 18:33):(I deliberately didn't think about "markings over markings" - a trained mathematician learns to not pay much attention to things that don't make sense.)
Joe Moeller (Apr 29 2020 at 18:34):It sounded potentially interesting.
Gershom (Apr 29 2020 at 18:34):right, so you have "configurations enabling other configurations" which is closer to P(E) x P(E) -> 2, which is chu-like.
John Baez (Apr 29 2020 at 18:34):So anyway, there's a lot of fun to be had categorically with "paths of markings" or "marking evolutions over time" or "firing sequences" or whatever you want to call them.
Joe Moeller (Apr 29 2020 at 18:34):Especially since I was thinking taking these reachability subcategories might give something like a fibration.
John Baez (Apr 29 2020 at 18:38):Anyway, I will start thinking about these things. Thanks, @Gershom!
Joe Moeller (Apr 29 2020 at 18:39):I was curious about what the "with choice" refers to specifically in pre-DSCs.
Gershom (Apr 29 2020 at 18:40):The choice is you have E -> P(P(E)) and not just E -> P(E). So events have a "choice" of where they come from.
Joe Moeller (Apr 29 2020 at 18:40):oh, so the choice is like non-determinism?
John Baez (Apr 29 2020 at 18:41):It's non-determinism in the past, not the future.
John Baez (Apr 29 2020 at 18:41):If you have $100 you could have earned it by working, or could have found it on the street, but not both...
John Baez (Apr 29 2020 at 18:42):So "$100 in pocket" maps to
John Baez (Apr 29 2020 at 18:42):{ {earning $100}, {finding $100 in street}}
That's an example of our map E P(P(E)). I like this idea.
Gershom (Apr 29 2020 at 18:42):Yep! The general problem is that non-determinism (or "choice") and conflict both give nice topological structures, but the two topological structures are apparently unrelated. So you try to put them together and all the nice properties fail. In a sense, the original Pratt literature on chu-spaces was motivated by concurrency models where they said "ok, so let's let everything fail and try to pretend its a space anyway". The Winskel stuff says "ok, lets not handle choice, and just handle conflict". Ever since then they've been trying to add back choice. Our approach says "let's handle choice, then try to put in conflict later."
Gershom (Apr 29 2020 at 18:45):I should mention the paper covers what the free distributive lattice is, which is the downsets of the upsets, and it shows that it has a different internal logic, which is better for reasoning about branching choice in some ways, and it gives a quotient relation on this internal logic which should correspond to "contracting" a big collection of nodes in a petri net to a single "black box"
Joe Moeller (Apr 29 2020 at 18:46):I'm super interested in this connection between concurrency and directed topology.
Joe Moeller (Apr 29 2020 at 18:46):Oh, does this contracting produce another Petri net?
Gershom (Apr 29 2020 at 18:49):we have cites in the paper to some intro stuff on directed topology. It was invented and motivated by trying to model concurrency. Grandis is the categorically richer stuff but the other big team with the book is the one with a lot more "hands on" stuff that's approachable. I think their stuff runs off in weird directions because it starts with point-set stuff, so they do a lot of work to "recover" more abstract stuff from there.
We don't handle the petri net case, but the stuff about "versions" in the paper should be able to be "pulled back" into the petri net story. Algorithmically it can be useful I think, because it lets you "quotient" away structure thats easy to compute with so you have a simpler problem to solve.
Gershom (Apr 29 2020 at 18:50):directed topology can also be seen as trying to "munge" two undirected topologies (i.e. choice and conflict). This is because there's a nice posetal structure to each and you somehow want "both at once".
Gershom (Apr 29 2020 at 18:51):in directed topology its not "choice" and "conflict" so much as "dependency" and "compatibility" to be precise, but waves hands
Gershom (Apr 29 2020 at 19:00):@Joe Moeller here's the book I was thinking of (could have sworn there was a pdf preprint easily accessible, but can't find it now) https://sfx.aub.aau.dk/sfxaub?sid=pureportal&doi=10.1007/978-3-319-15398-8 -- note it share some authors with the patch theory stuff mentioned in the discussion...
Gershom (Apr 29 2020 at 19:06):@sarahzrf btw one fun problem in the "depleted" world is if Bruns-Lakser is some sort of "depleted" version of the envelopes of the sort that mike was talking about (i.e. coming from Hyland). I don't know of a good general "theory of envelopes" but would love to learn of one! Perhaps its just another name for some subset of a theory of (co)reflections?
John Baez (Apr 29 2020 at 19:08):I was shocked when Mike said taking the Hyland envelope was not a left (2-)adjoint. Maybe I'm misremembering the details, because there were a few envelopes running around in that talk.
John Baez (Apr 29 2020 at 19:09):But yeah, the term "envelope" seems to be showing up when we have two (2-)categories of gadgets and and is a reflective subcategory of .
John Baez (Apr 29 2020 at 19:09):Or something like that: some sort of left adjoint that "improves" objects of to make them objects of .
John Baez (Apr 29 2020 at 19:10):It seems to mainly be used when our gadgets are posets of some sort.
Gershom (Apr 29 2020 at 19:20):Here is a talk by ray at CT octoberfest where he talks about how we've been thinking about completions (envelopes) more generally and attempting to relate them to forbidden configurations: https://jh.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=676ab6d0-e298-4b5a-b866-aaf200d61558
We don't have a "general" procedure for picking any old algebraic structure and getting the completion this way. But there's definitely a general pattern that mike talked about where you take a presheaf category and pick out only the "right" presheaves, which are the ones that respect the desired algebraic structure. I would like to relate this to the theory of canonical extensions as given in https://www.irif.fr/~mgehrke/TopologicalDualityandAlgebraicCompletions.pdf
Mike Shulman (Apr 29 2020 at 19:28):I think frequently words like "envelope" are used when A-objects remember "some fragment" of the structure of B-objects, and the point is to embed an A-object into a B-object preserving that fragment. So for instance the universal enveloping algebra of a Lie algebra is an associative algebra such that the embedding preserves the Lie bracket, a "fragment" of the structure of an associative multiplication. Similarly, the Hyland envelope of a polycategory is a -autonomous category such that the embedding preserves the polycategory structure (and, for the enhanced version I described, also some existing tensors and cotensors), a fragment of the -autonomous structure. Sometimes these envelopes have a universal property, sometimes not -- or, at least, not obviously.
Mike Shulman (Apr 29 2020 at 19:31):I'm positive the Hyland envelope is not a left adjoint to something obvious like the forgetful functor from -autonomous categories to polycategories; it's way too big for that. (In a technical sense -- the Hyland envelope of a small polycategory is a large -autonomous category.) The first "modules" step in its construction is a sort of presheaf construction (in fact it does happen to be a presheaf category on an appropriately chosen domain), hence some kind of left adjointy "free cocompletion" modulo size -- but then we do a Chu construction to that, whose most straightforward universal property is as a right adjoint.
Mike Shulman (Apr 29 2020 at 19:35):I wouldn't be surprised, however, if there were some way to express the Hyland envelope as a left adjoint (modulo size). The Hyland envelope for polycategories is a lot like the Isbell envelope for 1-categories, and Richard Garner showed in The Isbell monad that the Isbell envelope of C is the "free category with a cylinder factorization system" generated by C. So perhaps there is some structure like that that the Hyland envelope also adds freely.
Gershom (Apr 29 2020 at 21:15):Note that the Dedekind-MacNeillie completion is the posetal version of the Isbell envelope. So that does lend itself to the question "what is the Bruns-Lakser completion a posetal version of" and further, if in that categorical setting, we can extract out what the two have in common.
Gershom (Apr 29 2020 at 21:25):There was also a question in chat in the zoom related to this, which is how this stuff relates to the "conservative cocompletion" given in A Categorical Theory of Patches (originally due to Kelly): "the full subcategory of presheaves on C whose objects, considered as functors, preserve finite limits". This is very similar to the definition given of Bruns-Lakser in the paper by the authors of that name, which is "the poset of downsets of P, restricted to those downsets which themselves have joins distributing over meets".
So mathematically they're very similar. The two differences are of course that the conservative cocompletion is a construction on categories and not just posets, and that it just gives colimits freely which would "just" be adding joins in a posetal context, while Bruns-Lakser adds enough structure to ensure that joins distribute over meets. But as discussed, a fair number of these completions feel like instances of a single very general construction, and it would be good to pin that down.
Nathanael Arkor (Apr 29 2020 at 21:38):There are multiple ways we can consider "thickened" versions of the construction, but if we could take "meet semilattice" to thicken to "cartesian category" and "distributive lattice" to thicken to "distributive category". Then the distributive completion of a cartesian category is actually its coproduct completion: by freely adding coproducts, we get the distributivity property for free.
Nathanael Arkor (Apr 29 2020 at 21:39):This may be found in Cockett's Introduction to distributive categories.
Nathanael Arkor (Apr 29 2020 at 21:40):I think a similar property holds for the cocompletion of a finitely complete category, though I'm not sure of a reference right now.
Gershom (Apr 29 2020 at 22:18):@Nathanael Arkor Thanks for the reference. I think that this "free coproduct completion" as described is quite different than an envelope. In particular, it does not seem to be idempotent? The "conservative cocompletion", like Dedekind-MacNeillie and Bruns-Lakser, is idempotent, and so we have a reflector. They do mention that the Karoubi envelope (https://ncatlab.org/nlab/show/Karoubi+envelope) also gives a distributive category, and that seems to be more similar as a construction. But when you decategorify the karoubi envelope what you get is the completion of a preorder into a poset...
Valeria de Paiva (Apr 29 2020 at 22:39):Nathanael Arkor said:
I think a similar property holds for the cocompletion of a finitely complete category, though I'm not sure of a reference right now.
hi, the thing that rings a bell for me in this context is Joyal and H. Hu's work in https://www.sciencedirect.com/science/article/pii/S1571066105801628
this is about bicompletions of categories, when you start from a *-autonomous category
John Baez (Apr 29 2020 at 22:48):I wouldn't be surprised if Kelly, author of Enriched Categories, did an enriched version of "conservative completions", by considering enriched presheaves that preserve a chosen class of limits. Then the Bool-enriched case of these might give various nice "envelopes" or "completions" of posets.
John Baez (Apr 29 2020 at 22:49):Just a wild guess.
Mike Shulman (Apr 30 2020 at 01:09):John Baez said:
I wouldn't be surprised if Kelly, author of Enriched Categories, did an enriched version of "conservative completions", by considering enriched presheaves that preserve a chosen class of limits.
Yes, it's in section 3.12 of his book.
Mike Shulman (Apr 30 2020 at 01:13):Gershom said:
The "conservative cocompletion", like Dedekind-MacNeillie and Bruns-Lakser, is idempotent, and so we have a reflector.
If I understood your definition of conservative completion correctly ("the full subcategory of presheaves on C whose objects, considered as functors, preserve finite limits") then no, I don't think it is idempotent. The only way I can think of that might yield an idempotent operation is to consider categories equipped with some specified collection of colimits and consider the "completion" operation that takes the full subcategory of presheaves that preserve those specified colimits. Then you could equip the completion with the collection of all small colimits and hope that it would be its own completion in that sense, analogously to how a Grothendieck topos is equivalent to the category of sheaves on itself for its canonical topology. But restricting to finite covers/colimits breaks it, since the canonical topology is not finite.
Gershom (Apr 30 2020 at 02:53):Ah I left out a "finite" or two in the description. Let me paste directly the definition from the mimram/di giusto paper i was poorly paraphrasing (https://arxiv.org/abs/1311.3903)
Mike Shulman (Apr 30 2020 at 03:14):Ah yes, that works: if you restrict to those objects that are finite colimits of representables, then I can believe it's idempotent.
Gershom (Apr 30 2020 at 03:22):In looking at that, I was inspired to take a look at Mimram's habilitation thesis, which is quite interesting for an overview of a lot of the same stuff I've been interested in https://hal.inria.fr/tel-01783442/ . In that, the section on categorical patch theory is similar to that in the paper, but it notes that a counterexample was found to one of the later claims in the paper (not the cocompletion). That counterexample, iirc, is why a some of the promised future work on that approach has not come to fruition (but as people can see from the thesis, and subsequent work as well, a lot of other good work on related but distinct topics has been developed instead!)
সায়ন্তন রায় (Apr 30 2020 at 13:32):I don't know whether it is appropriate to mention this here but let me try anyway. So far as I have seen, all the online conferences are being conducted via the Zoom app. Is it safe to use it when, e.g., Google has banned its employees from using it due to security concerns?
Fabrizio Genovese (Apr 30 2020 at 15:12):I do prefer jitsi, which is free and opensource, but I guess it depends from uni to uni, often it's not up to the single research groups to choose what to use.
John Baez (Apr 30 2020 at 15:27):Our university uses Zoom so that's what I'm using. I could use jitsi if someone explained how to do it, but I'm lazy.
Fabrizio Genovese (Apr 30 2020 at 15:29):You just do meet.jit.si/nameOfYourMeetingand that's it. NameOfYourMeetingcan be created on the fly without doing any setup work
Fabrizio Genovese (Apr 30 2020 at 15:30):If you are even lazier, there's a camera button below the box in which you type that will set a link up for you
Fabrizio Genovese (Apr 30 2020 at 15:30): Fabrizio Genovese (Apr 30 2020 at 15:30)::D
Fabrizio Genovese (Apr 30 2020 at 15:30):Jitsi has a lot of the functions zoom has, like screen share, mute/unmute, set password for a conversation, raise your hand, etc, and as for zoom you can join with your phone. There is no desktop application, so everything is in browser.
John Baez (Apr 30 2020 at 15:39):How do other people join the meeting? Usually when I have a meeting I do it with other people.
John Baez (Apr 30 2020 at 15:40):(I'm not being sarcastic because I doubt it's easy. I just enjoy joking around.)
Fabrizio Genovese (Apr 30 2020 at 15:43):They all click on the link
Fabrizio Genovese (Apr 30 2020 at 15:43):If I do meet.jit.si/MyMeeting everyone visiting that address will be in the same room
Fabrizio Genovese (Apr 30 2020 at 15:44):So if you have to invite someone just copy paste the link :slight_smile:
সায়ন্তন রায় (Apr 30 2020 at 15:45):Maybe another option is to use Google Meet (that's what we use at our university) or even Skype @John Baez .
Mike Shulman (May 01 2020 at 03:30):Do these other options compare to Zoom in terms of quality at scale? The last time I tried anything non-Zoom the quality was far inferior.
সায়ন্তন রায় (May 01 2020 at 04:36):@Mike Shulman , my personal experience of using Google Meet is great. However, it supports only 100 persons (as far as I know).
Fabrizio Genovese (May 01 2020 at 11:53):Jitsi is giving me zero issues atm.
Gershom (May 01 2020 at 19:51):I didn't fully work this out, but I suspect the law for "lacks $M_3$" can be formulated as something like:
forall a b c. a /\ b = a /\c = b /\ c ==> (a\/b) /\ (a \/ c) = a.
(which should also hold in the dual)
Another, condition I wrote down some time ago that might formulate it (haven't done the work to compare them and see equivalence yet again, so its all sketchy) is
a \/ b = a \/ b \/ c & a /\ b = a /\ b /\ c iff a >= c || b >= c || a <= c || b <= c
This second condition is a more straightforward transcription of the rule, and so it perhaps offers a bit less insight.
But either way we can see that "no $M_3$" is a condition about a sort of "weak atomicity" of information, or about how we can recover data about atoms from meets and joins.
While the other condition along with this, upper semimodularity, is more well studied (see e.g. the wikipedia article for some various characterizations) I have less intuition for the "intuitive meaning" of its logical expression. It feels like a condition about "no hidden atoms" perhaps, just as semimodularity can be interpreted.
Gershom (May 02 2020 at 01:08):I also asked on mathoverflow and got another answer that confirms there's no way to have a variety of lattices with this property (there's another argument too, which follows from covering varieties of D and the investigation there): https://mathoverflow.net/questions/359113/class-of-lattices-that-excludes-m-3
Note that both conditions we give (no M_3, and semimodularity) are hard to tackle by these traditional methods. In the latter case, it can't be tackled because every variety of semimodular lattices consists entirely of modular lattices.
Related to our work on idempotent completions, Ray and I have been kicking around an approach (discussed in his talk which I linked above) that is more general than varieties, in that sentences need not be identities, but may instead be expressions in regular logic, which translate to "extension properties". Our hope is that this will let us get something in some ways more general than the HSP theorem. We put it aside a bit to focus more on the dependency structure stuff, but it would be nice to pick it up again.
John Baez (May 02 2020 at 01:29):Gershom said:
I didn't fully work this out, but I suspect the law for "lacks $M_3$" can be formulated as something like:
forall a b c. a /\ b = a /\c = b /\ c ==> (a\/b) /\ (a \/ c) = a.
(which should also hold in the dual)
Cool! I don't get it, but it's nice to see an equational law for this property. (It took me quite a while to grok modularity, so it's not surprising that I don't instantly get this one.)
Mike Shulman (May 03 2020 at 16:13):Sayantan Roy said:
I don't know whether it is appropriate to mention this here but let me try anyway. So far as I have seen, all the online conferences are being conducted via the Zoom app. Is it safe to use it when, e.g., Google has banned its employees from using it due to security concerns?
FWIW, it seems that Zoom has made some progress on improving their security in response to the recent criticism and scrutiny.
Gershom (May 09 2020 at 06:59):Btw, @Bob Coecke I mentioned in my talk that your work had made some use of the Bruns-Lakser construction (which I described a characterization of). It seemed to me that you had since moved on and no longer were continuing that approach, but this is just from a quick skim of the literature. In any case, I am curious about what came of that line of work.
Bob Coecke (May 09 2020 at 18:22):Hi, I haven't done anything since 1999 with that, but it became part of the topos approach to some extend. The best place for this is Dan Marsden's MSc thesis (which he should publish!): http://www.cs.ox.ac.uk/people/bob.coecke/Marsden.pdf
Bob Haugen (Jun 19 2020 at 13:05):Fabrizio Genovese said:
Jitsi has a lot of the functions zoom has, like screen share, mute/unmute, set password for a conversation, raise your hand, etc, and as for zoom you can join with your phone. There is no desktop application, so everything is in browser.
There is a phone app, though...works pretty well.