🔢 mathematics

Non-Wellfounded and Cyclic Proofs for LTL: A Syntactic Correspondence with Linear Nested Sequents

This paper introduces non-wellfounded and cyclic linear nested sequent calculi for Linear Temporal Logic (LTL) and establishes a syntactic correspondence between them by developing methods for cycle recognition and unraveling to address challenges in expressive multisequent formalisms.

Original authors: Tim S. Lyon, Lukas Zenger

Published 2026-06-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tim S. Lyon, Lukas Zenger

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to prove that a specific rule in a complex game of logic will always hold true, no matter how the game plays out over an infinite amount of time. This is the challenge of Linear Temporal Logic (LTL), a system used to reason about things that change and evolve, like computer programs or traffic lights.

The paper by Lyon and Zenger tackles a specific problem: How do we write a proof for something that goes on forever without writing an infinitely long piece of paper?

Here is the breakdown of their solution using simple analogies.

The Problem: The Infinite Forest

In traditional logic, a proof is like a tree. You start at the top (the conclusion) and branch down to the roots (the basic facts). Usually, this tree stops growing; it has a bottom.

However, for systems that run forever (like a computer program), the proof tree might need to grow infinitely deep. You can't write down an infinite tree on a piece of paper.

Non-wellfounded proofs: These are the "infinite trees." They are valid mathematical objects, but they are impossible to write down completely because they never end.
Cyclic proofs: These are the "finite shortcuts." Instead of drawing the whole infinite tree, you draw a finite tree and draw a loop (a cycle) that says, "When we get to this point, we can jump back to an earlier point and do the same thing again." It's like a video game level that loops back to the start.

The authors ask: Can we reliably turn the "infinite tree" into a "looping shortcut," and can we turn the "looping shortcut" back into the "infinite tree" to prove it's safe?

The Challenge: The Growing Puzzle

The authors note that while this "looping" trick is well-understood for simple logic (Gentzen sequents), it gets very messy when you use a more complex structure called Linear Nested Sequents (LNS).

Think of a standard logic proof as a single line of dominoes falling.
Think of an LNS proof as a train of train cars, where each car contains its own set of dominoes.

In a simple proof, you just look for a domino that looks exactly like one you saw before to make a loop.
In an LNS proof, the "train cars" keep growing. You might never see the exact same train car twice. Instead, you see a pattern of growth. The train gets longer, then a specific car gets bigger, then the whole train shifts. Finding a loop here is like trying to spot a repeating pattern in a fractal that keeps getting more detailed.

The Solution: Two Magic Tricks

The authors developed two "magic tricks" (mathematical procedures) to solve this.

Trick 1: The "Saturation" Detector (Cycle Recognition)

Goal: Turn the infinite tree into a looping shortcut.
The Analogy: Imagine you are walking down a hallway that stretches forever. You want to know if you can draw a map of the hallway that fits on a postcard.
The authors discovered a special state called "Saturation Recurrence."

As you walk down the hallway (the infinite proof), the rooms (the logic steps) eventually stop changing in their type of complexity. They become "saturated."
Even though the hallway keeps growing, the pattern of how it grows repeats.
The authors proved that if a proof is valid, it must eventually hit these "saturated" rooms. Once you find two saturated rooms that look similar (even if one is bigger than the other), you can draw a line between them and say, "This is a loop."
Result: They can systematically find these loops and turn the infinite tree into a finite, looping proof.

Trick 2: The "Sliding Door" (Unraveling)

Goal: Turn the looping shortcut back into the infinite tree (to prove the loop is safe).
The Analogy: Imagine you have a magic door that, when you walk through it, instantly adds a new room to the hallway behind you.

In a cyclic proof, you have a loop where you jump from Room A back to Room B.
The authors created a procedure called "Shifting." When you hit the loop, instead of jumping back, you "slide" the rules forward. You take the logic from the jump and apply it to a new section of the hallway.
By doing this over and over, you "unravel" the loop. You take the finite loop and stretch it out into the infinite hallway it represents.
Result: This proves that the looping shortcut is just a compressed version of a valid infinite tree. If the shortcut works, the infinite tree works.

Why This Matters (According to the Paper)

The authors didn't just invent these tricks; they proved they work for Linear Temporal Logic (LTL).

Completeness: They showed that if a statement is true, you can always find a "looping shortcut" proof for it (using Trick 1).
Soundness: They showed that if you have a "looping shortcut" proof, it is guaranteed to be true because it can be unraveled into a valid infinite tree (using Trick 2).

Summary

The paper is about building a bridge between two ways of thinking about infinite logic:

The Infinite View: A never-ending, growing structure (Non-wellfounded).
The Finite View: A looping structure that repeats (Cyclic).

The authors showed that for complex logic systems (Linear Nested Sequents), you can reliably translate back and forth between these two views. They solved the hard problem of finding loops in growing structures and the hard problem of expanding loops back into infinite structures, ensuring that the "shortcuts" we use to prove things are mathematically safe.

Technical Summary: Non-Wellfounded and Cyclic Proofs for LTL: A Syntactic Correspondence with Linear Nested Sequents

Problem Statement
The paper addresses the relationship between non-wellfounded and cyclic proofs within the context of multisequent formalisms, specifically linear nested sequents (LNS). While the correspondence between these two proof styles is well-understood for traditional Gentzen sequents, it remains under-explored for more expressive structures like hypersequents, labeled sequents, and LNS. The authors identify two central challenges in this setting:

Cycle Recognition: The difficulty of identifying cycles in non-wellfounded proofs. Unlike Gentzen sequents where repetitions are often verbatim, LNS structures tend to grow along infinite branches. Consequently, cycles cannot be detected by simple identity checks but must be identified as recurring growth patterns.
Unraveling: The challenge of transforming cyclic proofs back into non-wellfounded ones. Standard unraveling procedures are inapplicable due to the complex, nested structures of LNS, which prevent direct expansion.

The authors focus on Linear Temporal Logic (LTL) as a case study to develop and test solutions for these problems within the LNS framework.

Methodology
The authors introduce cut-free non-wellfounded and cyclic linear nested sequent calculi for LTL ( $LNS^\infty_{LTL}$ and $LNS^{cyc}_{LTL}$ ). The methodology relies on three core technical components:

Saturation Recurrence Property (SRP): To address cycle recognition, the authors define a specific normal form for non-wellfounded proofs called the Saturation Recurrence Property. A derivation satisfies SRP if every infinite branch contains infinitely many "saturated" sequents. A sequent is saturated if its interior components contain no complex formulae (meaning no rules are applicable bottom-up to them). The authors prove that every valid LTL formula admits a non-wellfounded proof satisfying SRP. This property ensures that repetitive growth patterns can be systematically detected, enabling the extraction of cyclic proofs.
Specialized Unraveling via Shifting: To address unraveling, the authors introduce a "shifting" procedure. Unlike standard methods, this technique shifts rule applications forward along the linear nested sequents. By iteratively applying a "Shifting Lemma," a cyclic proof rooted at a companion node can be transformed into a cyclic proof of the corresponding cyclic leaf, effectively extending the proof tree. Iterating this process ad infinitum reconstructs a non-wellfounded proof from a cyclic one.
Proof Transformations: The paper establishes bi-directional transformations:
- Non-wellfounded to Cyclic: Using the SRP and a cardinality argument (Kőnig's Lemma), infinite branches containing infinitely many saturated sequents with identical end components are pruned and replaced by cycles.
- Cyclic to Non-wellfounded: Using the shifting procedure, cycles are "unraveled" to produce an infinite sequence of cyclic proofs, the limit of which constitutes a non-wellfounded proof.

Key Contributions

New Calculi: The paper provides the first cut-free non-wellfounded and cyclic linear nested sequent calculi for LTL. These systems are formula-driven (containing no structural rules) and feature entirely invertible rules.
Cycle Recognition Mechanism: The authors demonstrate that the Saturation Recurrence Property enables the systematic detection of cycles in non-wellfounded LNS proofs, solving the problem of identifying non-verbatim repetitions in growing structures.
Unraveling Procedure: The paper introduces a specialized unraveling technique based on shifting rule applications, which allows for the reconstruction of non-wellfounded proofs from cyclic ones in the LNS setting.
Syntactic Correspondence: The work establishes a formal syntactic correspondence between non-wellfounded and cyclic proofs in multisequent formalisms.

Results

Soundness and Completeness of $LNS^\infty_{LTL}$ : The non-wellfounded system is proven sound via a progress measure argument (showing that invalid formulas lead to infinite descending sequences of natural numbers) and complete via a proof-search argument that constructs proofs satisfying the SRP.
Soundness and Completeness of $LNS^{cyc}_{LTL}$ : As a corollary of the bi-directional transformations, the cyclic system is proven sound and complete. The transformation from cyclic to non-wellfounded proofs preserves validity, while the transformation from non-wellfounded (satisfying SRP) to cyclic proofs preserves provability.
Structural Properties: The paper confirms that the proposed LNS systems for LTL are cut-free and analytic, with all rules being invertible.

Significance
The paper claims to advance the line of research regarding cyclic proofs in multisequent formalisms, which has previously been limited to hypersequents and labeled sequents with specific constraints. By focusing on linear nested sequents, the authors provide a deeper understanding of how cycle recognition and unraveling operate in expressive, structured proof systems.

The significance lies in providing new proof-theoretic techniques for handling non-wellfoundedness in LNS, a formalism that generalizes hypersequents and is often better suited for proof analysis and applications (such as counter-model extraction) than traditional Gentzen systems. The work serves as a foundational step for extending these techniques to other multisequent formalisms, such as labeled sequents, and potentially resolving open problems regarding syntactic cut-elimination in related LTL systems.