CS Paper Radar

Invariance and Expressiveness: Modal Variations

Martin Otto

cs.LO math.LO ·submitted 2026-11-19 15:24 UTC · v1

Abstract

This contribution focuses on bisimulation invariance as the hallmark of modal model theory and of modal modelling. It exemplifies traditional as well as more recent ramifications \&\ extensions of classical results -- involving variant modes of bisimulation equivalence and matching modalities also beyond plain Kripke structures, and emphasising especially the technical challenges in finite model theory and other non-elementary settings. Main results to be discussed revolve about the theme of expressive completeness phenomena: beside expressive completeness under bisimulation invariance in relation to first-order background logics, in the style of van Benthem--Rosen characterisations, this also concerns maximality results under criteria form abstract model theory, in the style of Lindstroem theorems.

Comment
this is a draft for a chapter in a forthcoming handbook on Comtemporary Modal Logic

Closest papers

Nearest neighbours by meaning across the whole index.

Bisimulations and Modal Logics for Higher Dimensional Automata

cs.LO ·2026-08-14 ·Safa Zouari, Rob van Glabbeek, Krzysztof Ziemiański
published similarity 0.61
Abstract

Higher-Dimensional Automata (HDAs) provide a geometric model of true concurrency. While hereditary history-preserving (hhp) bisimilarity is the finest behavioural equivalence in van Glabbeek's spectrum, no modal logic has previously characterised it on HDAs. We introduce several new intermediate equivalences that sit strictly between ST- and hhp-bisimilarity. We show how separating similarity and subsumption of paths leads to a clean formulation of these equivalences, and we present a modal logic that characterises hhp-bisimilarity. Natural fragments characterise ST-bisimilarity and the intermediate notions.

0.29

Non-Expansive Fuzzy Modal Logic Has Uniform Interpolation

cs.LO ·2026-10-23 ·Stefan Gebhart, Lutz Schröder, Paul Wild
similarity 0.60
Abstract

Fuzzy logics with truth values in the unit interval vary in their choice of propositional connectives and their semantics, ranging from just minimum and maximum as in Zadeh logics to truncated addition and subtraction as in Łukasiewicz logics or their extensions with truth constants, known as Pavelka logics. In the more specific world of fuzzy modal logics, non-expansive fuzzy modal logic has recently been proposed as a sweet spot between Łukasiewicz (more precisely, Pavelka) and Zadeh fuzzy modal logic; it restricts Łukasiewicz propositional connectives to have one argument constant, equivalently extends the Zadeh propositional base with constant shift operators. It retains reasonable expressiveness both in practical terms and abstractly; in particular, it characterizes the standard notion of behavioural distance on fuzzy Kripke frames. At the same time, it allows for satisfiability checking in the same complexity as for its two-valued correspondent (the modal logic K, or the description logic ALC), in contrast to the notorious computational hardness of Łukasiewicz modal logic. In the present work, we show that non-expansive fuzzy modal logic admits uniform interpolation, a key property in modularization, information hiding, summarization, and other applications that fails for both Łukasiewicz (or Pavelka) and Zadeh modal logic.

0.24

Modal Extensions of Generalised Nelson Logics

cs.LO ·2026-10-07 ·Igor Sedlár, Pietro Vigiani
similarity 0.60
Abstract

Motivated by relevant epistemic logic, we extend Dunn's simple Kripke-style binary relational semantics for the semi-relevant logic RM to fit a modal extension of RM. It is shown that the modal axioms and rules that need to be added to RM to obtain a sound and complete axiomatisation of its modal extension give an axiomatisation of modal extensions of all logics in the family of generalised Nelson logics, also studied by Dunn.

0.31

A minimal intuitionistic public announcement logic

cs.LO ·2026-11-10 ·Philippe Balbiani, Hans van Ditmarsch, Cigdem Gencer, Clara Lerouvillois
similarity 0.58
Abstract

We introduce intuitionistic public announcement logics Lmin and Lequ determined by classes of birelational frames where the intuitionistic preorder and the modal accessibility relation do not need to satisfy the confluence conditions traditionally considered within the framework of IPAL. Our logics can be seen as generalisations of IPAL seeing that their language is based on a binary epistemic modality of "relativised knowledge" that allows us to define valid reduction axioms. Our main results are the soundness and completeness of Lmin with respect to the class of all birelational frames and the soundness and completeness of Lequ with respect to the class of all birelational frames where the modal accessibility relation is an equivalence relation.

0.24

Proofs Without Nominals: Gödel's Ontological Argument, its Shallow Embedding, and the Open Questions of the Monatshefte Notes

cs.LO cs.AImath.LO ·2026-09-28 ·Christoph Benzmüller
theory similarity 0.58
Abstract · 51 pages. New in v5: the witness criterion and the whole-term condition come apart (a proof with the nominal in a context alone); three open…

The shallow embedding of higher-order modal logic in classical higher-order logic, used in Benzmüller and Scott's Notes on Gödel's and Scott's variants of the ontological argument, reaches beyond the modal object language: its quantifiers range over domains containing the nominals and satisfaction operators of hybrid logic. A proof using one proves a theorem of the embedding, not necessarily of the modal logic. Whether a result is one of the modal logic can be settled by replaying it in an explicit calculus, or, more cheaply and for all results at once, by analysing what the embedding's proofs substitute. Every statement the Notes prove has a proof in the embedding substituting nothing outside the object language, 294 of them explicit. The Notes' own proofs substitute none either; what it flags are terms a prover introduced. A soundness theorem over general models closed under the object language, and a sentence of that language the embedding proves but which fails in such a model, fix what the certificate says. The Notes' three open questions are settled too, without nominals, but by the empty instance of the conjunction axiom, too cheaply to convince. Generalised to Gödel's "any number of summands", the axiom covers the empty conjunction and the singleton. This article restricts it to at least two different conjuncts, a non-degenerate reading of Gödel's footnote, and settles them again without nominals. In effect only the empty conjunction is excluded; the singleton comes back with the other axioms. In one variant the restriction refutes the possible existence of a God-like being; the answers return, with no side condition, once the Notes' non-emptiness clause is confined to Gödel's essence. Every theorem here is verified in Isabelle/HOL and independently in Lean 4, the separating model in its propositional part; the countermodels are Nitpick's, checked by the build.

0.45

The Density of Interpolants in Modal Logic: First Results

cs.LO ·2026-11-19 ·Roman Kontchakov, Louwe Kuijer, Frank Wolter
similarity 0.58
Abstract

We initiate a quantitative study of interpolation in propositional modal logic. Instead of asking only whether a logic has Craig or uniform interpolation, we measure the density of formulas, or pairs of formulas, admitting interpolants. For quasi-normal modal logics, formulas of bounded modal depth over finite signatures are counted modulo logical equivalence. We show that interpolation failure is local to cells determined by the retained signature, yielding product decompositions of both uniform and Craig interpolation densities. These decompositions allow us to analyse their asymptotic behaviour as either the retained or the forgotten signature grows. When the retained signature grows, we obtain general results for all quasi-normal modal logics; when the forgotten signature grows, the behaviour is subtler, particularly when formulas are counted after existential quantification over forgotten variables. For locally tabular logics, we introduce cell incompatibility graphs and use them for a fine-grained analysis covering tabular logics, the difference logic Diff, and bounded-depth extensions of Grz.

0.33

On Weak Bisimilarities in CCSK

cs.CL ·2026-08-12 ·Baptiste Vallée, Ivan Lanese
similarity 0.57
Abstract · 16 pages, 5 figures, Conference : RC 2026

In the context of CCSK, a reversible extension of CCS, we study different notions of bisimilarity (strong/weak, forward-only/reversible) and highlight their differences and commonalities. In particular, for the weak reversible case, not previously studied in the literature, we propose two variants, dubbed directional and mixed bisimilarity, depending on whether $τ$ actions should be in the same direction (forward/backward) as the action being matched or not. We show, in particular, that mixed bisimilarity is a congruence and completely abstracts away from $τ$ actions.

0.18

Properties of Public Announcements as Operators: Commutativity, Monotonicity, Idempotence, Fixed Points, and Stabilization

cs.LO math.LO ·2026-11-09 ·Eiji Yamada
similarity 0.57
Abstract · 31 pages, 2 figures, 2 tables

For each formula $\varphi$, we introduce the public announcement operator $U_\varphi$, which maps every model to its updated model under the public announcement of $\varphi$. We then study its algebraic and dynamic properties with a particular focus on commutativity, monotonicity, idempotence, fixed points, and stabilization. Among many results, we show the following. First, monotonicity of $U_\varphi$ is characterized by a family of preservation conditions and equivalence to an existential formula. Second, there exists a formula that achieves every nonzero ordinal as a stabilization rank---the first stage at which a model stabilizes---of some model. Finally and unexpectedly, extinction of every model under iterated announcements of $\varphi$ is equivalent to common unknowability, being always informative when true, and a fixed point view of the Moore sentence. Over S5, those are further equivalent to common unbelievability and being always informative. Other results include characterizations of commutativity and strong commutativity, idempotence as success, properties of fixed points, and finite and $ω$-stabilization. For analysis, we use PAL (state elimination) and BPAL (arrow elimination), clarifying their subtle differences.

0.35