Duality in Computer Science
( 25. Oct – 30. Oct, 2015 )
- Mai Gehrke (University of Paris VII, FR)
- Achim Jung (University of Birmingham, GB)
- Victor Selivanov (A. P. Ershov Institute - Novosibirsk, RU)
- Dieter Spreen (Universität Siegen, DE)
- Dagmar Glaser (für administrative Fragen)
Duality allows one to move between an algebraic world of properties and a spacial world of individuals and their dynamics, thereby leading to a change of perspective that may, and often does, lead to new insights. Because computer science is fundamentally concerned both with specification of programs and the dynamics of their executions, dualities have given rise to active research in a number of areas of theoretical computer science.
In this seminar, we will focus on applications of duality to semantics for probability in computation, to algebra and coalgebra, and on applications in complexity theory. We want to bring together researchers from these communities within computer science as well as from mathematics with the goal of uncovering commonalities, forging new collaborations, and sharing tools and techniques between areas based on their common use of topological methods and duality.
Duality and probability in computation The very definition of probability, based on the real numbers, creates numerous challenges in the otherwise discrete world of computation. Structures such as graphs and transition systems lose their discrete character when enriched with probabilistic features while classical approaches to probability assume topological properties that are not encompassed by existing semantics in computer science.
Much of the work in the area has therefore focused on extending established theories, e.g. by defining probabilities over non-Hausdorff spaces, and, extending ideas going back to Riesz, it has been recognized that duality theory and coalgebra can play a major role in addressing the issues.
Making probability accessible to computation in a more practical sense has also been a challenge. The real numbers themselves are clearly not finite, nor even a “constructive space” and questions of computability present themselves. To establish a connection to logics (for verification purposes, for example) is also a major challenge as established techniques are not immediately applicable.
Duality and algebra and coalgebra In logic, dualities have been used in order to relate syntactic and semantic approaches. Stone's original result is in fact of this type as it shows that clopen subsets of Stone spaces provide complete semantics for classical propositional logic. This base case has been generalized in various directions. One general scheme underlying such work relates the Lindenbaum algebra of a logic with relational semantics via Jónsson-Tarski duality. For infinitary logics, Stone-type dualities have also played an important role starting with Scott's groundbreaking first model of the lambda-calculus leading to Abramsky's seminal work on Domain's in Logical Form.
A closely related point of view is provided by the coalgebraic approach to logics. The basic idea is that coalgebras are given parametrically with respect to an endofunctor F on a category C. The logic part of coalgebraic logic comes from the search for a logical counterpart of a given coalgebraic semantics. In the base cases, such as modal logic this is provided by applying Stone duality to the underlying category of spaces and translating the endofunctor across the duality to obtain dual algebras. Much work in coalgebraic logic either seeks to generalize existing work in duality to a broader parametric setting or at least to a more categorical framework, or it grapples with the same issues as mentioned above capturing various constructs or various types of spaces.
Duality and complexity theory While the use of Stone duality in semantics is well established, uses in complexity theory are much more recent and rare. In this direction, we want to bring together researchers from formal language theory, computability theory, and researchers working on the Constraint Satisfaction Problem (CSP) using topological methods in order to explore connections between these novel applications and the classical ones.
The connection between profinite words and Stone spaces has recently been developed leading to a generalization of Eilenberg-Reiterman theory and a novel connection to methods in semantics. In computability theory, hierarchies and associated reducibility relations provide a means of measuring complexity. In applications of such hierarchies their characterization in terms of so-called alternating trees is of principal importance. Using Priestley duality, Selivanov has recently shown that a version of alternating trees and reducibilities exist for a rather general class of hierarchies.
The aim in constraint satisfaction problems (CSP) is to find an assignment of values to a given set of variables, subject to constraints on the values, which can be assigned simultaneously to certain specified subsets of variables. A wide variety of computational problems may be modelled as CSPs and thus they are highly applicable. One of the most fruitful approaches for studying the complexity and algorithms for CSPs on finite structures applies universal algebra. Recent discoveries have made it possible to transfer the algebraic approach to some classes of the infinite CSP bringing the product topology of algebraic clones into play. In addition, results on Ramsey theory and topological dynamics also play a role. Relating these topological methods to the more established ones is a central goal of the seminar.
Aims of the seminar
Duality allows one to move between an algebraic world of properties and a spacial world of individuals and their dynamics, thereby leading to a change of perspective that may, and often does, lead to new insights. Because computer science is fundamentally concerned both with specification of programs and the dynamics of their executions, dualities have given rise to active research in a number of areas of theoretical computer science. In this seminar we particularly wanted to concentrate on applications of duality in semantics for continuous data with special focus on probability in computation, algebra and coalgebra, and applications in complexity theory.
Our call for participation was exceptionally successful and right up to the actual start of the meeting we were in danger of exceeding the number of places allocated. We see this as a vindication of our aim of bringing these researchers together for exchanging ideas centred around the common topic of duality. The talks offered fell quite naturally into groupings which allowed us to adopt a fairly thematic programme structure:
- Day 1, morning session: Duality and classical algebra. Talks by Libor Barto, Michael Pinsker, Max Dickmann, and Marcus Tressl.
- Day 1, afternoon session: Duality and categories. Talks by Paul Taylor, Steve Vickers, and Pino Rosolini.
- Day 2, morning session: Duality and topology. Talks by Matthew de Brecht, Mathias Schröder, Reinhold Heckmann, and Jean Goubault-Larrecq.
- Day 2, afternoon session: Alternative views on duality. Talks by Niels Schwartz, George Hansoul, Rob Myers, and Alexander Kurz.
- Day 3, morning session: Duality and coalgebra. Talks by Adriana Balan, Dirk Pattinson, Ulrich Berger, and Samuel J. van Gool.
- Day 4, morning session: Duality and domain theory. Talks by Jimmie Lawson, Abbas Edalat, Achim Jung, and Klaus Keimel.
- Day 4, afternoon session: Duality and logic. Talks by Peter Schuster, Martín Escardé, Vladimir Shavrukov, and Vasco Brattka.
- Day 5, morning session: Duality and probability. Talks by Willem Fouché, Dexter Kozen, Daniela Petric san, and Drew Moshier.
As always, Dagstuhl staff were incredibly efficient and helpful which allowed all of us, including the organisers, to focus on the exchange of ideas and plans for joint work. We are sincerely grateful to them for their hospitality and professionalism.
Mai Gehrke (LIAFA, CNRS and University Paris Diderot)
Achim Jung (School of Computer Science, University of Birmingham)
Victor Selivanov (Institute of Informatics Systems, RAS, Novosibirsk)
Dieter Spreen (Math. Logik und Theoretische Informatik, Universität Siegen)
- Adriana Balan (University Politehnica of Bucharest, RO) [dblp]
- Libor Barto (Charles University - Prague, CZ) [dblp]
- Ulrich Berger (Swansea University, GB) [dblp]
- Nick Bezhanishvili (University of Amsterdam, NL) [dblp]
- Vasco Brattka (Universität der Bundeswehr - München, DE) [dblp]
- Matthew de Brecht (NICT - Osaka, JP) [dblp]
- Max Dickmann (University of Paris VII, FR) [dblp]
- Abbas Edalat (Imperial College London, GB) [dblp]
- Martín H. Escardó (University of Birmingham, GB) [dblp]
- Willem L. Fouché (UNISA - Pretoria, ZA) [dblp]
- Silvio Ghilardi (University of Milan, IT) [dblp]
- Jean Goubault-Larrecq (ENS - Cachan, FR) [dblp]
- Georges Hansoul (University of Liège, BE) [dblp]
- Reinhold Heckmann (AbsInt - Saarbrücken, DE) [dblp]
- Achim Jung (University of Birmingham, GB) [dblp]
- Klaus Keimel (TU Darmstadt, DE) [dblp]
- Dexter Kozen (Cornell University, US) [dblp]
- Andreas Krebs (Universität Tübingen, DE) [dblp]
- Clemens Kupke (University of Strathclyde, GB) [dblp]
- Alexander Kurz (University of Leicester, GB) [dblp]
- Jimmie D. Lawson (Louisiana State University - Baton Rouge, US) [dblp]
- Matteo Mio (ENS - Lyon, FR) [dblp]
- M. Andrew Moshier (Chapman University - Orange, US) [dblp]
- Robert Myers (London, GB) [dblp]
- Dirk Pattinson (Australian National University - Canberra, AU) [dblp]
- Daniela Petrisan (University of Paris VII, FR) [dblp]
- Michael Pinsker (Charles University - Prague, CZ) [dblp]
- Luca Reggio (University of Paris VII, FR)
- Giuseppe Rosolini (University of Genova, IT) [dblp]
- Matthias Schröder (TU Darmstadt, DE) [dblp]
- Peter M. Schuster (University of Verona, IT) [dblp]
- Niels Schwartz (Universität Passau, DE) [dblp]
- Victor Selivanov (A. P. Ershov Institute - Novosibirsk, RU) [dblp]
- Vladimir Shavrukov (Utrecht, NL)
- Alex Simpson (University of Ljubljana, SI) [dblp]
- Dieter Spreen (Universität Siegen, DE) [dblp]
- Paul Taylor (Honorary Member of University of Birmingham, GB) [dblp]
- Marcus Tressl (Manchester University, GB) [dblp]
- Sam van Gool (City University of New York, US) [dblp]
- Yde Venema (University of Amsterdam, NL) [dblp]
- Steven J. Vickers (University of Birmingham, GB) [dblp]
- Klaus Weihrauch (FernUniversität in Hagen, DE) [dblp]
- Dagstuhl-Seminar 13311: Duality in Computer Science (2013-07-28 - 2013-08-02) (Details)
- data structures / algorithms / complexity
- semantics / formal methods
- verification / logic
- Stone duality
- domain theory
- semantics of non-classical logics
- probabilistic systems