Infinitary proof theory : the multiplicative additive case
Infinitary proof theory : the multiplicative additive case
复制标题
无限证明理论：乘法加法情况
DOI：
10.1109/lics.2007.16
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
A. Saurin
中科院分区：
文献类型：
--
作者：
David Baelde;Amina Doumane;A. Saurin
7无限制和常规证明通常在固定点逻辑中使用。尤其是开发的。在证明理论和编程语言理论的交集中解锁了12个富裕的发展，将其扩展到无限期的骨子，例如，对14个递归和编程语言中的14次理解。 15证明系统的两个基本特性：削减局限性和焦点。对于圣地亚哥和堡垒的17件作品，第二本书从未在本文中研究。这两个关键结果
7 Infinitary and regular proofs are commonly used in fixed point logics. Being natural intermediate 8 devices between semantics and traditional finitary proof systems, they are commonly found in 9 completeness arguments, automated deduction, verification, etc. However, their proof theory 10 is surprisingly underdeveloped. In particular, very little is known about the computational 11 behavior of such proofs through cut elimination. Taking such aspects into account has unlocked 12 rich developments at the intersection of proof theory and programming language theory. One 13 would hope that extending this to infinitary calculi would lead, e.g., to a better understanding of 14 recursion and corecursion in programming languages. Structural proof theory is notably based 15 on two fundamental properties of a proof system: cut elimination and focalization. The first 16 one is only known to hold for restricted (purely additive) infinitary calculi, thanks to the work 17 of Santocanale and Fortier; the second one has never been studied in infinitary systems. In 18 this paper, we consider the infinitary proof system μMALL∞ for multiplicative and additive 19 linear logic extended with least and greatest fixed points, and prove these two key results. We 20 thus establish μMALL∞ as a satisfying computational proof system in itself, rather than just an 21 intermediate device in the study of finitary proof systems. 22