Published: 29th December 2021
DOI: 10.4204/EPTCS.351
ISSN: 2075-2180

EPTCS 351

Proceedings 37th Conference on
Mathematical Foundations of Programming Semantics
Hybrid: Salzburg, Austria and Online, 30th August - 2nd September, 2021

Edited by: Ana Sokolova

Preface
Ana Sokolova
An ML-style Record Calculus with Extensible Records
Sandra Alves and Miguel Ramos
1
Categorical Semantics of Reversible Pattern-Matching
Kostia Chardonnet, Louis Lemonnier and Benoît Valiron
18
Monads for Measurable Queries in Probabilistic Databases
Swaraj Dash and Sam Staton
34
A General Glivenko–Gödel Theorem for Nuclei
Giulio Fellin and Peter Schuster
51
A Cartesian Bicategory of Polynomial Functors in Homotopy Type Theory
Eric Finster, Samuel Mimram, Maxime Lucas and Thomas Seiller
67
Traced Monoidal Categories as Algebraic Structures in Prof
Nick Hu and Jamie Vicary
84
Multinomial and Hypergeometric Distributions in Markov Categories
Bart Jacobs
98
Learning from What's Right and Learning from What's Wrong
Bart Jacobs
116
Sharp Elements and Apartness in Domains
Tom de Jong
134
Join Inverse Rig Categories for Reversible Functional Programming, and Beyond
Robin Kaarsgaard and Mathys Rennela
152
From Semantics to Types: the Case of the Imperative lambda-Calculus
Ugo de'Liguoro and Riccardo Treglia
168
Syntactic Regions for Concurrent Programs
Samuel Mimram and Aly-Bora Ulusoy
184
Two Guarded Recursive Powerdomains for Applicative Simulation
Rasmus Ejlers Møgelberg and Andrea Vezzosi
200
Semialgebras and Weak Distributive Laws
Daniela Petrişan and Ralph Sarkis
218
On Star Expressions and Completeness Theorems
Todd Schmid, Jurriaan Rot and Alexandra Silva
242
Inductive and Coinductive Predicate Liftings for Effectful Programs
Niccolò Veltri and Niels F.W. Voorneveld
260
A Compositional Approach to Parity Games
Kazuki Watanabe, Clovis Eberhart, Kazuyuki Asada and Ichiro Hasuo
278
Canonical Automata via Distributive Law Homomorphisms
Stefan Zetzsche, Gerco van Heerdt, Matteo Sammartino and Alexandra Silva
296

Preface

This volume contains the proceedings of the 37th International Conference of Mathematical Foundations of Programming Semantics (MFPS) held as one of the first hybrid (online and onsite) conferences during the corona virus pandemic, from the University of Salzburg, Austria. The conference took place from August 30 to September 2, 2021. The local organization was lead by myself, with a great team of "local" organizers including Henning Basold (University of Leiden), Adriana Pratter (University of Salzburg), Jurriaan Rot (Radboud University Nijmegen), Sarah Sallinger (TU Vienna), and Michael Starzinger (University of Salzburg), that I cordially thank for their support. Many thanks go to the MFPS Organizers (Steering Committee), in particular Michael Mislove, for the guidance and financial support. Like in 2015, 2017, and 2019, MFPS was colocated with the Conference on Algebra and Coalgebra in Computer Science (CALCO). The majority of the record number of registered participants took part online, a happy small fraction was able to enjoy the normal-conference experience.

MFPS conferences are dedicated to the areas of mathematics, logic, and computer science that are related to models of computation in general, and to semantics of programming languages in particular. This is a forum where researchers in mathematics and computer science can meet and exchange ideas.

Topics include, but are not limited to, the following: bio-computation; concurrent qualitative and quantitative distributed systems; process calculi; probabilistic systems; constructive mathematics; domain theory and categorical models; formal languages; formal methods; game semantics; lambda calculus; programming-language theory; quantum computation; security; topological models; logic; type systems; type theory.

MFPS 2021 continued the tradition of having an exciting group of invited speakers and special session organizers and speakers: We enjoyed listening to four invited talks by Eugenia Cheng (School of the Art Institute of Chicago), joint with CALCO, Amina Doumane (ENS Lyon), Shin-ya Katsumata (NII Tokyo), and Krishna S. (IIT Bombay). In addition, MFPS had four special sessions: (1) Special Session on Termination Analysis and Synthesis, joint with CALCO, organized by Azadeh Farzan (University of Toronto) with Zachary Kincaid (Princeton University) and Florian Zuleger (TU Vienna); (2) Special Session on Probabilistic Programming Semantics organized by Sam Staton (University of Oxford) with Tobias Fritz (University of Innsbruck) and Alex Simpson (University of Ljubljana); (3) Special Session on Categorical Type Theory organized by Paul-André Melliès (IRIF, Université Paris Denis Diderot) with Raphaëlle Crubillé (LORIA, Nancy), Nicolò Veltri (Taltech) and Noam Zeilberger (École Polytechnique); and (4) Special Session on String Diagrams organized by Filippo Bonchi (University of Pisa) and Pawel Sobocinski (Taltech) with Brendan Fong (Topos Institute) and Fabio Zanasi (UCL).

The conference received submissions from Canada, Denmark, Estonia, France, Italy, Japan, Netherlands, Portugal, Russia, Sweden, United Kingdom, and Unites States. There were 25 submissions of which 18 were accepted. I thank all programme committee members and external reviewers for their work. The 18 accepted papers are published in this volume (in alphabetical order of the names of first authors). I wish you enjoy reading the papers in this volume as much as we enjoyed listening to the talks.


December 2021,       Ana Sokolova



Programme Committee

 Sandra Alves, University of Porto, Portugal
 Henning Basold, University of Leiden, Netherlands
 Andrej Bauer, University of Ljubljana, Slovenia
 Stephen Brookes, Carnegie Mellon University, USA
 Corina Cirstea, University of Southampton, UK
 Fabio Gadducci, University of Pisa, Italy
 Ichiro Hasuo, NII, Japan
 Helle Hvid Hansen, University of Groningen, Netherlands
 Justin Hsu, University of Wisconsin-Madison, USA
 Patricia Johann, Appalachian State University, USA
 Achim Jung, University of Birmingham, UK
 Sandra Kiefer, RWTH Aachen University, Germany / University of Warsaw, Poland
 Barbara König, University of Duisburg-Essen, Germany
 Catherine Meadows, NRL, USA
 Michael Mislove, Tulane University, USA
 Joel Ouaknine, Max Planck Institute for Software Systems, Germany
 Prakash Panangaden, McGill University Montreal, Canada
 Daniela Petrisan, IRIF, Paris 7, France
 Tatjana Petrov, University of Konstanz, Germany
 Jurriaan Rot, Radboud University Nijmegen, Netherlands
 Mehrnoosh Sadrzadeh, UCL, UK
 Lutz Schröder, Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany
 Ana Sokolova, University of Salzburg, Austria (chair)
 Valeria Vignudelli, CNRS/ENS Lyon, France



Organizers (Steering Committee)

 Andrej Bauer, University of Ljubljana, Slovenia
 Stephen Brookes, Carnegie Mellon University, USA
 Achim Jung, University of Birmingham, UK
 Catherine Meadows, NRL, USA
 Michael Mislove, Tulane University, USA (chair)
 Joel Ouaknine, Max Planck Institute for Software Systems, Germany
 Prakash Panangaden, McGill University Montreal, Canada



External Reviewers

 Clément Aubert
 Rebecca Bernemann
 Pierre Cagne
 Jacques Carette
 Jim de Groot
 Elena Di Lavore
 Ivan Di Liberti
 Bartek Klin
 Cristina Matache
 Joshua Moerman
 Sean Moss
 Fredrik Nordvall Forsberg
 Atsushi Ohori
 Maciej Piróg
 Aloïs Rosset
 Stefano Tognazzi
 Davide Trotta
 Henning Urbat