The Complexity of Generalized Satisfiability for Linear Temporal Logic (2008)
Bauland, Michael, Schneider, Thomas, Schnoor, Henning, Schnoor, Ilka, Vollmer, Heribert
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 operators used....
The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments (2008)
Bauland, Michael, Mundhenk, Martin, Schneider, Thomas, Schnoor, Henning, Schnoor, Ilka, Vollmer, Heribert
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 temporal...
Generalized Modal Satisfiability (2008)
Hemaspaandra, Edith, Schnoor, Henning, Schnoor, Ilka
It is well known that modal satisfiability is PSPACE-complete (Ladner 1977). However, the complexity may decrease if we restrict the set of propositional operators used. Note that there exist an...
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...
New algebraic tools for constraint satisfaction, 2006. These Proceedings (2008)
Abstract. The Galois connection involving polymorphisms and coclones has received a lot of attention in regard to constraint satisfaction problems. However, it fails if we are interested in a...
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...
On the Complexity of Elementary Modal Logics (2008)
Hemaspaandra, Edith, Schnoor, Henning
Modal logics are widely used in computer science. The complexity of modal satisfiability problems has been investigated since the 1970s, usually proving results on a case-by-case basis. We prove a...
On the Complexity of Elementary Modal Logics (2008)
Hemaspaandra, Edith, Schnoor, Henning
Modal logics are widely used in computer science. The complexity of modal satisfiability problems has been investigated since the 1970s, usually proving results on a case-by-case basis. We prove a...
On the Complexity of Elementary Modal Logics (2008)
Hemaspaandra, Edith, Schnoor, Henning
Modal logics are widely used in computer science. The complexity of modal satisfiability problems has been investigated since the 1970s, usually proving results on a case-by-case basis. We prove 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 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...
31. On the Complexity of Elementary Modal Logics (2008)
Hemaspaandra, Edith, Schnoor, Henning
Modal logics are widely used in computer science. The complexity of modal satisfiability problems has been investigated since the 1970s, usually proving results on a case-by-case basis. We prove a...
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...
Enumerating all solutions for constraint satisfaction problems (2007)
Abstract. Constraint satisfaction problems are generalizations of many combinatorial problems. In recent years, there have been many results on the complexity of this problem, and it has proven to be...
Enumerating all solutions for constraint satisfaction problems (2007)
Abstract. We contribute to the study of efficient enumeration algorithms for all solutions of constraint satisfaction problems. The only algorithm known so far, presented by Creignou and Hébrard...
Enumerating all Solutions for Constraint Satisfaction Problems (2006)
Schnoor, Henning, Schnoor, Ilka
We contribute to the study of efficient enumeration algorithms for all solutions of constraint satisfaction problems. The only algorithm known so far, presented by Creignou and Hébrard and...
New Algebraic Tools for Constraint Satisfaction (2006)
Schnoor, Henning, Schnoor, Ilka
The Galois correspondence involving polymorphisms and co-clones has received a lot of attention in regard to constraint satisfaction problems. However, it fails if we are interested in a reduction...
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 the Boolean formula value problem (2005)
We examine the complexity of the formula value problem for Boolean formulas, which is the following decision problem: Given a Boolean formula without variables, does it evaluate to true? We show that...
Bases for Boolean co-clones (2005)
Elmar Böhler, Steffen Reith, Henning Schnoor, Heribert Vollmer
The complexity of various problems in connection with Boolean constraints, like, for example, quantified Boolean constraint satisfaction, have been studied recently. Depending on what types 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...