Not signed in (Sign In)

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Site Tag Cloud

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory k-theory lie-theory limit limits linear linear-algebra locale localization logic mathematics measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory stack string string-theory subobject superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).
    • CommentRowNumber1.
    • CommentAuthorTodd_Trimble
    • CommentTimeFeb 8th 2014

    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).

    • CommentRowNumber2.
    • CommentAuthorUrs
    • CommentTimeFeb 9th 2014

    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?

    • CommentRowNumber3.
    • CommentAuthorTodd_Trimble
    • CommentTimeFeb 9th 2014

    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.

  1. 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.

  2. 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?

  3. 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.

    • CommentRowNumber7.
    • CommentAuthorTodd_Trimble
    • CommentTimeJan 30th 2015

    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.)

    • CommentRowNumber8.
    • CommentAuthorThomas Holder
    • CommentTimeJan 30th 2015
    I've expanded a bit the idea section and added a remark on the homological form of the Danos-Regnier criterion.
  4. 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.

    • CommentRowNumber10.
    • CommentAuthorMike Shulman
    • CommentTimeNov 14th 2019

    Is there an extended version of BCST circuit diagrams for models of MELL, i.e. *\ast-autonomous categories with a !-modality?

    • CommentRowNumber11.
    • CommentAuthorTodd_Trimble
    • CommentTimeNov 14th 2019

    If there is, I’m not aware of it.

    • CommentRowNumber12.
    • CommentAuthorMike Shulman
    • CommentTimeNov 14th 2019

    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.

    • CommentRowNumber13.
    • CommentAuthorMike Shulman
    • CommentTimeNov 16th 2019

    Well, I found Storage as tensorial strength which does linearly distributive categories with ? and !, but using boxes rather than brackets/croissants.

    • CommentRowNumber14.
    • CommentAuthorMike Shulman
    • CommentTimeDec 12th 2019

    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.

    • CommentRowNumber15.
    • CommentAuthorMike Shulman
    • CommentTimeDec 12th 2019

    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 nn-ary links for n>2n\gt 2, then it seems (e.g. by writing ABCA\otimes B \otimes C as A(BC)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 nn-ary link, for all n0n\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.)

  5. Réparation du lien vers l’article “Functorial boxes in string diagrams” de Paul-André Melliès

    Bérénice Delcroix-Oger

    diff, v25, current