21 citations · 116 across the 38 of their papers we have counts for
3 papers · 1 filter
Linear-time Temporal Logic with Team Semantics: Expressivity and Complexity
Jonni Virtema, Jana Hofmann, Bernd Finkbeiner +2
We study the expressivity and complexity of model checking linear temporal logic with team semantics (TeamLTL). TeamLTL, despite being a purely modal logic, is capable of defining…
On the Complexity of Horn and Krom Fragments of Second-Order Boolean Logic
Miika Hannula, Juha Kontinen, Martin Lück +1
Second-order Boolean logic is a generalization of QBF, whose constant alternation fragments are known to be complete for the levels of the exponential time hierarchy. We consider t…
Descriptive complexity of real computation and probabilistic independence logic
Miika Hannula, Juha Kontinen, Jan Van den Bussche +1
We introduce a novel variant of BSS machines called Separate Branching BSS machines (S-BSS in short) and develop a Fagin-type logical characterisation for languages decidable in no…