Intuitionistic Podelski-Rybalchenko Theorem and Equivalence Between Inductive Definitions and Cyclic Proofs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

Intuitionistic Podelski-Rybalchenko Theorem and Equivalence Between Inductive Definitions and Cyclic Proofs

Makoto Tatsuta
  • Fonction : Auteur
  • PersonId : 1043058

Résumé

A cyclic proof system gives us another way of representing inductive and coinductive definitions and efficient proof search. Podelski-Rybalchenko termination theorem is important for program termination analysis. This paper first shows that Heyting arithmetic HA proves Kleene-Brouwer theorem for induction and Podelski-Rybalchenko theorem for induction. Then by using this theorem this paper proves the equivalence between the provability of the intuitionistic cyclic proof system and that of the intuitionistic system of Martin-Lof’s inductive definitions when both systems contain HA.
Fichier principal
Vignette du fichier
473364_1_En_3_Chapter.pdf (374.28 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02044649 , version 1 (21-02-2019)

Licence

Paternité

Identifiants

Citer

Stefano Berardi, Makoto Tatsuta. Intuitionistic Podelski-Rybalchenko Theorem and Equivalence Between Inductive Definitions and Cyclic Proofs. 14th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Apr 2018, Thessaloniki, Greece. pp.13-33, ⟨10.1007/978-3-030-00389-0_3⟩. ⟨hal-02044649⟩
48 Consultations
86 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More