**Contemporary Mathematics**

Volume: 92;
1989;
382 pp;
Softcover

MSC: Primary 18;
Secondary 00; 03; 68

Print ISBN: 978-0-8218-5100-5

Product Code: CONM/92

List Price: $66.00

AMS Member Price: $52.80

MAA Member Price: $59.40

**Electronic ISBN: 978-0-8218-7680-0
Product Code: CONM/92.E**

List Price: $66.00

AMS Member Price: $52.80

MAA Member Price: $59.40

# Categories in Computer Science and Logic

Share this page *Edited by *
*John W. Gray; Andre Scedrov*

Category theory has had important uses in logic since the invention of topos theory in the early 1960s, and logic has always been an important component of theoretical computer science. A new development has been the increase in
direct interactions between category theory and computer science. In June
1987, an AMS-IMS-SIAM Summer Research Conference on Categories in Computer
Science and Logic was held at the University of Colorado in Boulder. The aim
of the conference was to bring together researchers working on the
interconnections between category theory and computer science or between
computer science and logic. The conference emphasized the ways in which the
general machinery developed in category theory could be applied to specific
questions and be used for category-theoretic studies of concrete problems.
This volume represents the proceedings of the conference. (Some of the
participants' contributions have been published elsewhere.)

The papers published here relate to three different aspects of the conference. The first concerns topics relevant to all three fields, including, for example, Horn logic, lambda calculus, normal form reductions, algebraic theories, and categorical models for computability theory. In the area of logic, topics
include semantical approaches to proof-theoretical questions, internal
properties of specific objects in (pre-) topoi and their representations, and
categorical sharpening of model-theoretic notions. Finally, in the area of
computer science, the use of category theory in formalizing aspects of
computer programming and program design is discussed.

# Table of Contents

## Categories in Computer Science and Logic

- Contents vii8 free
- Preface ix10 free
- Models of Horn theories 112 free
- Geometric invariance of existential fixed-point logic 920
- On the decidability of objects in a locos 2334
- The Dialectica categories 4758
- Combinators 6374
- Polynat in per 6778
- Towards a geometry of interaction 6980
- The category of sketches as a model for algebraic semantics 109120
- The theory of constructions: Categorical semantics and topos-theoretic models 137148
- A simple model of the theory of constructions 201212
- Multicategories revisited 217228
- An application of minimal context-free intersection partitions to rewrite rule consistency checking 241252
- Qualitative distinctions between some toposes of generalized graphs 261272
- Typed lambda models and cartesian closed categories 301312
- Some connections between models of computation 317328
- Some applications of categorical model theory 325336
- Coherence for bicategories with finite Bilimits I 341352
- On partial Cartesian closed categories 349360
- Normalization revisited 357368
- Linear logic, *-autonomous categories and cofree coalgebras 371382