32 citations · 72 across the 9 of their papers we have counts for
8 papers · 1 filter
Conservative Extensions in Guarded and Two-Variable Fragments
Jean Christoph Jung, Carsten Lutz, Mauricio Martel +2
We investigate the decidability and computational complexity of (deductive) conservative extensions in fragments of first-order logic (FO), with a focus on the two-variable fragmen…
Generalized Satisfiability for the Description Logic ALC
Arne Meier, Thomas Schneider
The standard reasoning problem, concept satisfiability, in the basic description logic ALC is PSPACE-complete, and it is EXPTIME-complete in the presence of unrestricted axioms. Se…
Model Checking CTL is Almost Always Inherently Sequential
Olaf Beyersdorff, Arne Meier, Martin Mundhenk +3
The model checking problem for CTL is known to be P-complete (Clarke, Emerson, and Sistla (1986), see Schnoebelen (2002)). We consider fragments of CTL obtained by restricting the…
The Complexity of Satisfiability for Sub-Boolean Fragments of ALC
Arne Meier, Thomas Schneider
The standard reasoning problem, concept satisfiability, in the basic description logic ALC is PSPACE-complete, and it is EXPTIME-complete in the presence of unrestricted axioms. Se…
The Complexity of Satisfiability for Fragments of Hybrid Logic -- Part I
Arne Meier, Martin Mundhenk, Thomas Schneider +3
The satisfiability problem of hybrid logics with the downarrow binder is known to be undecidable. This initiated a research program on decidable and tractable fragments. In this pa…
The Complexity of Generalized Satisfiability for Linear Temporal Logic
Michael Bauland, Thomas Schneider, Henning Schnoor +2
In a seminal paper from 1985, Sistla and Clarke showed that satisfiability for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of tempora…