An Analytic Propositional Proof System on Graphs
An Analytic Propositional Proof System on Graphs
复制标题
图上的解析命题证明系统
DOI：
10.46298/lmcs-18(4:1)2022
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Lutz Straßburger
中科院分区：
文献类型：
--
作者：
Matteo Acclavio;Ross Horne;Lutz Straßburger
在本文中，我们提出了一个在图上运行的证明系统，而不是
公式。从众所周知的公式和之间的关系出发
cographs，我们放弃 cograph 条件并查看任意无向）
图表。这意味着我们失去了公式的树结构
对应于cographs，我们不能再使用标准证明
依赖于该树结构的理论方法。为了克服
这个困难，我们使用图的模块化分解和一些技术
来自深度推理，其中推理规则不依赖于主要连接词
一个公式。对于我们的证明系统，我们展示了切割的可接受性和
分裂性质的推广。最后，我们证明我们的系统是一个
乘法线性逻辑与混合的保守扩展，我们认为
我们的图表形成了广义连接词的概念。
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
generalisation 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 generalised connective.
超越公式作为图形：布尔逻辑到任意图形的扩展
DOI：
--
发表时间：
2020
期刊：
--
影响因子：
--
作者：
Calk C
通讯作者：
Calk C
差分线性逻辑的深度推理系统
影响因子：
--
作者：
Acclavio M
通讯作者：
Acclavio M
独立于开关和中间的布尔逻辑中新的最小线性推理
DOI：
--
发表时间：
2021
期刊：
--
影响因子：
--
作者：
Anupam Das
通讯作者：
Anupam Das