License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2013.469
URN: urn:nbn:de:0030-drops-42142
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4214/
Go to the corresponding LIPIcs Volume Portal

Leivant, Daniel

Global semantic typing for inductive and coinductive computing

pdf-format:
34.pdf (0.5 MB)

Abstract

Common data-types, such as N, can be identified with term algebras. Thus each type can be construed as a global set; e.g. for N this global set is instantiated in each structure S to the denotations in S of the unary numerals. We can then consider each declarative program as an axiomatic theory, and assigns to it a semantic (Curry-style) type in each structure. This leads to the intrinsic theories of [Leivant, 2002], which provide a purely logical framework for reasoning about programs and their types. The framework is of interest because of its close fit with syntactic, semantic, and proof theoretic fundamentals of formal logic.
This paper extends the framework to data given by coinductive as well as inductive declarations. We prove a Canonicity Theorem, stating that the denotational semantics of an equational program P, understood operationally, has type \tau over the canonical model iff P, understood as a formula has type \tau in every "data-correct" structure. In addition we show that every intrinsic theory is interpretable in a conservative extension of first-order arithmetic.

BibTeX - Entry

@InProceedings{leivant:LIPIcs:2013:4214,
  author =	{Daniel Leivant},
  title =	{{Global semantic typing for inductive and coinductive computing}},
  booktitle =	{Computer Science Logic 2013 (CSL 2013)},
  pages =	{469--483},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-60-6},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{23},
  editor =	{Simona Ronchi Della Rocca},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4214},
  URN =		{urn:nbn:de:0030-drops-42142},
  doi =		{10.4230/LIPIcs.CSL.2013.469},
  annote =	{Keywords: Inductive and coinductive types, equational programs, intrinsic theories, global model theory}
}

Keywords: Inductive and coinductive types, equational programs, intrinsic theories, global model theory
Collection: Computer Science Logic 2013 (CSL 2013)
Issue Date: 2013
Date of publication: 02.09.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI