The Complexity of Defining and Separating Fixpoint Formulae in Modal Logic

Jean Christoph Jung ORCID:0000-0002-4159-2255, Jędrzej Kołodziejski ORCID:0000-0001-5008-9224 · 2025

Read The Complexity of Defining and Separating Fixpoint Formulae in Modal Logic by Jean Christoph Jung ORCID:0000-0002-4159-2255, Jędrzej Kołodziejski ORCID:0000-0001-5008-9224 (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-2509-24583.txt.

Introduction

Jean Christoph Jung and Jędrzej Kołodziejski weigh the hardness of splitting two modal fixpoint formulas with a plain modal formula, in a 2025 paper. A separator must follow from one formula and clash with the other. The team tests this task across model classes: all models, finite ones, trees, and bounded fan-out. A side case asks when a shared consequence, called an interpolant, exists at all.

Hardness jumps by class. Over word-like models the task sits in one known class. Over wide fan-out it climbs two steps higher, and a classic logic property fails there. Replica results also give methods to build separators when they exist.

Catalog record

CREATORJean Christoph Jung ORCID:0000-0002-4159-2255, Jędrzej Kołodziejski ORCID:0000-0001-5008-9224
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE143 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-24583

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Complexity of Defining and Separating Fixpoint Formulae in Modal Logic Jean Christoph Jung ORCID:0000-0002-4159-2255, Jędrzej Kołodziejski ORCID:0000-0001-5008-9224 Abstract . Modal separability for modal fixpoint formulae is the problem to decide for two given modal fixpoint formulae φ , φ ′ \varphi,\varphi^{\prime} whether there is a modal formula ψ \psi that separates them, in the sense that φ ⊧ ψ \varphi\models\psi and ψ ⊧ ¬ φ ′ \psi\models\neg\varphi^{\prime} . We study modal separability and its special case modal definability over various classes of models, such as arbitrary models, finite models, trees, and models of bounded outdegree. Our main results are that modal separability is PSpace -complete over words, that is, models of outdegree ≤ 1 \leq 1 , ExpTime -complete over unrestricted and over binary models, and 2-ExpTime -complete over models of outdegree bounded by some d ≥ 3 d\geq 3 . Interestingly, this latter case behaves fundamentally different from the other cases also in that modal logic does not enjoy the Craig interpolation property over this class. Motivated by this we study also the induced interpolant existence problem as a special case of modal separability, and show that it is coNExpTime -complete and thus harder than validity in the logic. Besides deciding separability, we also provide algorithms for the effective construction of separators. Finally, we consider in a case study the extension of modal fixpoint formulae by graded modalities and investigate separability by modal formulae and graded modal formulae. 1. Introduction For given logics \mathcal{L},\mathcal{L}^{+} , the \mathcal{L} -separability problem for \mathcal{L}^{+} is to decide given two \mathcal{L}^{+} -formulae \varphi,\varphi^{\prime} whether there is an \mathcal{L} -formula \psi that separates \varphi and \varphi^{\prime} in the sense that \varphi\models\psi and \psi\models\neg\varphi^{\prime} . Obviously, a separator can only exist when \varphi and \varphi^{\prime} are mutually exclusive, and the problem is only meaningful when \mathcal{L} is less expressive than \mathcal{L}^{+} . Intuitively, a separator formulated in a “simpler” logic \mathcal{L} explains a given inconsistency in a “complicated” logic \mathcal{L}^{+} . Note that, for logics \mathcal{L}^{+} closed under negation, \mathcal{L} -separability generalizes the \mathcal{L} -definability problem for \mathcal{L}^{+} : decide whether a given \mathcal{L}^{+} -formula is equivalent to an \mathcal{L} -formula. Indeed, \varphi\in\mathcal{L}^{+} is equivalent to an \mathcal{L} -formula iff \varphi and \neg\varphi are \mathcal{L} -separable. Since separability is more general than definability, solving it requires an even better understanding of the logics under consideration. Both separability and definability are central problems with many applications in computer science. As seminal work let us only mention definability and separability of regular word languages by languages recognized by first-order logic [ PZ16 , Sch65 , CH91 ] . In this paper we study definability and separability of formulae of the modal \mu -calculus \mu\mathsf{ML} [ Pra81 , Koz83 ] by formulae in propositional modal logic \mathsf{ML} . \mu\mathsf{ML} is the extension of \mathsf{ML} with fixpoints that encompasses virtually all specification languages such as \mathsf{PDL} [ FL79 ] and \mathsf{LTL} and \mathsf{CTL} [ BK08 ] . Let us consider an example. {exa} Consider the following properties P_{1},P_{2},P_{3} of vertex-labelled trees: • P_{1} : there is an infinite path starting in the root on which each point satisfies a ; • P_{2} : on every path there are only finitely many points satisfying a ; • P_{3} : on every path at most two points satisfy a . The properties are expressible in \mu\mathsf{ML} but not in \mathsf{ML} , and both P_{1},P_{2} and P_{1},P_{3} are mutually exclusive. The properties P_{1},P_{3} are separated by the \mathsf{ML} -formula \psi=a\wedge\Diamond(a\wedge\Diamond a) which expresses that there is a path starting with three points satisfying a . On the other hand, no \mathsf{ML} -formula separates P_{1},P_{2} . The intuitive reason for this is that any \mathsf{ML} -formula \psi only sees trees up to depth |\psi| , and one can find two trees with properties P_{1},P_{2} which nonetheless look the same up to depth |\psi| . A formal proof of non-existence of an \mathsf{ML} -separator is given in Example 3 in the paper.∎ We explore the definability and separability problems over several classes of models relevant for computer science: all models, words, trees of bounded or unbounded outdegree; as well as restrictions of all these classes to finite models. On top of analyzing the decision problems, we also address the problem of constructing definitions and separators whenever they exist. The starting point for our research is the seminal paper of Otto [ Ott99 ] , where he solves modal definability over models of bounded and unbounded outdegree. In this paper, we continue this line of work, extend it to separability, and establish a fairly complete and interesting picture. Table 1 summarizes our results. We now explain its content further. all models words binary trees d -ary trees, d\geq 3 \mathsf{ML} -def. ExpTime [ Ott99 ] PSpace ExpTime [ Ott99 ] ExpTime [ Ott99 ] \mathsf{ML} -sep. ExpTime PSpace ExpTime 2-ExpTime sep. constr. double exp. single exp. double exp. triple exp. interpolant ex. always always always coNExpTime Table 1. Overview of our results. All complexity results are completeness results. The first line essentially repeats Otto’s results; we only add the observation that \mathsf{ML} -definability over words is PSpace -complete. The second line contains our results for \mathsf{ML} -separability. The case of words is the easiest one, both in terms of computational complexity and required arguments. Next come the cases of binary and of unrestricted trees. These two classes possess some nice structural properties which (although true for different reasons) enable a common algorithmic treatment. Finally, the cases of trees with outdegree bounded by a number d\geq 3 enter the stage. These trees lack the good properties essential for previous constructions, which results in significantly higher computational complexity. The hardness result for d\geq 3 is interesting for two reasons. First, as it is entirely standard to encode trees of higher outdegree into binary ones, one could expect the ternary (and higher) case to have the same complexity as the binary one. And second, even though there are known cases when separation is provably harder than definability (regularity of visibly pushdown languages is decidable [ LS19 , Theorem 19] but regular separability thereof is not [ Kop16 , Theorem 2.4] ), to the best of our knowledge our results are the only such case known in the area of logic. The complexity landscape for deciding separability is also reflected in the maximal sizes of the separators that we construct. Relying on the well-known connection of \mu\mathsf{ML} to automata, we provide effective constructions for the cases of all models, words, and binary trees. It is worth mentioning that equally effective constructions for definability over all models are given in [ LQ15 ] , but they do not work for separability. The ternary case follows from a general argument. Our construction of separators over words is optimal. Under mild assumptions (there are at least two modalities) the constructions over binary and over unrestricted trees are optimal as well, but we leave it open whether these assumptions are needed for the lower bounds. In the case of ternary and higher outdegree trees we only conjecture optimality of the constructed separators. Finally, we observe that \mathsf{ML} lacks the Craig interpolation property over trees of outdegree bounded by d\geq 3 . Recall

Read the complete text