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...
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...
Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data (2008)
Michael Elberfeld, Ilka Schnoor, Till Tantau
Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. One fast haplotyping method is based on an evolutionary model where a...
Complexity of default logic on generalized conjunctive queries (2007)
Abstract. Reiter’s default logic formalizes nonmonotonic reasoning using default assumptions. The semantics of a given instance of default logic is based on a fixpoint equation defining an...
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,...
Complexity of default logic on generalized conjunctive queries (2007)
Miki Hermann, Ilka Schnoor, Theoretische Informatik
Abstract. Reiter’s default logic formalizes nonmonotonic reasoning using default assumptions. The semantics of a given instance of default logic is based on a fixpoint equation defining an...
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...
Complexity of default logic on generalized conjunctive queries (2007)
Miki Hermann, Ilka Schnoor, Theoretische Informatik
Abstract. Reiter’s default logic formalizes nonmonotonic reasoning using default assumptions. The semantics of a given instance of default logic is based on a fixpoint equation defining an...
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...