Skip to main navigation Skip to search Skip to main content

The focused calculus of structures

  • Laboratoire d'Informatique (LIX)

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

24 Citations (Scopus)

Abstract

The focusing theorem identifies a complete class of sequent proofs that have no inessential non-deterministic choices and restrict the essential choices to a particular normal form. Focused proofs are therefore well suited both for the search and for the representation of sequent proofs. The calculus of structures is a proof formalism that allows rules to be applied deep inside a formula. Through this freedom it can be used to give analytic proof systems for a wider variety of logics than the sequent calculus, but standard presentations of this calculus are too permissive, allowing too many proofs. In order to make it more amenable to proof search, we transplant the focusing theorem from the sequent calculus to the calculus of structures. The key technical contribution is an incremental treatment of focusing that avoids trivializing the calculus of structures. We give a direct inductive proof of the completeness of the focused calculus of structures with respect to a more standard unfocused form. We also show that any focused sequent proof can be represented in the focused calculus of structures, and, conversely, any proof in the focused calculus of structures corresponds to a focused sequent proof.

Original languageEnglish
Title of host publicationComputer Science Logic 2011 - 25th International Workshop/20th Annual Conference of the EACSL, CSL 2011
Pages159-173
Number of pages15
DOIs
Publication statusPublished - 1 Dec 2011
Event25th International Workshop on Computer Science Logic, CSL 2011/20th Annual Conference of the European Association for Computer Science Logic, EACSL - Bergen, Norway
Duration: 12 Sept 2011 → 15 Sept 2011

Publication series

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

Conference

Conference25th International Workshop on Computer Science Logic, CSL 2011/20th Annual Conference of the European Association for Computer Science Logic, EACSL
Country/TerritoryNorway
CityBergen
Period12/09/11 → 15/09/11

Keywords

  • Calculus of structures
  • Focusing
  • Linear logic
  • Polarity

Fingerprint

Dive into the research topics of 'The focused calculus of structures'. Together they form a unique fingerprint.

Cite this