Samson Abramsky’s wide-ranging contributions to logical and structural aspects of Computer Science have had a major influence on the field. This book is a rich collection of papers, inspired by and extending Abramsky’s work. It contains both survey material and new results, organised around six major themes: domains and duality, game semantics, contextuality and quantum computation, comonads and descriptive complexity, categorical and logical semantics, and probabilistic computation. These relate to different stages and aspects of Abramsky’s work, reflecting its exceptionally broad scope and his ability to illuminate and unify diverse topics.
Chapters in the volume include a review of his entire body of work, spanning from philosophical aspects to logic, programming language theory, quantum theory, economics and psychology, and relating it to a theory of unification of sciences using dual adjunctions. The section on game semantics shows how Abramsky’s work has led to a powerful new paradigm for the semantics of computation. The work on contextuality and categorical quantum mechanics has been highly influential, and provides the foundation for increasingly widely used methods in quantum computing. The work on comonads and descriptive complexity is building bridges between currently disjoint research areas in computer science, relating Structure to Power.
The volume also includes a scientific autobiography, and an overview of the contributions. The outstanding set of contributors to this volume, including both senior and early career academics, serve as testament to Samson Abramsky’s enduring influence. It will provide an invaluable and unique resource for both students and established researchers.
Part
1. Duality and domains in logical form.
Chapter
1. Duality,
intensionality, and contextuality: Philosophy of category theory and the
categorical unity of science in Samson Abramsky (Yoshihiro Maruyama).-
Chapter
2. Minimisation in logical form (Nick Bezhanishvili, Marcello
Bonsangue, Helle Hvid Hansen, Dexter Kozen, Clemens Kupke, Prakash
Panangaden, and Alexandra Silva).
Chapter
3. A Cooks tour of duality in
logic: From quantifiers, through Vietoris, to measures (Mai Gehrke, Tomas
Jakl, and Luca Reggio).
Chapter
4. Stone duality for relations (Alexander
Kurz, Andrew Moshier, and Achim Jung).- Part
2. Game semantics.
Chapter
5.
The mays and musts of concurrent strategies (Simon Castellan, Pierre
Clairambault, and Glynn Winskel).
Chapter
6. A tale of additives and
concurrency in game semantics (Pierre Clairambault).
Chapter
7. The far side
of the cube: An elementary introduction to game semantics (Dan Ghica).-
Chapter
8. An axiomatic account of a fully abstract game semantics for
general references (Jim Laird and Guy McCusker).
Chapter
9. Deconstructing
general references via game semantics (Andrzej S. Murawski and Nikos
Tzevelekos).
Chapter
10. The game semantics of game theory (Jules Hedges).-
Part
3. Contextuality and quantum computation.
Chapter
11. Consistency,
acyclicity, and positive semirings (Albert Atserias and Phokion G.
Kolaitis).
Chapter
12. Closing bell, boxing black box simulations in the
resource theory of contextuality (Rui Soares Barbosa, Martti Karvonen, and
Shane Mansfield).
Chapter
13. Describing and animating quantum protocols
(Richard Bornat and Rajagopal Nagarajan).
Chapter
14. The
Contextuality-by-default view of the Sheaf-Theoretic approach to
contextuality (Ehtibar Dzhafarov).
Chapter
15. Godel, Escher, Bell,
contextual semantics for logical paradoxes (Kohei Kishida).
Chapter
16.
Putting paradoxes to work: Contextuality in measurement-based quantum
computation (Robert Raussendorf).- Part
4. Game comonads and descriptive
complexity.
Chapter
17. Monadic Monadic second order logic (Mikolaj
Bojanczyk, Bartek Klin, and Julian Salamanca).
Chapter
18. Constraint
satisfaction, graph isomorphism, and the pebbling comonad (Anuj Dawar).-
Chapter
19. The strategic balance of games in logic (Jouko Vaananen).- Part
5. Categorical and logical semantics.
Chapter
20. Compositionality in
context (Alexandru Baltag, Johan van Benthem, and Dag Westerstahl).
Chapter
21. Compact inverse categories (Robin Cockett and Chris Heunen).
Chapter
22.- Reductive logic, proof-search, and Coalgebra: A perspective from
resource semantics (Alexander Gheorghiu, Simon Docherty, and David Pym).-
Chapter
23. Lambek-Grishin calculus: Focusing, display and full polarization
(Giuseppe Greco, Michael Moortgat, Valentin D. Richard, and Apostolos
Tzimoulis).
Chapter
24. On strictifying extensional reflexivity in compact
closed categories (Peter Hines).
Chapter 25.- Semantics for a Lambda
calculus for string diagrams (Bert Lindenhovius, Michael Mislove, and
Vladimir Zamdzhiev).
Chapter
26. Retracing some paths in categorical
semantics: From process-propositions-as-types to categorified reals and
computers (Dusko Pavlovic).- Part
6. Probabilistic computation.
Chapter
27.
(Towards a) Statistical probabilistic Lazy Lambda calculus (Radha
Jagadeesan).
Chapter
28. Multisets and distributions, in drawing and
learning (Bart Jacobs).
Chapter
29. Structure in machine learning (Prakash
Panangaden).
Professor Alessandra Palmigiano is the Chair of Logic and Management Theory at the Department of Ethics, Governance and Society of the School of Business and Economics at the VU Amsterdam. She is an expert in algebraic, duality-theoretic and proof-theoretic methods in logic, with a focus on the logics for social behaviour. Mehrnoosh Sadrzadeh is a Professor of Computer Science and a senior Royal Academy of Engineering Research Fellow at the department of Computer Science, University College London. Her expertise in on unified logical and statistical models of natural language with a focus on algebras of vector spaces, categorical models and substructural logics.
