💻 computer science

The Complexity of Defining and Separating Fixpoint Formulae in Modal Logic

This paper investigates the computational complexity and decidability of modal separability and definability for modal fixpoint formulae across various model classes, establishing PSpace, ExpTime, and TwoExpTime completeness results while highlighting the unique behavior of bounded outdegree models where Craig interpolation fails and providing algorithms for constructing effective separators.

Original authors: Jean Christoph Jung, Jędrzej Kołodziejski

Published 2026-01-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jean Christoph Jung, Jędrzej Kołodziejski

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 a detective trying to solve a mystery involving two suspects, Formula A and Formula B. These suspects are described using a very complex, high-tech language called the Modal $\mu$ -calculus (let's call it "Super-Lingo"). Super-Lingo is powerful because it can describe infinite loops and complex patterns, like "there is a path that goes on forever where every step is red."

Your job is to find a Separator. A separator is a simpler sentence written in plain Modal Logic (let's call it "Basic-Lingo"). This sentence must do two things:

It must be true for Formula A.
It must be false for Formula B.

If you can find such a sentence, you have proven that the complex features of Super-Lingo aren't actually needed to tell A and B apart. If you can't find one, it means the only way to distinguish them is to use the full power of the complex language.

This paper is a massive investigation into how hard it is to find these separators, depending on the "world" (or model) where the suspects live.

The Different Worlds (Models)

The authors tested this detective work in four different types of worlds, which act like different terrains for the suspects to hide in:

The Word World (Outdegree 1): Imagine a single, straight line of dominoes. There is only one path forward.
- The Result: This is the easiest case. Finding a separator is like solving a puzzle that takes a moderate amount of time (specifically, "PSpace-complete"). It's manageable.
- The Separator Size: The sentences needed are reasonably short (exponential size).
The Binary Tree World (Outdegree 2): Imagine a family tree where every person has exactly two children. It branches out, but in a very predictable, symmetrical way.
- The Result: This gets harder. Finding a separator now takes a significant amount of computing power (ExpTime-complete).
- The Separator Size: The sentences needed to separate the suspects become very long (doubly exponential). It's like needing a book to explain something that could be said in a paragraph in the Word World.
The "Three-or-More" Tree World (Outdegree $\ge$ 3): Imagine a tree where every person has three or more children. The branches spread out wildly.
- The Result: This is the hardest case. The complexity jumps to a massive level (2-ExpTime-complete).
- The Big Surprise: In this world, the rules of logic break down in a specific way. Usually, if two things are different, there is a "middle ground" sentence that explains why. But here, that middle ground doesn't always exist. The authors proved that for trees with 3+ branches, you cannot always find a "Craig Interpolant" (a special kind of separator that only uses words common to both suspects). This is a fundamental break in the logic that doesn't happen in the simpler worlds.
- The Separator Size: The sentences needed are astronomically long (triply exponential).

The "Graded" Twist

The authors also looked at a version of the game where the language includes "counting" words, like "there are at least 5 children who are red."

If the separator is allowed to use these counting words, the difficulty stays the same as the standard case.
If the separator is forbidden from using counting words (it must stick to Basic-Lingo), the difficulty jumps up again for the "Three-or-More" trees, matching the hardest complexity level found earlier.

Why Does This Matter? (According to the Paper)

The paper doesn't just say "this is hard." It explains why the difficulty changes:

In the Word and Binary worlds: The structure is so orderly that you can always "squash" the complex infinite patterns into a finite, simple description.
In the 3+ Tree world: The branching is so wild that the complex language can create patterns that look identical from a distance but are fundamentally different up close. A simple sentence can't "see" deep enough to tell them apart without getting lost in an infinitely long description.

Summary of the Detective's Findings

The World	How Hard is it to find a separator?	How long is the separator?	Special Note
Straight Line (1 branch)	Moderate (PSpace)	Short (Exponential)	The easiest case.
Binary Tree (2 branches)	Hard (ExpTime)	Very Long (Doubly Exponential)	Logic works perfectly here.
Wild Tree (3+ branches)	Super Hard (2-ExpTime)	Astronomically Long (Triply Exponential)	Logic breaks: Sometimes no simple explanation exists.

The Bottom Line:
The paper shows that as soon as you allow a system to branch out in three or more directions, the complexity of distinguishing complex behaviors explodes. The "simple" logic we use to explain things stops working, and the explanations we do find become impossibly long. It's a mathematical proof that some systems are just too complex to be explained simply, especially when they branch out in many directions.

Technical Summary: The Complexity of Defining and Separating Fixpoint Formulae in Modal Logic

1. Problem Statement

The paper investigates the modal separability problem for the modal $\mu$ -calculus ( $\mu$ ML) with respect to propositional modal logic (ML). Given two inconsistent $\mu$ ML-formulae $\phi$ and $\phi'$ , the problem asks whether there exists an ML-formula $\psi$ (a "separator") such that $\phi \models \psi$ and $\psi \models \neg \phi'$ .

This problem generalizes modal definability: determining if a specific $\mu$ ML-formula is equivalent to an ML-formula. Definability is the special case where $\phi' = \neg \phi$ . The study is conducted over various classes of models relevant to computer science:

Arbitrary models (unrestricted outdegree).
Words (models of outdegree $\le 1$ , denoted $T_1$ ).
Binary trees (outdegree $\le 2$ , denoted $T_2$ ).
Trees of bounded outdegree $d \ge 3$ (denoted $T_d$ ).
Finite models and infinite words.

The authors also investigate the Craig interpolant existence problem (a special case of separability where the separator must only use symbols common to $\phi$ and $\phi'$ ) and the effective construction of separators.

2. Methodology

The authors employ a combination of model-theoretic characterizations and automata-theoretic techniques:

Model-Theoretic Characterizations: The core of the decision procedure relies on joint consistency. Two formulae are not separable if and only if they are "jointly consistent" with respect to specific bisimulation relations. Specifically, $\phi$ and $\phi'$ are not ML-separable over a class $\mathcal{C}$ if they are jointly consistent with respect to $(\sigma, n)$ -bisimulations for all $n$ .
- For words ( $T_1$ ) and binary trees ( $T_2$ ), the authors leverage the fact that bisimilarity implies isomorphism (or can be reduced to it) to equate joint bisimulation consistency with joint isomorphism consistency.
- For $d \ge 3$ , this equivalence fails, necessitating a more complex analysis involving bisimulation quotients.
Automata Theory: The paper utilizes the well-known correspondence between $\mu$ ML and Nondeterministic Parity Tree Automata (NPTA).
- $\mu$ ML formulae are translated into NPTAs.
- The problem of checking joint consistency is reduced to checking the intersection of languages accepted by these automata.
- A key technical tool is the construction of automata that recognize bisimulation quotients of the languages accepted by the original automata. This allows the authors to decide separability over bounded outdegree trees by reducing it to isomorphism checking of these quotients.
Construction of Separators: When separability is established, the authors provide algorithms to construct the separating formula. These constructions often involve generating ML-uniform consequences of the input formulae, which are disjunctions of types consistent with the input.

3. Key Contributions and Results

3.1. Complexity of Separability and Definability

The paper establishes a precise complexity landscape for ML-separability and ML-definability of $\mu$ ML-formulae, summarized in Table 1 of the paper:

Model Class	ML-Definability	ML-Separability	Separator Construction Size
Words ( $T_1$ )	PSpace-complete	PSpace-complete	Single exponential
Binary Trees ( $T_2$ )	ExpTime-complete	ExpTime-complete	Double exponential
Unrestricted Models	ExpTime-complete	ExpTime-complete	Double exponential
Trees ( $T_d, d \ge 3$ )	ExpTime-complete	2-ExpTime-complete	Triple exponential

Words ( $T_1$ ): Separability is PSpace-complete. This is the easiest case, matching the complexity of $\mu$ ML satisfiability over words.
Binary Trees ( $T_2$ ) and Unrestricted: Separability is ExpTime-complete. The authors show that the structural properties of binary trees (where bisimilarity implies isomorphism) allow for a common algorithmic treatment with unrestricted models.
Trees with $d \ge 3$ : This is the most significant finding. While ML-definability remains ExpTime-complete, ML-separability jumps to 2-ExpTime-complete.
- The authors demonstrate that this increase in complexity is not merely due to encoding higher outdegrees into binary trees (which would preserve complexity).
- The hardness arises because ML lacks the Craig Interpolation Property (CIP) over $T_d$ for $d \ge 3$ .

3.2. Craig Interpolation and Interpolant Existence

Failure of CIP: The paper proves that ML enjoys the Craig Interpolation Property over all models, words, and binary trees, but fails over trees of outdegree $d \ge 3$ .
Interpolant Existence: Motivated by the failure of CIP, the authors study the Craig interpolant existence problem (does a separator exist using only common symbols?) for ML over $T_d$ ( $d \ge 3$ ). They show this problem is coNExpTime-complete, which is strictly harder than the validity problem for ML (which is PSpace-complete over these classes).

3.3. Effective Construction

The paper provides algorithms for constructing separators when they exist:

Words: Construction is possible in exponential time (optimal, as $\mu$ ML is exponentially more succinct than ML over words).
Binary/Unrestricted: Construction is possible in double exponential time.
$d \ge 3$ : Construction is possible in triple exponential time.
The authors note that for $d \ge 3$ , the constructed separators are conjectured to be optimal in size, though a formal lower bound for construction size remains open.

3.4. Graded Modalities (Case Study)

The authors extend their results to Graded Modal Logic (grML) and the Graded $\mu$ -calculus (gr $\mu$ ML), which include modalities counting the number of successors (e.g., "at least $k$ children satisfy...").

With Grades in Separator: Both definability and separability remain ExpTime-complete.
Without Grades in Separator:
- Definability: ML-definability of gr $\mu$ ML-formulae is ExpTime-complete.
- Separability: ML-separability of gr $\mu$ ML-formulae is 2-ExpTime-complete.
- The authors attribute the higher complexity of separability (compared to definability) to the fact that trees of bounded arity are definable in gr $\mu$ ML, allowing the reduction of the general $d \ge 3$ case to the graded setting.

4. Significance and Claims

The paper claims to provide a "fairly complete and interesting picture" of the complexity of definability and separability for fixpoint logics. Its primary significance lies in:

Identifying a Complexity Gap: It is the first known case in the area of logic where separability is provably harder than definability (specifically, 2-ExpTime vs. ExpTime) for a natural logic over a standard class of models. This contrasts with previous results where separability was either equal to or easier than definability.
Connecting Interpolation and Complexity: The work establishes a direct link between the failure of the Craig Interpolation Property and the increased computational complexity of the separability problem. The lack of CIP over $d \ge 3$ trees is shown to be the root cause of the 2-ExpTime hardness.
Refining the Landscape of Modal Logic: The results clarify that the complexity of modal reasoning is not uniform across tree structures; the transition from binary to ternary trees fundamentally alters the logical properties (specifically interpolation) and the computational cost of reasoning tasks like separability.
Constructive Results: Beyond decision procedures, the paper offers effective constructions for separators, providing bounds on the size of these separators (e.g., double exponential for binary trees, triple exponential for $d \ge 3$ ).

The authors conclude that their findings highlight the subtle interplay between the structural properties of models (outdegree), the logical properties of the language (interpolation), and the computational complexity of reasoning problems. They leave open questions regarding the optimality of separator sizes for $d \ge 3$ and the extension of these results to other fragments or operators.