Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
There has been a pretty massive expansion at proof net. All who are interested in this are invited to have a look (but the nLab is super-slow in loading now from where I write).
Noam Z., if you are reading this: I had looked at the notes you kindly mentioned to me recently. Could you comment on what the connection might be with the sequentialization result (see the remark 2 under theorem 1 in proof net)? The outline of proof reminded me of your description of inversion and focusing, but I confess I had a little trouble following everything (my fault, not yours).
Thanks, Todd! That’s really nice. Thanks.
I am going through it only adding hyperlinks to some more keywords.
Let me just check: “turnstyle” must be “turnstile”, I suppose?
Thanks! Yes, “turnstile” – oops. (And here I chided you about spell-check recently – double oops!) I’m not sure how prevalently that term is used to begin with.
I plan on tightening this up with Kelly-Mac Lane graph and Trimble rewiring pretty soon.
Todd: there is a definite resemblance, but since I never studied proof nets very closely I’m not sure what can be said more precisely. Thanks for the question, though, I’ll let you know if I have any more thoughts.
Hello Todd. I’m coming back to this stuff now, and noticed that I very much like the definition of proof nets given in the article, in terms of the “graphical semantics” functor. Is this categorical formulation in your thesis, or somewhere else in the literature?
I see that something like this graphical semantics functor appears in the original paper by Kelly and MacLane on “Coherence in closed categories” (which is a very nice paper!), so I imagine that might have been an inspiration.
Thanks! Most definitely Kelly-Mac Lane is a prominent source for this idea, but I’d trace the root idea back even earlier to the extranaturality graphs introduced by Eilenberg and Kelly in 1966 (A Generalization of the Functorial Calculus, J. Alg. 3, 366-375). Kelly wrote articles on graph functors during the 70’s (I think in SLNM 420 for instance), in connection with his concept of “club”, and it was Rick Blute in his 1991 thesis who can be credited for linking them to proof nets (see the references here).
I may have other things to say later about my thesis, spec. about a so-called “bimodule interpretation” of proof nets not found in the literature (I never published my thesis). (I’m not sure how “important” the idea is, although it was helpful to me at the time.)
Thanks very much for the references. The list of articles about coherence in Kelly’s bibliography also look quite interesting.
One minor comment about the article. I noticed that in the description of associating a net to a sequent deduction, the procedure gives just the rules for computing the KM-graph (i.e., the axiom links) of the net, but not the tensor and par links. It was already explained in an earlier section of the article that the net of a given sequent is determined up to its KM-graph, but I added a little reminder about that to this section.
Is there an extended version of BCST circuit diagrams for models of MELL, i.e. $\ast$-autonomous categories with a !-modality?
If there is, I’m not aware of it.
Have you ever thought about what it might look like?
Some context for my question: I think I have (as I mentioned to you, Todd, at Octoberfest last month) a solution to this question showing that any closed symmetric monoidal category can be fully and closedly embedded in a $\ast$-autonomous one. Moreover, if you start with a cartesian monoidal category, I believe I can show that the resulting $\ast$-autonomous category has an idempotent !-modality and the embedding lands inside the !-coalgebras. I am hoping that this will provide an answer to this question: the “brackets and croissants” used in sharing graphs look like they should be part of a circuit diagram calculus for $\ast$-autonomous categories with !-modality, and if so then all the sharing graphs involved in optimal $\lambda$-calculus reduction could be semantically interpreted in the $\ast$-autonomous envelope of a CCC to provide a semantic read-back.
Well, I found Storage as tensorial strength which does linearly distributive categories with ? and !, but using boxes rather than brackets/croissants.
Actually that’s a misleading thing to say: the sharing graphs used in optimal $\lambda$-calculus reduction do still have “boxes”, but they’re (sometimes) indicated implicitly by assigning a “level” to each node indicating how many boxes it’s inside. I think there are two different kinds of boxes though, one representing a functorial action of $!$ and the other representing a promotion rule. The real problem with interpreting optimal reduction semantically is that the intermediate steps are not even valid proof nets in the usual sense.
On a totally different topic, here’s something else curious that just occurred to me (although it is probably obvious to the experts). The graphical criterion for unit-free proof net validity says that for each binary $\invamp$-introduction or $\otimes$-elimination link, you cut one of the two non-principal wires (I’m not sure that’s the correct adjective, but hopefully you know what I mean), and for every possible choice of such cuttings you get a tree. If you generalize this to $n$-ary links for $n\gt 2$, then it seems (e.g. by writing $A\otimes B \otimes C$ as $A\otimes (B\otimes C)$) that the correct criterion should be that you cut all but one of the non-principal wires, so in particular there should be exactly one such wire left over. This makes it seem more natural that in the 0-ary case, we have to add a wire (the thinning link) so that we can say in general that an $n$-ary link, for all $n\ge 0$, should end up with exactly one non-principal wire.
However, I don’t at the moment see how to explain from this perspective the difference between how the higher-ary cases have a universal quantifier (for all ways of cutting) while the nullary case has an existential (we must be able to choose a place to put the thinning links). (The proof-relevance of the latter choice, i.e. the fact that different placements can – but don’t always – represent different morphisms in a category, seems less problematic to me, amounting to replacing an $\exists$ with a $\Sigma$ or rather some quotient thereof.)
1 to 16 of 16