Central submonads and notions of computation: Soundness, completeness and internal languages

Titouan Carette, Louis Lemonnier, Vladimir Zamdzhiev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Monads in category theory are algebraic structures that can be used to model computational effects in programming languages. We show how the notion of "centre", and more generally "centrality", i.e., the property for an effect to commute with all other effects, may be formulated for strong monads acting on symmetric monoidal categories. We identify three equivalent conditions which characterise the existence of the centre of a strong monad (some of which relate it to the premonoidal centre of Power and Robinson) and we show that every strong monad on many well-known naturally occurring categories does admit a centre, thereby showing that this new notion is ubiquitous. More generally, we study central submonads, which are necessarily commutative, just like the centre of a strong monad. We provide a computational interpretation by formulating equational theories of lambda calculi equipped with central submonads, we describe categorical models for these theories and prove soundness, completeness and internal language results for our semantics.
Original languageEnglish
Title of host publication2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science
Place of PublicationBoston, Massachusetts
PublisherInstitute of Electrical and Electronics Engineers
Pages1-13
Number of pages13
ISBN (Electronic)9798350335873
ISBN (Print)9798350335880
DOIs
Publication statusPublished - 14 Jul 2023
EventThe 38th Annual ACM/IEEE Symposium on Logic in Computer Science - Boston University, Boston, United States
Duration: 26 Jun 202329 Jun 2023
https://lics.siglog.org/lics23/

Publication series

NameProceedings of the ACM/IEEE Symposium on Logic in Computer Science
PublisherIEEE
ISSN (Print)1043-6871
ISSN (Electronic)2575-5528

Symposium

SymposiumThe 38th Annual ACM/IEEE Symposium on Logic in Computer Science
Abbreviated titleLICS 2023
Country/TerritoryUnited States
CityBoston
Period26/06/2329/06/23
Internet address

Keywords / Materials (for Non-textual outputs)

  • computer science
  • computer languages
  • computational modeling
  • semantics
  • mathematical models

Fingerprint

Dive into the research topics of 'Central submonads and notions of computation: Soundness, completeness and internal languages'. Together they form a unique fingerprint.

Cite this