Aarhus University Seal / Aarhus Universitets segl

Guarded Cubical Type Theory: Path Equality for Guarded Recursion

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Documents

This paper improves the treatment of equality in guarded dependent type theory (GDTT), by combining it with cubical type theory (CTT). GDTT is an extensional type theory with guarded recursive types, which are useful for building models of program logics, and for programming and reasoning with coinductive types. We wish to implement GDTT with decidable type-checking, while still supporting non-trivial equality proofs that reason about the extensions of guarded recursive constructions. CTT is a variation of Martin-L\"of type theory in which the identity type is replaced by abstract paths between terms. CTT provides a computational interpretation of functional extensionality, is conjectured to have decidable type checking, and has an implemented type-checker. Our new type theory, called guarded cubical type theory, provides a computational interpretation of extensionality for guarded recursive types. This further expands the foundations of CTT as a basis for formalisation in mathematics and computer science. We present examples to demonstrate the expressivity of our type theory, all of which have been checked using a prototype type-checker implementation, and present semantics in a presheaf category.
Original languageEnglish
Title of host publicationCSL 2016 : 25th EACSL Annual Conference on Computer Science Logic
EditorsJean-Marc Talbot, Laurent Regnier
Number of pages17
Publication year2016
Pages1 - 17
ISBN (Electronic)978-3-95977-022-4
Publication statusPublished - 2016
Event25th EACSL Annual Conference on Computer Science Logic - Marseille, France
Duration: 29 Aug 20161 Sep 2016
http://csl16.lif.univ-mrs.fr/

Conference

Conference25th EACSL Annual Conference on Computer Science Logic
LandFrance
ByMarseille
Periode29/08/201601/09/2016
Internetadresse
SeriesLeibniz International Proceedings in Informatics
Volume62
ISSN1868-8969

Bibliographical note

17 pages, to be published in proceedings of CSL 2016

    Research areas

  • cs.LO, cs.PL, F.3.3; F.3.2

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 108605383