Skip to main navigation Skip to search Skip to main content

Separating functional computation from relations

  • Laboratoire d'Informatique (LIX)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

6 Citations (Scopus)

Abstract

The logical foundation of arithmetic generally starts with a quantificational logic over relations. Of course, one often wishes to have a formal treatment of functions within this setting. Both Hilbert and Church added choice operators (such as the epsilon operator) to logic in order to coerce relations that happen to encode functions into actual functions. Others have extended the term language with confluent term rewriting in order to encode functional computation as rewriting to a normal form. We take a different approach that does not extend the underlying logic with either choice principles or with an equality theory. Instead, we use the familiar twophase construction of focused proofs and capture functional computation entirely within one of these phases. As a result, our logic remains purely relational even when it is computing functions.

Original languageEnglish
Title of host publicationComputer Science Logic 2017, CSL 2017
EditorsValentin Goranko, Mads Dam
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770453
DOIs
Publication statusPublished - 1 Aug 2017
Event26th Annual EACSL Conference on Computer Science Logic, CSL 2017 - Stockholm, Sweden
Duration: 20 Aug 2017 → 24 Aug 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume82
ISSN (Print)1868-8969

Conference

Conference26th Annual EACSL Conference on Computer Science Logic, CSL 2017
Country/TerritorySweden
CityStockholm
Period20/08/17 → 24/08/17

Keywords

  • Computation and deduction
  • Fixed points
  • Focused proof systems

Fingerprint

Dive into the research topics of 'Separating functional computation from relations'. Together they form a unique fingerprint.

Cite this