An Analytic Propositional Proof System On Graphs - Département d'informatique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2020

An Analytic Propositional Proof System On Graphs

Résumé

In this paper we present a proof system that operates on graphs instead of formulas. Starting from the well-known relationship between formulas and cographs, we drop the cograph-conditions and look at arbitrary (undirected) graphs. This means that we lose the tree structure of the formulas corresponding to the cographs, and we can no longer use standard proof theoretical methods that depend on that tree structure. In order to overcome this difficulty, we use a modular decomposition of graphs and some techniques from deep inference where inference rules do not rely on the main connective of a formula. For our proof system we show the admissibility of cut and a generalization of the splitting property. Finally, we show that our system is a conservative extension of multiplicative linear logic with mix, and we argue that our graphs form a notion of generalized connective.
Fichier principal
Vignette du fichier
2012.01102.pdf (1.05 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03087392 , version 1 (23-12-2020)
hal-03087392 , version 2 (27-10-2022)

Identifiants

  • HAL Id : hal-03087392 , version 1

Citer

Matteo Acclavio, Ross Horne, Lutz Strassburger. An Analytic Propositional Proof System On Graphs. 2020. ⟨hal-03087392v1⟩
88 Consultations
110 Téléchargements

Partager

Gmail Facebook X LinkedIn More