Classical proof forestry
Classical proof forestry
复制标题
经典林业证明
DOI：
10.1016/j.apal.2010.04.006
复制
发表时间：
2010
影响因子：
0.8
通讯作者：
Heijltjes W
中科院分区：
文献类型：
--
作者：
Heijltjes W
经典证明森林（英语：Classical proof forests）是一种基于Herbrand定理和Coquand风格的回溯游戏的一阶经典逻辑的证明形式。首先由米勒在一个无割设置中描述为一阶和高阶经典证明的经济表示，森林的定义特征是严格关注量词的见证项和不存在不必要的结构或“官僚主义”。本文提出了经典的证明森林作为一个图形的证明形式主义，并探讨了可能的森林组成的削减消除。削减减少步骤采取的形式的本地重写关系，产生于自然的方式从森林的结构。然而，减少，这是显着不同的微积分，是复杂的组合，并不排除可能性的无限减少的痕迹，其中一个例子。削减消除，在一个弱规范化定理的形式，获得使用修改后的版本的重写关系的启发博弈论的解释的森林。它是澄清，修改后的约简关系，事实上，强正规化。
Classical proof forests are a proof formalism for first-order classical logic based on Herbrand’s Theorem and backtracking games in the style of Coquand. First described by Miller in a cut-free setting as an economical representation of first-order and higher-order classical proof, defining features of the forests are a strict focus on witnessing terms for quantifiers and the absence of inessential structure, or ‘bureaucracy’. This paper presents classical proof forests as a graphical proof formalism and investigates the possibility of composing forests by cut-elimination. Cut-reduction steps take the form of a local rewrite relation that arises from the structure of the forests in a natural way. Yet reductions, which are significantly different from those of the sequent calculus, are combinatorially intricate and do not exclude the possibility of infinite reduction traces, of which an example is given. Cut-elimination, in the form of a weak normalisation theorem, is obtained using a modified version of the rewrite relation inspired by the game-theoretic interpretation of the forests. It is conjectured that the modified reduction relation is, in fact, strongly normalising.
登录
查看更多内容
游戏和逻辑中的顺序性与并发性
影响因子：
0.5
作者：
S. Abramsky
通讯作者：
S. Abramsky
DOI：
--
发表时间：
1987
期刊：
Studia Logica: An International Journal for Symbolic Logic
影响因子：
--
作者：
D. Miller
通讯作者：
D. Miller
DOI：
10.1007/3-540-60178-3_85
发表时间：
1994-10
期刊：
--
影响因子：
--
作者：
S. Buss
通讯作者：
S. Buss
DOI：
--
发表时间：
2006
期刊：
Algebraic and Proof-theoretic Aspects of Non-classical Logics
影响因子：
--
作者：
Stefan Hetzl;A. Leitsch
通讯作者：
A. Leitsch
影响因子：
1.1
作者：
G. Bellin;M. Hyland;E. Robinson;Christian Urban
通讯作者：
Christian Urban