Embedding first-order logic in a pure type system with parameters

T.D.L. Laan, M.G.J. Franssen

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

standard way to code first-order predicate logic in a propositions-as-types style uses a type system that is a variant of the pure type system P. Types in this system are not necessarily in ß-normal form. Therefore, checking whether two types are ß-equal is decidable, albeit sometimes costly in terms of time and/or memory. In this paper we present an alternative to Berardi's system, based on pure type systems with parameters. We show that all types in our system are in ß-normal form, which is an advantage for implementations. Moreover, the syntactical structure of the system with parameters is similar to the syntax of first-order predicate logic. This is not the case for the system without parameters.
Original languageEnglish
Pages (from-to)545-557
JournalJournal of Logic and Computation
Volume11
Issue number4
DOIs
Publication statusPublished - 2001

Fingerprint

Dive into the research topics of 'Embedding first-order logic in a pure type system with parameters'. Together they form a unique fingerprint.

Cite this