An Algebraic Approach to the Complexity of Generalized Conjunctive Queries ⋆ (2008)
Michael Baul, Nadia Creignou, Miki Hermann, Heribert Vollmer
Abstract. Kolaitis and Vardi pointed out that constraint satisfaction and conjunctive query containment are essentially the same problem. We study the Boolean conjunctive queries under a more...
Generalized Modal Satisfiability ⋆ (2008)
Michael Baul, Edith Hemaspa, Henning Schnoor, Ilka Schnoor
Abstract. It is well-known that modal satisfiability is PSPACE-complete [Lad77]. However, the complexity may decrease if we restrict the set of propositional operators used. Note that there exist an...
Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation ⋆ (2008)
Michael Baul, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer
Abstract. We consider constraint satisfaction problems parameterized by the set of allowed constraint predicates. We examine the complexity of quantified constraint satisfaction problems with a...
The Complexity of Generalized Satisfiability for Linear Temporal Logic (2008)
Michael Baul, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer
Abstract. 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 temporal...
The Complexity of Generalized Satisfiability for Linear Temporal Logic (2008)
Michael Baul, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer
Abstract. 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 temporal...
The Complexity of Generalized Satisfiability forLinearTemporalLogic (2008)
Michael Baul, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer
Abstract. 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 temporal...
The Complexity of Generalized Satisfiability for Linear Temporal Logic (2008)
Michael Baul, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer
Abstract. 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 temporal...
The tractability of model-checking for LTL: The good, the bad, and the ugly fragments (2007)
Michael Baul, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer
vollmerATthi.uni-hannover.de Abstract. In a seminal paper from 1985, Sistla and Clarke showed that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete,...
The tractability of model-checking for LTL: The good, the bad, and the ugly fragments (2007)
Michael Baul, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer
Abstract. In a seminal paper from 1985, Sistla and Clarke showed that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of...
The complexity of satisfiability problems: refining Schaefer’s theorem (2005)
Eric Allender, Michael Baul, Neil Immerman, Henning Schnoor, Heribert Vollmer
Abstract. Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NPcomplete, and identified all tractable cases. Schaefer’s...
The complexity of satisfiability problems: refining Schaefer’s theorem (2005)
Eric Allender, Michael Baul, Neil Immerman, Henning Schnoor, Heribert Vollmer
Abstract. Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NPcomplete, and identified all tractable cases. Schaefer’s...
The complexity of satisfiability problems: refining Schaefer’s theorem (2005)
Eric Allender, Michael Baul, Neil Immerman, Henning Schnoor, Heribert Vollmer
Abstract. Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NPcomplete, and identified all tractable cases. Schaefer’s...
The complexity of satisfiability problems: refining Schaefer’s theorem (2005)
Eric Allender, Michael Baul, Neil Immerman, Henning Schnoor, Heribert Vollmer
Abstract. Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NPcomplete, and identified all tractable cases. Schaefer’s...