Intuitionistic Podelski-Rybalchenko Theorem and Equivalence Between Inductive Definitions and Cyclic Proofs - Coalgebraic Methods in Computer Science
Conference Papers Year : 2018

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

Makoto Tatsuta
  • Function : Author
  • PersonId : 1043058

Abstract

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
Origin Files produced by the author(s)
Loading...

Dates and versions

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

Licence

Identifiers

Cite

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⟩
69 View
119 Download

Altmetric

Share

More