3 papers
cs.LO2026
Finite Convergence of the Modal Mu-Calculus on Almost-Periodic Words
Fabian Lehr, Florian Bruse
A formula of the modal mu-calculus enjoys finite convergence on a structure if there is some finite unfolding of the formula that defines the same set. A structure enjoys finite co…
cs.LO2026
A Bisimulation-Invariance-Based Approach to the Separation of Polynomial Complexity Classes
Florian Bruse, Martin Lange
We investigate the possibility to separate the bisimulation-invariant fragment of P from that of NP, resp. PSPACE. We build on Otto's Theorem stating that the bisimulation-invarian…
cs.LO2025
Characterizing the Exponential-Space Hierarchy Via Partial Fixpoints
Florian Bruse, David Kronenberger, Martin Lange
The characterization of PSPACE-queries over ordered structures as exactly those expressible in first-order logic with partial fixpoints (Vardi'82) is one of the classical results i…