# IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

# Logic in Computer Science (LICS 2001)

## Paper: A Symbolic Labelled Transition System for Coinductive Subtyping of F_{\mu\leq} Types (at LICS 2001)

Authors: Alan Jeffrey

### Abstract

F_\leq is a typed lambda-calculus with subtyping and bounded polymorphism. Typechecking for F_\leq is known to be undecidable, because the subtyping relation on types is undecidable. F_{\mu\leq} is an extension of F_\leq with recursive types. In this paper, we show how symbolic labelled transition system techniques from concurrency theory can be used to reason about subtyping for F_{\mu\leq}. We provide a symbolic labelled transition system for F_{\mu\leq} types, together with an an appropriate notion of simulation, which coincides with the existing coinductive definition of subtyping. We then provide a 'simulation up to' technique for proving subtyping, for which there is a simple model checking algorithm. The algorithm is more powerful than the usual one for F_\leq, for example it terminates on Ghelli's canonical example of nontermination.

### BibTeX

  @InProceedings{Jeffrey-ASymbolicLabelledTr,
author = 	 {Alan Jeffrey},
title = 	 {A Symbolic Labelled Transition System for Coinductive Subtyping of F_{\mu\leq} Types},
booktitle =  {Proceedings of the Sixteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2001)},
year =	 {2001},
month =	 {June},
pages =      {323--333},
location =   {Boston, MA, USA},
publisher =	 {IEEE Computer Society Press}
}