Skip to Main content Skip to Navigation
Conference papers

Normalization by Completeness with Heyting Algebras

Abstract : Usual normalization by evaluation techniques have a strong relationship with completeness with respect to Kripke structures. But Kripke structures is not the only semantics that ts intuitionistic logic: Heyting algebras are a more algebraic alternative. In this paper, we focus on this less investigated area: how completeness with respect to Heyting algebras generate a normalization algorithm for a natural deduction calculus, in the propositional fragment. Our main contributions is that we prove in a direct way completeness of natural deduction with respect to Heyting algebras, that the underlying algorithm natively deals with disjunction, that we formalized those proofs in Coq, and give an extracted algorithm.
Document type :
Conference papers
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal-mines-paristech.archives-ouvertes.fr/hal-01204599
Contributor : Claire Medrala <>
Submitted on : Thursday, September 24, 2015 - 11:30:09 AM
Last modification on : Thursday, September 24, 2020 - 4:36:04 PM
Long-term archiving on: : Tuesday, December 29, 2015 - 9:45:36 AM

File

A-614.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01204599, version 1

Citation

Gaëtan Gilbert, Olivier Hermant. Normalization by Completeness with Heyting Algebras. LPAR 20 : 20th International Conference on Logic for Programming, Artificial Intelligence and Reasoning, Nov 2015, Suva, Fiji. ⟨hal-01204599⟩

Share

Metrics

Record views

496

Files downloads

206