This paper introduces Hilbert systems for λ-calculus, called sequent combinators, addressing many of the problems of Hilbert systems that have led to the more widespread adoption of natural deduction systems in computer science. This suggests that Hilbert systems, with their uniform approach to meta-variables and substitution, may be a more suitable framework than λ-calculus for type theories and programming languages. Two calculi are introduced here. The calculus SKIn captures λ-calculus reduction faithfully, is confluent even in the presence of meta-variables, is normalizing but not strongly normalizing in the typed case, and standardizes. The sub-calculus SKInT captures λ-reduction in slightly less obvious ways, and is a language of proof-terms not directly for intuitionistic logic, but for a fragment of S4 that we name near-intuitionistic logic. To our knowledge, SKInT is the first confluent, first-order calculus to capture λ-calculus reduction fully and faithfully and be strongly normalizing in the typed case. In particular, no calculus of explicit substitutions has yet achieved this goal.

While developing a method for reasoning about programs, Pitts defined the [top ][top ]-closed relations as an alternative to the standard admissible relations. This paper reformulates and studies Pitts's operational concept of [top ][top ]-closure in a semantic framework. It investigates the non-trivial connection between [top ][top ]-closure and admissibility, showing that [top ][top ]-closure is strictly stronger than admissibility and that every [top ][top ]-closed relation corresponds to an admissible preorder.

On December 5, 1997, a small conference was held at McGill on the occasion of Jim Lambek's 75th birthday. Subsequently it was decided to publish two volumes of papers contributed in his honour to mark this occasion: this issue of Mathematical Structures in Computer Science is one of the volumes; the other is Volume 6 of the journal Theory and Applications of Categories. At the December 1997 conference, a brief biographical essay was presented by Michael Barr and appears in the TAC volume. However, we wish to make some further remarks here.

Jim completed his Ph.D. at McGill under Hans Zassenhaus in 1950, and has remained at McGill since then. But it is of interest to note that Jim wrote two theses: the second involved biquaternions in mathematical physics, and so foreshadows a significant feature of his career: Jim has consistently shown a remarkable range of interests, from physics to linguistics, from algebra to logic, from the history and philosophy of mathematics to the theory of computing science (although he never touches a computer, to this day!). Let us just review a small sample of his more than 100 published papers.

‘Geometry and Concurrency’ is not (yet) a well-established domain of research, but consists rather of a collection of seemingly related techniques, algorithms and formalizations, coming from different application areas, and accumulated over a long period of time. There is currently a certain amount of effort being made to unify these, following the workshop ‘New Connections between Computer Science and Mathematics’ held at the Newton Institute in Cambridge, England in November 1995 (and sponsored by HP/BRIMS). More recently, the first workshop on the same subject was held in Aalborg, Denmark (see http://www.math.auc.dk/˜raussen/admin/workshop/workshop.html) where the articles of this issue, among others, were first sketched.

As a starter, and to put in context the papers by Lisbeth Fajstrup, Philippe Gaucher, Maurice Herlihy, Vaughan Pratt, Sergio Rajsbaum and Martin Raussen that appear later in this issue, I have written a brief historical note, or survey, which follows and naturally completes this foreword.

Last and not least, I must express my gratitude to Giuseppe Longo, who gave me the opportunity to act as a guest editor for this special issue, and who very kindly helped me through the many different steps that editing necessitates. My very warm thanks also go to the authors who did a very nice job, in a relatively short time. Finally, I wish to thank the referees of this issue, who found ‘bugs’ that I would not have found, and who suggested very useful improvements to the authors. The referees were Nir Shavit, Stefan Sokolowski, Christophe Tabacznyj, Jean Goubault-Larrecq, Arnaud Venet, Ian Mackie (who helped me with the survey article), Ronnie Brown and Tim Porter, as well as some of the authors who cross-checked other authors' articles, Philippe Gaucher, Martin Raussen and Lisbeth Fajstrup.

We consider types and typed lambda calculus over a finite number of ground types. We are going to investigate the size of the fraction of inhabited types of the given length n against the number of all types of length n. The plan of this paper is to find the limit of that fraction when n → ∞. The answer to this question is equivalent to finding the ‘density’ of inhabited types in the set of all types, or the so-called asymptotic probability of finding an inhabited type in the set of all types. Under the Curry–Howard isomorphism this means finding the density or asymptotic probability of provable intuitionistic propositional formulas in the set of all formulas. For types with one ground type (formulas with one propositional variable), we prove that the limit exists and is equal to 1/2 + √5/10, which is approximately 72.36%. This means that a long random type (formula) has this probability of being inhabited (tautology). We also prove that for every finite number k of ground-type variables, the density of inhabited types is always positive and lies between (4k + 1)/(2k + 1)2 and (3k + 1)/(k + 1)2. Therefore we can easily see that the density is decreasing to 0 with k going to infinity. From the lower and upper bounds presented we can deduce that at least 1/3 of classical tautologies are intuitionistic.

In this paper we consider Milner's calculus CCS enriched by a probabilistic choice operator. The calculus is given operational semantics based on probabilistic transition systems. We define operational notions of preorder and equivalence as probabilistic extensions of the simulation preorder and the bisimulation equivalence respectively. We extend existing category-theoretic techniques for solving domain equations to the probabilistic case and give two denotational semantics for the calculus. The first, ‘smooth’, semantic model arises as a solution of a domain equation involving the probabilistic powerdomain and solved in the category CONT⊥ of continuous domains. The second model also involves an appropriately restricted probabilistic powerdomain, but is constructed in the category CUM of complete ultra-metric spaces, and hence is necessarily ‘discrete’. We show that the domain-theoretic semantics is fully abstract with respect to the simulation preorder, and that the metric semantics is fully abstract with respect to bisimulation.

The λ-calculus can be represented topologically by assigning certain spaces to the types and certain continuous maps to the terms. Using a recent result from category theory, the usual calculus of λ-conversion is shown to be deductively complete with respect to such topological semantics. It is also shown to be functionally complete, in the sense that there is always a ‘minimal’ topological model in which every continuous function is λ-definable. These results subsume earlier ones using cartesian closed categories, as well as those employing so-called Henkin and Kripke λ-models.

Studies of the mathematical properties of impredicative polymorphic types have for the most part focused on the polymorphic lambda calculus of Girard–Reynolds, which is a calculus of total polymorphic functions. This paper considers polymorphic types from a functional programming perspective, where the partialness arising from the presence of fixpoint recursion complicates the nature of potentially infinite (‘lazy’) data types. An approach to Reynolds' notion of relational parametricity is developed that works directly on the syntax of a programming language, using a novel closure operator to relate operational behaviour to parametricity properties of types. Working with an extension of Plotkin's PCF with ∀-types, lazy lists and existential types, we show by example how the resulting logical relation can be used to prove properties of polymorphic types up to operational equivalence.

This paper presents a cut-elimination procedure for intuitionistic propositional logic in which cut is eliminated directly, without introducing the multiple-cut rule mix, and in which pushing cut above contraction is one of the reduction steps. The presentation of this procedure is preceded by an analysis of Gentzen's mix-elimination procedure, made in the perspective of permuting cut with contraction. We also show that in the absence of implication, pushing cut above contraction does not pose problems for directly eliminating cut.

Geometrical methods in concurrency theory (and in distributed systems theory) have appeared recently for modelling and analyzing the behaviour of systems and also for solving computability and complexity issues. We identify some of the main directions of research, and survey some of the major ideas on which all this is based (some of which are now more than thirty years old).

We consider the problem of determining the number of fixed points of a combinator (a closed λ-term). This appears to be a still unsolved problem. We give a partial answer by showing that if there is a fixed point in normal form, then this fixed point is unique or there are infinitely many fixed points.

We study continuous lattices with maps that preserve all suprema rather than only directed ones. We introduce the (full) subcategory of FS-lattices, which turns out to be *-autonomous, and in fact maximal with this property. FS-lattices are studied in the presence of distributivity and algebraicity. The theory is extremely rich with numerous connections to classical Domain Theory, complete distributivity, Topology and models of Linear Logic.

This paper focusses on the determination of the dihomotopy classes of dipaths in cubical complexes, representing the essentially different computations in a given concurrent program due to different schedules. Several new notions have to be developed, for example, the domains of dependence (Definition 2.4), which are borrowed from relativity theory (Penrose 1972). However, it turns out that the algorithm determining deadlocks and unsafe regions described in Fajstrup et al. (1998a; 1998b) can be modified and applied to do the essential calculational work.

We study a general algebraic framework that underlies a wide range of computational formalisms that use the notion of names, notably process calculi. The algebraic framework gives a rigorous basis for describing and reasoning about processes semantically, as well as offering new insights into existing constructions. The formal status of the theory is elucidated by introducing its alternative presentation, which is geometric in nature and is based on explicit manipulation of connections among nameless processes. Nameless processes and their relational theory form a coherent universe in their own right, which underlies existing graphical formalisms such as proof nets. We establish the formal equivalence between these two presentations, and illustrate how they can be used complementarily for the precise and effective description of diverse algebras and the dynamics of processes through examples.

Higher Order Matching consists of solving finite sets of equations of the form u =βηv, where u, v are simply typed terms of λ-calculus, and v is a closed term. Whether this problem is decidable is an open question. In this paper its decidability is proved when the free variables of all equations are of order at most 4 – we actually extend this result to a more general situation in which in addition to equations, disequations are also considered.

We consider processes consisting of a category of states varying over a control category as prescribed by a unique factorisation lifting functor. After a brief analysis of the structure of general processes in this setting, we restrict attention to linearly-controlled ones. To this end, we introduce and study a notion of path-linearisable category in which any two paths of morphisms with equal composites can be linearised (or interleaved) in a canonical fashion. Our main result is that categories of linearly-controlled processes (viz., processes controlled by path-linearisable categories) are sheaf models.

In Fajstrup et al. (1998a) the authors proposed a fast algorithm for deadlock detection, which was based on a geometric model of concurrency. We propose here an extension of this approach to deal with recursive processes (loops) and branchings.

Linear bicategories are a generalization of bicategories in which the one horizontal composition is replaced by two (linked) horizontal compositions. These compositions provide a semantic model for the tensor and par of linear logic: in particular, as composition is fundamentally non-commutative, they provide a suggestive source of models for non-commutative linear logic.

In a linear bicategory, the logical notion of complementation becomes a natural linear notion of adjunction. Just as ordinary adjoints are related to (Kan) extensions, these linear adjoints are related to the appropriate notion of linear extension.

There is also a stronger notion of complementation, which arises, for example, in cyclic linear logic. This sort of complementation is modelled by cyclic adjoints. This leads to the notion of a *ast;-linear bicategory and the coherence conditions that it must satisfy. Cyclic adjoints also give rise to linear monads: these are, essentially, the appropriate generalization (to the linear setting) of Frobenius algebras and the ambialgebras of Topological Quantum Field Theory.

A number of examples of linear bicategories arising from different sources are described, and a number of constructions that result in linear bicategories are indicated.

The research reported in this paper exploits the view of constraint programming as computation in a logical system, namely constraint logic. The basic ingredients of constraint logic are: constraint models for the semantics (they form a comma-category over a fixed model of ‘built-ins’); generalized polynomials in the role of basic syntactic ingredient; and a constraint satisfaction relation between semantics and syntax. Category-based constraint logic means the development of the logic is abstract categorical rather than concrete set theoretical.

We show that (category-based) constraint logic is an institution, and we internalize the study of constraint logic to the abstract framework of category-based equational logic, thus opening the door for considering constraint logic programming over non-standard structures (such as CPO's, topologies, graphs, categories, etc.). By embedding category-based constraint logic into category-based equational logic, we integrate the constraint logic programming paradigm into (category-based) equational logic programming. Results include completeness of constraint logic deduction, a novel Herbrand theorem for constraint logic programming characterizing Herbrand models as initial models in constraint logic, and logical foundations for the modular combination of constraint solvers based on amalgamated sums of Herbrand models in the constraint logic institution.

In another paper (Abramsky et al. 1999), we have developed Abramsky's analysis of Girard's Geometry of Interaction programme in detail. In this paper, our goal is to study the data ow based computational aspects of that analysis. We introduce unique decomposition categories that provide a suitable categorical framework for such computational analysis. The current study also serves to establish connections with the work on proof nets and paths by Girard and Danos and Regnier in this categorical setting. The latter goal is partially achieved here by the presentation of categorical models for dynamic algebras.