Selected papers of the conference "Algebraic and Coalgebraic Methods in Computer Science: CALCO 2011"


Editors: Bartek Klin, Andrzej Tarlecki

CALCO 2011, the 4th Conference on Algebra and Coalgebra in Computer Science, was held in Winchester, United Kingdom, August 30 -- September 2, 2011. This special issue contains extended versions of selected papers presented at the conference.

CALCO is a bi-annual event formed by joining CMCS (the International Workshop on Coalgebraic Methods in Computer Science) and WADT (the International Workshop on Algebraic Development Techniques). CALCO focuses on foundational aspects as well as both traditional and emerging uses of algebras and coalgebras in computer science, where the study of algebra and coalgebra relates to the data, process and structural aspects of software systems.

We are grateful to the University of Southampton and to the Local Organizing Committee chaired by Corina Cîrstea, for organizing the interesting and memorable event of CALCO 2011.

Proceedings of the conference with the original contributions by invited speakers and submissions selected by the Programme Committee were published by Springer-Verlag as volume 6859 of Lecture Notes in Computer Science.

The seven papers in this collection were invited by the guest editors, based on the evaluation by the Programme Committee and subreferees. All submitted papers were peer-reviewed according to the usual high standards of LMCS.

We would like to thank the authors of the papers in this special issue for their excellent submissions, and the referees for their careful and thorough work.

Andrea Corradini and Bartek Klin
Guest Editors & PC Chairs of CALCO 2011

1. Indexed Induction and Coinduction, Fibrationally

Neil Ghani ; Patricia Johann ; Clement Fumex.
This paper extends the fibrational approach to induction and coinduction pioneered by Hermida and Jacobs, and developed by the current authors, in two key directions. First, we present a dual to the sound induction rule for inductive types that we developed previously. That is, we present a sound coinduction rule for any data type arising as the carrier of the final coalgebra of a functor, thus relaxing Hermida and Jacobs' restriction to polynomial functors. To achieve this we introduce the notion of a quotient category with equality (QCE) that i) abstracts the standard notion of a fibration of relations constructed from a given fibration; and ii) plays a role in the theory of coinduction dual to that played by a comprehension category with unit (CCU) in the theory of induction. Secondly, we show that inductive and coinductive indexed types also admit sound induction and coinduction rules. Indexed data types often arise as carriers of initial algebras and final coalgebras of functors on slice categories, so we give sufficient conditions under which we can construct, from a CCU (QCE) U:E \rightarrow B, a fibration with base B/I that models indexing by I and is also a CCU (resp., QCE). We finish the paper by considering the more general case of sound induction and coinduction rules for indexed data types when the indexing is itself given by a fibration.

2. Coalgebraic Characterizations of Context-Free Languages

Joost Winter ; Jan J. M. Rutten ; Marcello M. Bonsangue.
In this article, we provide three coalgebraic characterizations of the class of context-free languages, each based on the idea of adding coalgebraic structure to an existing algebraic structure by specifying output-derivative pairs. Final coalgebra semantics then gives an interpretation function into the final coalgebra of all languages with the usual output and derivative operations. The first characterization is based on systems, where each derivative is given as a finite language over the set of nonterminals; the second characterization on systems where derivatives are given as elements of a term-algebra; and the third characterization is based on adding coalgebraic structure to a class of closed (unique) fixed point expressions. We prove equivalences between these characterizations, discuss the generalization from languages to formal power series, as well as the relationship to the generalized powerset construction.

3. Exploring the Boundaries of Monad Tensorability on Set

Nathan Bowler ; Sergey Goncharov ; Paul Blain Levy ; Lutz Schröder.
We study a composition operation on monads, equivalently presented as large equational theories. Specifically, we discuss the existence of tensors, which are combinations of theories that impose mutual commutation of the operations from the component theories. As such, they extend the sum of two theories, which is just their unrestrained combination. Tensors of theories arise in several contexts; in particular, in the semantics of programming languages, the monad transformer for global state is given by a tensor. We present two main results: we show that the tensor of two monads need not in general exist by presenting two counterexamples, one of them involving finite powerset (i.e. the theory of join semilattices); this solves a somewhat long-standing open problem, and contrasts with recent results that had ruled out previously expected counterexamples. On the other hand, we show that tensors with bounded powerset monads do exist from countable powerset upwards.

4. Bases as Coalgebras

Bart Jacobs.
The free algebra adjunction, between the category of algebras of a monad and the underlying category, induces a comonad on the category of algebras. The coalgebras of this comonad are the topic of study in this paper (following earlier work). It is illustrated how such coalgebras-on-algebras can be understood as bases, decomposing each element x into primitives elements from which x can be reconstructed via the operations of the algebra. This holds in particular for the free vector space monad, but also for other monads, like powerset or distribution. For instance, continuous dcpos or stably continuous frames, where each element is the join of the elements way below it, can be described as such coalgebras. Further, it is shown how these coalgebras-on-algebras give rise to a comonoid structure for copy and delete, and thus to diagonalisation of endomaps like in linear algebra.

5. Relation lifting, with an application to the many-valued cover modality

Marta Bilkova ; Alexander Kurz ; Daniela Petrisan ; Jiri Velebil.
We introduce basic notions and results about relation liftings on categories enriched in a commutative quantale. We derive two necessary and sufficient conditions for a 2-functor T to admit a functorial relation lifting: one is the existence of a distributive law of T over the "powerset monad" on categories, one is the preservation by T of "exactness" of certain squares. Both characterisations are generalisations of the "classical" results known for set functors: the first characterisation generalises the existence of a distributive law over the genuine powerset monad, the second generalises preservation of weak pullbacks. The results presented in this paper enable us to compute predicate liftings of endofunctors of, for example, generalised (ultra)metric spaces. We illustrate this by studying the coalgebraic cover modality in this setting.

6. Linear usage of state

Rasmus Ejlers Møgelberg ; Sam Staton.
We investigate the phenomenon that "every monad is a linear state monad". We do this by studying a fully-complete state-passing translation from an impure call-by-value language to a new linear type theory: the enriched call-by-value calculus. The results are not specific to store, but can be applied to any computational effect expressible using algebraic operations, even to effects that are not usually thought of as stateful. There is a bijective correspondence between generic effects in the source language and state access operations in the enriched call-by-value calculus. From the perspective of categorical models, the enriched call-by-value calculus suggests a refinement of the traditional Kleisli models of effectful call-by-value languages. The new models can be understood as enriched adjunctions.

7. Corecursive Algebras, Corecursive Monads and Bloom Monads

Jiří Adámek ; Mahdie Haddadi ; Stefan Milius.
An algebra is called corecursive if from every coalgebra a unique coalgebra-to-algebra homomorphism exists into it. We prove that free corecursive algebras are obtained as coproducts of the terminal coalgebra (considered as an algebra) and free algebras. The monad of free corecursive algebras is proved to be the free corecursive monad, where the concept of corecursive monad is a generalization of Elgot's iterative monads, analogous to corecursive algebras generalizing completely iterative algebras. We also characterize the Eilenberg-Moore algebras for the free corecursive monad and call them Bloom algebras.