Wider systems for linear logic with fixed points: proof theory and complexity

Anupam Das, Tikhon Pshenitsyn · 2026

Read Wider systems for linear logic with fixed points: proof theory and complexity by Anupam Das, Tikhon Pshenitsyn (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-10280.txt.

Description

Linear logic with fixed points poses deep questions for infinitary proof theory, where branching rules run over transfinite ordinals. A 2026 paper by Anupam Das and Tikhon Pshenitsyn investigates infinitary well-founded systems for fixed-point linear logic, with branching rules over transfinite ordinals indexed by a closure ordinal for fixed points. The main result places provability in that system for some computable ordinal at a high level of the hyperarithmetical hierarchy, complete for that level.

Proof-theoretic foundations come first: cut elimination and focusing results control both upper and lower bound analysis. Arguments use a finely tuned notion of formula rank, working out a tight cap on cut-free proof search height. The work advances both proof theory and complexity for fixed-point linear logic.

Catalog record

CREATORAnupam Das, Tikhon Pshenitsyn
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE145 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-10280

Browse the full library · About the Tower of Babel