Temporal Refinements for Guarded Recursive Types - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Preprints, Working Papers, ... Year : 2021

Temporal Refinements for Guarded Recursive Types

Colin Riba
  • Function : Author
  • PersonId : 938059

Abstract

We propose a logic to reason on temporal properties of higher-order programs that handle infinite objects like streams or infinite trees, represented via coinductive types. Specifications of programs are defined using safety and liveness properties. A given program can then be proven to satisfy its specification, in a compositional way, our logic being based on a type system. The logic is presented as a refinement type system over the guarded lambda-calculus, a λ-calculus with guarded recursive types. The refinements are formulae of a modal μ-calculus which embeds usual temporal modal logics such as LTL and CTL. The semantics of our system is given within a rich structure, the topos of trees, in which we build a realizability model of the temporal refinement type system. We use in a crucial way the connection with set-theoretic semantics to handle liveness properties.
Fichier principal
Vignette du fichier
reftrees.pdf (943.5 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-02512655 , version 1 (19-03-2020)
hal-02512655 , version 2 (16-07-2020)
hal-02512655 , version 3 (07-01-2021)
hal-02512655 , version 4 (21-01-2021)
hal-02512655 , version 5 (14-03-2021)

Identifiers

  • HAL Id : hal-02512655 , version 4

Cite

Guilhem Jaber, Colin Riba. Temporal Refinements for Guarded Recursive Types. 2021. ⟨hal-02512655v4⟩
393 View
272 Download

Share

Gmail Facebook X LinkedIn More