Passer à la navigation principale Passer à la recherche Passer au contenu principal

The focused calculus of structures

  • Laboratoire d'Informatique (LIX)

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

24 Citations (Scopus)

Résumé

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.

langue originaleAnglais
titreComputer Science Logic 2011 - 25th International Workshop/20th Annual Conference of the EACSL, CSL 2011
Pages159-173
Nombre de pages15
Les DOIs
étatPublié - 1 déc. 2011
Evénement25th International Workshop on Computer Science Logic, CSL 2011/20th Annual Conference of the European Association for Computer Science Logic, EACSL - Bergen, Norvcge
Durée: 12 sept. 2011 → 15 sept. 2011

Série de publications

NomLeibniz International Proceedings in Informatics, LIPIcs
Volume12
ISSN (imprimé)1868-8969

Une conférence

Une conférence25th International Workshop on Computer Science Logic, CSL 2011/20th Annual Conference of the European Association for Computer Science Logic, EACSL
Pays/TerritoireNorvcge
La villeBergen
période12/09/11 → 15/09/11

Empreinte digitale

Examiner les sujets de recherche de « The focused calculus of structures ». Ensemble, ils forment une empreinte digitale unique.

Contient cette citation