Analysis of a guard condition in type theory
Extended abstract
Roberto M. Amadio1, 2
and Solange Coupet-Grimal1, 2
| (1) |
Université de Provence, Marseille |
| (2) |
CMI, 39 rue Joliot-Curie, F-13453 Marseille, France |
Abstract
We present a realizability interpretation of co-inductive types based on partial equivalence relations (per's). We extract
from the per's interpretation sound rules to type recursive definitions. These recursive definitions are needed to introduce
‘infinite’ and ‘total’ objects of co-inductive type such as an infinite stream, a digital transducer, or a non-terminating
process. We show that the proposed type system subsumes those studied by Coquand and Gimenez while still enjoying the basic
syntactic properties of subject reduction and strong normalization with respect to a confluent rewriting system first put
forward by Gimenez.
The first author was partially supported by CTI-CNET 95-1B-182, Action Incitative INRIA, IFCPAR 1502-1, WG Confer, and HCM Express. A preliminary version of this paper (including proofs) can be found in [1].
References secured to subscribers.