Computer Science has witnessed the emergence of a plethora of different logics, models and paradigms for the description of computation. Yet, the classic Church–Turing thesis may be seen as indicating that all general models of computation are equivalent. Alan Perlis referred to this as the ‘Turing tarpit’, and argued that some of the most crucial distinctions in computing methodology, such as sequential versus parallel, deterministic versus non-deterministic, local versus distributed disappear if all one sees in computation is pure symbol pushing. How can we express formally the difference between these models of computation?

We present a calculus of mobile processes without prefix or summation, called the solos calculus. Using two different encodings, we show that the solos calculus can express both action prefix and guarded summation. One encoding gives a strong correspondence, but uses a match operator; the other yields a slightly weaker correspondence, but uses no additional operators. We also show that the expressive power of the solos calculus is still retained by the sub-calculus where actions carry at most two names. On the other hand, expressiveness is lost in the solos calculus without match and with actions carrying at most one name.

The intersection-types discipline for λ-calculus was introduced in Coppo and Dezani-Ciancaglini (1980) as an extension of Curry's type assignment system. The motivation was essentially to increase the class of terms possessing types. Indeed, it turned out that this discipline can assign types to all and only the strongly normalising terms. This is largely a folklore result; the first published proof appears in Pottinger (1980). Subsequently, the intersection-types discipline was used in Barendregt et al. (1983) as a tool for proving Scott's conjecture concerning the completeness of the set-theoretic semantics for simple types.

The ambient calculus is a process calculus for describing mobile computation. We develop a theory of Morris-style contextual equivalence for proving properties of mobile ambients. We prove a context lemma that allows derivation of contextual equivalences by considering contexts of a particular limited form, rather than all arbitrary contexts. We give an activity lemma that characterises the possible interactions between a process and a context. We prove several examples of contextual equivalence. The proofs depend on characterising reductions in the ambient calculus in terms of a labelled transition system.

During the last few years it has become increasingly clear that a very wide variety of state-based dynamical systems, such as transition systems, automata, process calculi and class-based systems can be captured uniformly as coalgebras. Moreover, the theory and applications of coalgebras is developing into a field of interest in its own right, presenting a deep mathematical foundation, a growing range of applications and interactions with various other areas, such as reactive and interactive system theory, object-oriented and concurrent programming, formal system specification, modal logic, dynamical systems, control systems, category theory, algebra, analysis, and so on.

We address the question of injectivity of coherent semantics of linear logic proof-nets. Starting from Girard's definition of experiment, we introduce the key-notion of ‘injective obsessional experiment’, which allows us to give a positive answer to our question for certain fragments of linear logic, and to build counter-examples to the injectivity of coherent semantics in the general case.

A concept of equation morphism is introduced for every endofuctor $F$ of a cocomplete category $\Ce$. Equationally defined classes of $F$-algebras for which free algebras exist are called varieties. Every variety is proved to be monadic over $\Ce$, and, conversely, every monadic category is equivalent to a variety. The Birkhoff Variety Theorem is also proved for $`{\sf Set}\hbox{-like}'$ categories.

By dualising, we arrive at a concept of coequation such that covarieties, that is, coequationally specified classes of coalgebras with cofree objects, correspond precisely to comonadic categories. Natural examples of covarieties are presented.

This paper presents a simple and powerful diagrammatic framework for dealing with specifications in computer science. Following a classical line, we define diagrammatic specifications as a kind of generalised sketch. In addition, the specifications themselves are defined as the realisations of projective sketches. This meta level provides adjunction properties: this is due to a well-known result of Ehresmann. Moreover, we prove in this paper that this meta level also provides an efficient definition of deduction. This work results from a collaboration with Christian Lair.

The purpose of this note is to give a methodologically simple proof of the undecidability of strong normalisation in the pure lambda calculus. For this we show how to represent an arbitrary partial recursive function by a term whose application to any Church numeral is either strongly normalizable or has no normal form. Intersection types are used for the strong normalization argument.

The Asynchronous $\pi$-calculus, proposed in Honda and Tokoro (1991) and, independently, in Boudol (1992), is a subset of the $\pi$-calculus (Milner et al. 1992), which contains no explicit operators for choice and output prefixing. The communication mechanism of this calculus, however, is powerful enough to simulate output prefixing, as shown in Honda and Tokoro (1991) and Boudol (1992), and input-guarded choice, as shown in Nestmann and Pierce (2000). A natural question arises, then, as to whether or not it is as expressive as the full $\pi$-calculus. We show that this is not the case. More precisely, we show that there does not exist any uniform, fully distributed translation from the $\pi$-calculus into the asynchronous $\pi$-calculus, up to any ‘reasonable’ notion of equivalence. This result is based on the incapability of the asynchronous $\pi$-calculus to break certain symmetries that may be present in the initial communication graph. By similar arguments, we prove a separation result between the $\pi$-calculus and CCS, and between the $\pi$-calculus and the $\pi$-calculus with internal mobility, a subset of the $\pi$-calculus proposed by Sangiorgi where the output actions can only transmit private names.

We review the conceptual development of (true) concurrency and branching time starting from Petri nets and proceeding via Mazurkiewicz traces, pomsets, bisimulation, and event structures up to higher dimensional automata (HDAs), whose acyclic case may be identified with triadic event structures and triadic Chu spaces. Acyclic HDAs may be understood as extending the two truth values of Boolean logic with a third value $\T$ expressing transition. We prove the necessity of such a third value under mild assumptions about the nature of observable events, and show that the expansion of any complete Boolean basis $L$ to $L_{\T}$ with a third literal $\that a$ expressing $a=\T$ forms an expressively complete basis for the representation of acyclic HDAs. The main contribution is a new value $\cancel$ of cancellation, which is a sibling of $\T$, serving to distinguish $a(b+c)$ from $ab+ac$ while simplifying the extensional definitions of termination $\tick\A$ and sequence $\A\B$. We show that every HDAX (acyclic HDA with $\cancel$) is representable in the expansion of $L_{\T}$ to $L_{\T\cancel}$ with a fourth literal $\can a$ expressing $a=\cancel$.

We refine the simulation technique introduced in Di Cosmo and Kesner (1997) to show strong normalisation of $\l$-calculi with explicit substitutions via termination of cut elimination in proof nets (Girard 1987). We first propose a notion of equivalence relation for proof nets that extends the one in Di Cosmo and Guerrini (1999), and show that cut elimination modulo this equivalence relation is terminating. We then show strong normalisation of the typed version of the $\ll$-calculus with de Bruijn indices (a calculus with full composition defined in David and Guillaume (1999)) using a translation from typed $\ll$ to proof nets. Finally, we propose a version of typed $\ll$ with named variables, which helps to give a better understanding of the complex mechanism of the explicit weakening notation introduced in the $\ll$-calculus with de Bruijn indices (David and Guillaume 1999).

We present the dual to Birkhoff's variety theorem in terms of predicates over the carrier of a cofree coalgebra (that is, in terms of ‘coequations’). We then discuss the dual to Birkhoff's completeness theorem, showing how closure under deductive rules dualises to yield two modal operators acting on coequations. We discuss the properties of these operators and show that they commute. We prove as our main result the invariance theorem, which is the formal dual of Birkhoff's completeness theorem.

We provide a consistent way of looking at a range of finite state machines and their algebraic models. Our claim is that the natural representation of transitions of finite state machines is in terms of monoid homomorphisms, and distinct generalisation processes that can be applied to finite state machines correspond to distinct categorical generalisation processes at the level of the algebraic models.

The generalisations we consider are those from deterministic to non-deterministic machines, from one-way to two-way machines, and from read-only machines to read/write machines. Hence the finite state machines we consider, and provide algebraic models for, are (deterministic and non-deterministic) finite state automata, two-way automata, Mealy machines, and bounded Turing machines.

The categorical constructions corresponding to these generalisation processes are, respectively: altering the base category from functions to relations, applying the Geometry of Interaction, or Int construction, and a categorical process, which we refer to as the Comp construction, that uses the tensor on monoidal categories to construct graded categories.

Connections between the sequentiality/concurrency distinction and the semantics of proofs are investigated, with particular reference to games and Linear Logic.

This paper presents a novel method for comparing computational properties of λ-terms that are typeable with intersection types, with respect to terms that are typeable with Curry types. We introduce a translation from intersection typing derivations to Curry typeable terms that is preserved by β-reduction: this allows the simulation of a computation starting from a term typeable in the intersection discipline by means of a computation starting from a simply typeable term. Our approach proves strong normalisation for the intersection system naturally by means of purely syntactical techniques. The paper extends the results presented in Bucciarelli et al. (1999) to the whole intersection type system of Barendregt, Coppo and Dezani, thus providing a complete proof of the conjecture, proposed in Leivant (1990), that all functions uniformly definable using intersection types are already definable using Curry types.

We consider the Pure Safe Ambient Calculus, which is Levi and Sangiorgi's Safe Ambient Calculus (a variant of Cardelli and Gordon's Mobile Ambient Calculus) restricted to its mobility primitives – in particular, we focus on its expressive power. Since it has no form of communication or substitution, we show how these notions can be simulated by mobility and modifications in the hierarchical structure of ambients. As a main result, we use these techniques to design an encoding of the synchronous $\pi$-calculus into pure ambients, and we study its correctness, thus showing that pure ambients are as expressive as the $\pi$-calculus. In order to simplify the proof and give an intuitive understanding of the encoding, we design an intermediate language, the $\pi$-Calculus with Explicit Substitutions and Channels, which is an extension of the $\pi$-calculus in which communication and substitution are broken into simpler steps, and we show that is has the same expressive power as the $\pi$-calculus.

Concrete computing machines, either sequential or concurrent, rely on an intimate relationship between computation and time. We recall the general characteristic properties of physical time and of present realisations of computing systems. We emphasise the role of computing interferences, that is, the necessity of avoiding them in order to give a causal implementation to logical operations. We compare synchronous and asynchronous systems, and give a brief survey of some methods used to deal with computing interferences. Using a graphic representation, we show that synchronous and asynchronous circuits reflect the same opposition as the Newtonian and relativistic causal structures for physical space-time.

This paper is part of a general programme of treating explicit substitutions as the primary λ-calculi from the point of view of foundations as well as applications. We work in a composition-free calculus of explicit substitutions and an augmented calculus obtained by adding explicit garbage-collection, and explore the relationship between intersection-types and reduction.

We show that the terms that normalise by leftmost reduction and the terms that normalise by head reduction can each be characterised as the terms typable in a certain system. The relationship between typability and strong normalisation is subtly different from the classical case: we show that typable terms are strongly normalising but give a counterexample to the converse. Our notions of leftmost and head reduction are non-deterministic, and our normalisation theorems apply to any computations obeying these strategies. In this way we refine and strengthen the classical normalisation theorems. The proofs require some new techniques in the presence of reductions involving explicit substitutions. Indeed, our proofs do not rely on results from classical λ-calculus, which in our view is subordinate to the calculus of explicit substitution.

Every finitary endofunctor of $\Set$ is proved to generate a free iterative theory in the sense of Elgot. This work is based on coalgebras, specifically on parametric corecursion, and the proof is presented for categories more general than just $\Set$.