PCARC 2010: July 9

Partial Combinatory Algebras in Realizability and Computability

associated with LICS


Partial Combinatory Algebras (PCAs) and their various generalizations have played an important role in several foundational areas of logic and computer science. Not only do they include models of the lambda calculus and related theories (both total and partial), but also they form the basic building blocks for the construction of realizability settings, and categories of PERs. These latter structures play an important role in the semantics of programming languages.

It is already known that several constructions from classical computability theory can be generalized to the level of PCAs. Conversely, recent efforts to provide abstract categorical settings for computability can be shown to arise from a generalization of PCAs. This makes the deeper understanding of the structural properties of PCAs a central issue in these abstract approaches to computability.

Different applications of PCAs call for different notions of morphisms and hence give rise to different categories of PCAs. Understanding the structural aspects of these categories is one of the challenges of this area. The study of PCAs involves a broad range of techniques from the very syntactic (rewriting theory) to the very semantic (categorical techniques).

This workshop will bring together representatives and experts from these different and related areas. We hope it will stimulate interactions and collaborations, leading to new perspectives on how these viewpoints can be unified.

More information can be found here.


Program Chairs

Pieter Hofstra, University of Ottawa, Canada

Program Committee: