Non-Wellfounded and Cyclic Proofs for LTL: A Syntactic Correspondence with Linear Nested Sequents
Tim S. Lyon, Lukas Zenger · 2026
Read Non-Wellfounded and Cyclic Proofs for LTL: A Syntactic Correspondence with Linear Nested Sequents by Tim S. Lyon, Lukas Zenger (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-2606-03413.txt.
Description
Lyon and Zenger develop new proof systems for linear temporal logic, known as LTL. Their systems use non-wellfounded and cyclic proofs in linear nested sequents. Two problems drive the work. Cycle recognition asks how to spot cycles in endless proofs and extract finite cyclic ones. Unraveling asks the reverse: how to rebuild an endless proof from a cyclic one.
Both moves are well understood for plain Gentzen sequents. They are much harder in the richer nested setting, and had drawn little study. For cycle recognition, the authors prove completeness against a normal form with saturation recurrence. That form lets cyclic proofs be extracted in a systematic way. For unraveling, a procedure shifts rule steps forward along the sequents. That shift lets endless proofs be rebuilt from cyclic ones. Logicians get fresh proof tools for expressive multisequent systems. The methods may extend to other temporal and modal logics.
Catalog record
| CREATOR | Tim S. Lyon, Lukas Zenger |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.03413