Skip to content

vcvpaiva/DialecticaCategories

Repository files navigation

Dialectica Categories

A place to collect work on dialectica categories.

My work:

  1. Ph.D. Thesis: "The Dialectica Categories", TR213 from Cambridge, 1991.

    videos: Dialectica Categories for All (2024) Dialectica for Friends (2021) Dialectica: the mathematical version (2020)

From the thesis, two conference papers and a much later journal comparison:

  1. AMS Contemporary Mathematics: "The Dialectica Categories" Boulder AMS meeting 1987, volume 92. (1989)

  2. CTCS 1989: "A Dialectica-like Model of Linear Logic" (1989)

  3. TAC paper: "Dialectica and Chu constructions: cousins?", Theory and Applications of Categories, Vol. 17, No. 7, pp 127-152 (2006)

From the thesis a new logical/type theory system that is the natural, intrinsic logic of the categories GC, "Full Intuitionistic Linear Logic" (FILL), and with Luiz Carlos a version for Intuitionistic logic (FIL). With Torben and Harley proofs of cut-elimination for the logic FILL, with Harley mechanized in Agda.

  1. FILL Full Intuitionistic Linear Logic (with Martin Hyland) APAL (1993) (official)

  2. Full Intuitionistic Logic (FIL) (with Luiz Carlos Pereira) Logic Colloquium 1994 -- abstract ``A New Proof System for Intuitionistic Logic", The Bulletin of Symbolic Logic, vol 1(1):101, 1995. paper in 2005, "A short note on Intuitionistic Propositional Logic with Multiple Conclusions" Manuscrito-- Rev Int. Fil. Campinas, v. 28, n.2, pp 317-329, jul-dez. (2005) (preprint) --this is intuitionistic logic, not Linear Logic!

  3. Cut-Elimination for Full Intuitionistic Linear Logic (with Torben Brauner), CSL1997, preprint CSL version `A formulation of linear logic based on dependency-relations'- T Braüner, V De Paiva. Int Workshop on Computer Science Logic, 129-148 (1997)

  4. FILL (new proof of cut-elimination with Harley Eades III) Multiple Conclusion Linear Logic: Cut-elimination and more. Lecture Notes in Computer Science (2016) Proceedings of the Symposium on Logical Foundations of Computer Science (LFCS 2016), formalized in Agda. Journal version in Journal of Logic and Computation, Multiple Conclusion Linear Logic: Cut-elimination and more (2020)

  5. Typed lambda-calculus for FILL (with Eike Ritter) "A Parigot-style linear λ-calculus for Full intuitionistic Linear Logic" (2007)

Algebraic versions

  1. Lineales with Martin Hyland, in "O que nos faz pensar?" PUC,Rio de Janeiro(1991) Lineales: algebras and categories in the semantics of Linear Logic. Presented at LLC8, Stanford, May 1999. CSLI book "Words, Proofs, and Diagrams" (eds. D. Barker-Plummer, D. Beaver, Johan van Benthem, and P. Scotto di Luzio), 2002 Preprint version Lineales: Algebraic Models of Linear Logic from a Categorical Perspective.

Applications

Petri Nets:

  1. "Categorical multirelations, linear logic and Petri nets" TR 225 from Computer Lab, Cambridge. Inspired by Carolyn Brown thesis.

  2. BRICS TR, with Carolyn Brown and Doug Gurr "A linear specification language for Petri Nets", accepted for TCS in mid 90's with mods, but abandoned.

  3. Dialectica Petri nets: Theme of ACT Adjoint School 2020 with Elena Di Lavore, Xiaoyan Li, Wilmer Leal, Eigil Rischel and Jade Master. Blog post. Poster at ACT 2021, presented by Elena di Lavore.

    Arxiv preprint with Elena di Lavore and Wilmer Leal Dialectica Petri Nets, submitted.

Dialectica categories for Lambek calculus:

  1. Original paper in Amsterdam Colloquium 1991 A Dialectica model of the Lambek Calculus

  2. Talk at APA, April 2017. Conference LFCS paper with Harley Eades III, Jan2018. Dialectica Categories for the Lambek Calculus journal paper not submitted.

Dialectica categories for modelling State/Pomset logic

  1. A Dialectica Model of State (1996) Conference paper in CATS'1996 with Marcelo Correa and Hermann Hauesler.

  2. journal paper: Valeria de Paiva. Linear Logic Model of State Revisited. Logic Journal of IGPL, 01 October 2014, volume 22, number 5, pages 791-804.

  3. Dialectica categories for Relevant logic (need to recover the important bits from http://www.dbd.puc-rio.br/depto_informatica/93_mere.pdf) slides?

Dialectica categories for Set Theory (work with Samuel G da Silva. three papers so far, 19, 20 and 21.)

  1. Dialectica Categories, Cardinalities of the Continuum and Combinatorics of Ideals, with Samuel G. da Silva.

  2. Linear Natural Numbers Objects in Dial (Valeria de Paiva, Charles Morgan, Samuel G. da Silva). Natural Number Objects in Dialectica Categories. ENTCS, 01 January 2014. Electronic Notes in theoretical Computer Science, 305 (2014), pages 53-65. https://www.researchgate.net/publication/263699584_Natural_Number_Objects_in_Dialectica_Categories)

  3. Kolgomorov-Veloso Problems and Dialectica Categories, (with Samuel G. da Silva). In "A Question is More Illuminating than the Answer: A Festschrift for Paulo A.S. Veloso Edward Hermann Haeusler, Luiz Carlos Pinheiro Dias Pereira and Jorge Petrucio Viana, eds.

Preprint arXiv https://arxiv.org/abs/2107.07854

Samuel, on his own, based on Dialectica:

  1. Dialectica over a partial order, in LC Pereira Festschrift, http://vcvpaiva.github.io/includes/pubs/2015boundedDial.pdf

  2. Generalizations:

Dialectica Principles via Gödel Doctrines (with Davide Trotta and Matteo Spadetto) Theoretical Computer Science, 2023. https://trottadavide.github.io/publication/pubb_6/ Preprint in the arXiv https://arxiv.org/abs/2104.14021

Dialectica logical principles: not only rules. (with Davide Trotta and Matteo Spadetto) Journal of Logic and Computation, 2022. https://trottadavide.github.io/publication/pubb_4/

Dialectica Logical Principles (with Davide Trotta and Matteo Spadetto) in LFCS2022. https://trottadavide.github.io/publication/pubb_3/ Preprint in the arXiv https://arxiv.org/abs/2109.08064

The Gödel fibration. (with Davide Trotta and Matteo Spadetto) In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), 2021. see https://trottadavide.github.io/publication/pubb_2/

  1. Dialectica and Games (lost EPSRC proposal, how did I do that?)

24A. SuperPower Lorenzen Games, manuscript from 2011 Nancy CLMPST Talk. https://drive.google.com/file/d/19wSFHBNdb-PQj2ZjM6oZtV6MVutpGIdn/view?usp=sharing

Extreme cases of Dialectica with Andrea Schalk

  1. Building models of linear logic, V De Paiva, A Schalk (https://www.researchgate.net/publication/220977218_Building_Models_of_Linear_Logic) International Conference on Algebraic Methodology and Software Technology

  2. Poset-valued sets or how to build models for linear logics A Schalk, V De Paiva Theoretical Computer Science 315 (1), 83-107 https://www.researchgate.net/publication/222848911_Poset-valued_sets_or_how_to_build_models_for_linear_logics

==================================================

Work (from others) related to dialectica categories:

  1. M. Hyland, Proof Theory in the Abstract 2002 https://www.sciencedirect.com/science/article/pii/S0168007201000756

  2. Hofstra, P in Makkai Festschrifft, 2011 The dialectica monad and its cousins, Pieter J. W. Hofstra, http://mysite.science.uottawa.ca/phofstra/dialectica.pdf

  3. Bodil Biering's thesis, Dialectica Interpretations: A Categorical Analysis http://cs.au.dk/~birke/phd-students/BieringB-thesis.pdf, 2008

  4. An Analysis of Gödel's dialectica Interpretation via Linear Logic, Paulo Oliva, Dialectica, 2008. (available from http://www.eecs.qmul.ac.uk/~pbo/) many more from his webpage!

  5. "A Functional Functional Interpretation", Pierre-Marie Pedrot, LICS 2014, https://www.pédrot.fr/articles/lics2014.pdf https://www.pédrot.fr/slides/thesis-09-15.pdf, the thesis https://hal.archives-ouvertes.fr/tel-01247085

also slides post-thesis https://www.xn--pdrot-bsa.fr/slides/types-dialectica-05-16.pdf

  1. Mihai Budiu, Joel Galenson, and Gordon Plotkin The Compiler Forest, ESOP 2013, http://budiu.info/work/esop13.pdf slides https://jgalenson.github.io/papers/esop2013-talk.pdf

  2. Jules Hedge's Dialectica categories and games with bidding. In Post-proceedings of TYPES’14. LIPIcs 39:89-110, 2015. http://drops.dagstuhl.de/opus/volltexte/2015/5493/pdf/7.pdf

Also influential blog post Lenses for Philosophers https://julesh.com/2018/08/16/lenses-for-philosophers/

a. Tamara von Glehn. Polynomials and models of type theory (PhD thesis) https://www.repository.cam.ac.uk/handle/1810/254394, 2015

b. Sean Moss and Tamara von Glehn. Dialectica models of type theory, LiCS2018. https://dl.acm.org/citation.cfm?doid=3209108.3209207 paywall, now https://arxiv.org/abs/2105.00283?context=math

c. Sean Moss. PhD thesis: The Dialectica models of type theory (Diller-Nahm) https://www.repository.cam.ac.uk/handle/1810/280672

d. Tamara von Glehn POLYNOMIALS, FIBRATIONS AND DISTRIBUTIVE LAWS, http://www.tac.mta.ca/tac/volumes/33/36/33-36.pdf

e. Sean Moss. Talk at Polynomial Workshop 2: Dependent products of polynomials https://topos.site/p-func-workshop/slides/Moss.pdf

  1. Tom Powell a. Applying Gödel's Dialectica Interpretation to Obtain a Constructive Proof of Higman's Lemma, https://arxiv.org/abs/1210.3117.

    b. Well Quasi-Orders and the Functional Interpretation, https://arxiv.org/pdf/1706.02881.pdf

    c. LICS2017 paper "Gödel's functional interpretation and the concept of learning" http://dl.acm.org/citation.cfm?doid=2933575.2933605

  2. Mike Shulman a. The 2-Chu-Dialectica construction and the polycategory of multivariable adjunctions, https://arxiv.org/abs/1806.06082

    b. Mike Shulman, Linear logic for constructive mathematics, https://arxiv.org/abs/1805.07518 (check also https://arxiv.org/abs/1107.6032 Traces in symmetric monoidal categories and https://golem.ph.utexas.edu/category/2017/12/the_2dialectica_construction_a.html)

  3. Pierre Pradic and Colin Riba, from http://perso.ens-lyon.fr/colin.riba/ a. A Dialectica-Like Interpretation of a Linear MSO on Infinite Words. Submitted [pdf].

    b. LMSO: A Curry-Howard Approach to Church's Synthesis via Linear Logic. LICS'18 [pdf].

    c. A Curry-Howard Approach to Church's Synthesis. FSCD'17 [pdf]. Long version (submitted) [pdf].

  4. Pierre Hyvernat, A Linear Category of Polynomial Diagrams, http://www.lama.univ-savoie.fr/pagesmembres/hyvernat/research.php

    https://www.lama.univ-savoie.fr/pagesmembres/hyvernat/Files/poly_functors.pdf

    https://www.lama.univ-savoie.fr/pagesmembres/hyvernat/Files/poly_diagrams.pdf

  5. Benno van der Berg et al A functional interpretation for nonstandard arithmetic with Eyvind Briseid and Pavol Safarik. Annals of Pure and Applied Logic, volume 163, issue 12 (2012), pp. 1962–1994.

    https://staff.fnwi.uva.nl/b.vandenberg3/papers/dsttopos.pdf.

  6. Martin Hyland's talk in Leeds "Polynomials and Dialectica categories" https://eps.leeds.ac.uk/maths/events/event/5993/polynomials-and-dialectica-categories

  7. "The Dialectica Interpretation of first-order Classical Affine Logic", M. Shirahata, http://emis.impa.br/EMIS/journals/TAC/volumes/17/4/17-04.pdf

  8. "A Semantic Version of the Diller-Nahm Variant of Godel’s Dialectica Interpretation" Thomas Streicher -- https://www2.mathematik.tu-darmstadt.de/~streicher/Dial.pdf

  9. Pino Rosolini -- "Triposes and Gödel's Dialectica Interpretation" https://www.youtube.com/watch?v=_db-eVaU-ts

  10. Hongde Hu; Andre Joyal -- Coherence completions of categories, https://core.ac.uk/download/pdf/82827543.pdf

  11. Kerjean and Pedrot: ∂ is for Dialectica: typing differentiable programming, https://www.irif.fr/~kerjean/papers/dial_diff.pdf

Make a list of the work on Lenses! and containers -- see https://www.brunogavranovic.com/posts/2022-02-10-optics-vs-lenses-operationally.html and applications in his github Make a list of work on games

About

A place to collect work on dialectica categories.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published