Interpolation for the two-way modal μ \mu -calculus
Johannes Kloibhofer, Yde Venema · 2025
Read Interpolation for the two-way modal μ \mu -calculus by Johannes Kloibhofer, Yde Venema (2025) 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-2505-12899.txt.
Introduction
Johannes Kloibhofer and Yde Venema proved an interpolation result in 2025 for a rich logic. Whenever one statement in the logic implies another, a middle statement exists that uses only their shared vocabulary. The logic is the two-way modal mu-calculus, which can look backward as well as forward, a feature that breaks simpler proof methods.
They built two sequent calculi for it, one allowing infinite proof branches and one finitary cyclic version with annotations. Both use trace atoms, a device that imports automaton ideas into proof theory to track the backward steps. Soundness and completeness are shown for each system. Maehara's method, adapted to cyclic proofs, then yields interpolation for both propositions and modalities, and Beth's definability property follows. The catalog creator field appends a funding note; the byline governs. Readers get proof machinery for a logic that reasons both ways in time.
Catalog record
| CREATOR | Johannes Kloibhofer, Yde Venema |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 126 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-12899
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Interpolation for the two-way modal μ \mu -calculus Thanks: The research of the first author has been made possible by a grant from the Dutch Research Council NWO, project nr. 617.001.857. The authors are grateful for comments by the anonymous referees. Johannes Kloibhofer, Yde Venema Abstract The two-way modal μ \mu -calculus is the extension of the (standard) one-way μ \mu -calculus with converse (backward-looking) modalities. For this logic we introduce two new sequent-style proof calculi: a non-wellfounded system admitting infinite branches and a finitary, cyclic version of this that employs annotations. As is common in sequent systems for two-way modal logics, our calculi feature an analytic cut rule. What distinguishes our approach is the use of so-called trace atoms, which serve to apply Vardi’s two-way automata in a proof-theoretic setting. We prove soundness and completeness for both systems and subsequently use the cyclic calculus to show that the two-way μ \mu -calculus has the (local) Craig interpolation property, with respect to both propositions and modalities. Our proof uses a version of Maehara’s method adapted to cyclic proof systems. As a corollary we prove that the two-way μ \mu -calculus also enjoys Beth’s definability property. I Introduction The modal \mu -calculus The (standard, one-way) modal \mu -calculus \mathcal{L}_{\mu} ( [ 1 , 2 ] ) is an extension of propositional (poly-)modal logic with explicit least- and greatest fixpoint operators which allow the expression of various recursive concepts in the language. The version used today, which was introduced by Kozen [ 3 ] , has become a key tool in the formal study of the behaviour of programs and the dynamics of processes in general. Many temporal and dynamic logics such as the computational tree logics CTL and CTL ∗ , and propositional dynamic logic PDL, have natural embeddings in \mathcal{L}_{\mu} . It has been shown that when it comes to bisimulation-invariant properties, \mathcal{L}_{\mu} has the same expressive power as monadic second-order logic [ 4 ] . Despite this increase in expressiveness, the \mu -calculus has remarkably good computational properties, such as an ExpTime -complete satisfiablity problem [ 5 ] . Furthermore, \mathcal{L}_{\mu} displays some excellent meta-logical behaviour. For instance, it enjoys the finite model property (Kozen [ 6 ] ), and a strong, uniform interpolation property as shown by D’Agostino and Hollenberg [ 7 ] . The set of valid \mathcal{L}_{\mu} -formulas has an elegant Hilbert-style axiomatisation, already proposed by Kozen [ 3 ] but only proved to be complete by Walukiewicz [ 8 ] . The proof theory of the modal \mu -calculus is generally considered to be hard, largely due to the subtleties of nested least- and greatest fixpoint operators. Niwiński & Walukiewicz [ 9 ] introduced, in a framework of infinite games, a certain sequent system in which sequents can be derived by means of non-wellfounded proofs allowing infinite branches, as long as these satisfy a certain success (or ‘progress’) condition. 1 1 1 Niwiński & Walukiewicz actually work with tableaux , which are somewhat dual to sequent systems by establishing satisfiability rather than validity of finite sets of formulas. However, tableau calculi and sequent-style proof systems have so much in common, that in this paper we do not differentiate between the two approaches. Using results from automata theory one may show that any such non-wellfounded proof can be replaced by one that is regular - it has only finitely many distinct subderivations. Such a regular proof can be represented as the unfolding of a cyclic proof, that is, a certain finite derivation tree with back edges. As a further step, Jungteerapanitch [ 10 ] and Stirling [ 11 ] annotate formulas to encode the automata-theoretic information, which guarantees that all infinite branches in a proof tree satisfy the mentioned success condition. We shall build on this work. The two-way \mu -calculus Despite its expressive power, enrichments of the standard modal \mu -calculus have been introduced with various features that are well-known in the setting of basic (that is, fixpoint-free) modal logic, such as converse modalities, nominals or counting modalities [ 12 ] . In this paper we shall focus on the two-way \mu -calculus \mathcal{L}_{\mu}^{2} [ 13 ] , perhaps the most natural and simple extension of \mathcal{L}_{\mu} . Concretely, we obtain the language of \mathcal{L}_{\mu}^{2} by adding, for each modality a , a modality \breve{a} which in the semantics will be interpreted as the converse of the accessibility relation for a . This addition enables \mathcal{L}_{\mu}^{2} to reason about the past, which is attractive from the perspective of formal program verification [ 14 ] , but also in the area of description logics, where converse modalities correspond to inverse roles [ 15 ] . Compared to its one-way version, surprisingly little seems to be known about this logic. While it is not hard to see that the two-way \mu -calculus lacks the finite model property, a key result by Vardi [ 13 ] states that the satisfiablity problem for the two-way \mu -calculus can be solved in exponential time. Vardi introduces the notion of an alternating two-way tree automaton, and the key argument in his proof is based on a reduction of these two-way automata to one-way deterministic tree automata. Building on this, French [ 16 , 17 ] proves various results on bisimulation quantifiers for \mathcal{L}_{\mu}^{2} via a transfer of results for \mathcal{L}_{\mu} . Afshari, Jäger & Leigh proposed a sound, complete and cut-free derivation system, which features an infinitely branching proof rule [ 18 ] . A finitary, cyclic proof calculus was given by Afshari et al. [ 19 ] ; this calculus is not cut-free, but its restrictions on the cut rule make the system suitable for proof search procedures. Our goal is to contribute to the knowledge on the two-way \mu -calculus by showing that it has two important properties: Craig interpolation and Beth definability. Our main tool for establishing this, is a new, cyclic proof system for \mathcal{L}_{\mu}^{2} that is of independent interest. Craig interpolation and Beth definability A logic has the Craig Interpolation Property (CIP) if for any pair of formulas \varphi and \psi such that \psi is a consequence of \varphi (denoted as \varphi\vDash\psi ), one may find an interpolant ; that is, a formula \theta in the common vocabulary of \varphi and \psi such that \varphi\vDash\theta and \theta\vDash\psi . The property was named of William Craig who proved it for first-order logic [ 20 ] , since then it has been studied intensively in logic (see for instance van Benthem [ 21 ] ) while it also has many computer science applications in for instance knowledge representation [ 22 ] and model checking [ 23 ] . Beth Definability is a related property; informally it states that the implicit definability of a concept in a logic implies the existence of an explicit definition. This notion has its origin in the work of Beth [ 24 ] who discovered it as a property of classical first-order logic. Beth definability is studied intensively in the area of description logics, where it is used to optimize reasoning [ 25 ] . The main result in our paper is the following. Theorem 1 . The two-way modal \mu -calculus has the