License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2010.135
URN: urn:nbn:de:0030-drops-26490
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2649/
Go to the corresponding LIPIcs Volume Portal

Guglielmi, Alessio ; Gundersen, Tom ; Parigot, Michel

A Proof Calculus Which Reduces Syntactic Bureaucracy

pdf-format:
10002.GuglielmiAlessio.2649.pdf (0.2 MB)

Abstract

In usual proof systems, like the sequent calculus, only a very limited way of combining proofs is available through the tree structure. We present in this paper a logic-independent proof calculus, where proofs can be freely composed by connectives, and prove its basic properties. The main advantage of this proof calculus is that it allows to avoid certain types of syntactic bureaucracy inherent to all usual proof systems, in particular the sequent calculus. Proofs in this system closely reflect their atomic flow, which traces the behaviour of atoms through structural rules. The general definition is illustrated by the standard deep-inference system for propositional logic, for which there are known rewriting techniques that achieve cut elimination based only on the information in atomic flows.

BibTeX - Entry

@InProceedings{guglielmi_et_al:LIPIcs:2010:2649,
  author =	{Alessio Guglielmi and Tom Gundersen and Michel Parigot},
  title =	{{A Proof Calculus Which Reduces Syntactic Bureaucracy}},
  booktitle =	{Proceedings of the 21st International Conference on Rewriting Techniques and Applications},
  pages =	{135--150},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-18-7},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{6},
  editor =	{Christopher Lynch},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2649},
  URN =		{urn:nbn:de:0030-drops-26490},
  doi =		{10.4230/LIPIcs.RTA.2010.135},
  annote =	{Keywords: Logic, Proof theory, Deep Inference, Flow graphs, Proof Systems, Open Deduction, Rewriting, Confluence, Termination}
}

Keywords: Logic, Proof theory, Deep Inference, Flow graphs, Proof Systems, Open Deduction, Rewriting, Confluence, Termination
Collection: Proceedings of the 21st International Conference on Rewriting Techniques and Applications
Issue Date: 2010
Date of publication: 06.07.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI