3 papers
cs.LO2025
When Symmetry Yields NP-Hardness: Affine ML-SAT on S5 Frames
Andreas Krebs, Arne Meier
Hemaspaandra~et~al.~[JCSS 2010] conjectured that satisfiability for multi-modal logic restricted to the connectives XOR and 1, over frame classes T, S4, and S5, is solvable in poly…
cs.LO2024
Synchronous Team Semantics for Temporal Logics
Andreas Krebs, Arne Meier, Jonni Virtema +1
We present team semantics for two of the most important linear and branching time specification languages, Linear Temporal Logic (LTL) and Computation Tree Logic (CTL). With team s…
cs.LO2014
Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth
Andreas Krebs, Oleg Verbitsky
Given a connected graph and its vertex , let denote the universal cover of obtained by unfolding into a tree starting from . Let be the minimum…