REPORTS > AUTHORS > ILKA SCHNOOR:
All reports by Author Ilka Schnoor:
TR08-028
| 5th December 2007
Michael Bauland, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer
Michael Bauland, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer
The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments
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 operators used. If, in contrast, the set of propositional operators is restricted, the complexity may decrease. This paper systematically studies ...
more >>>
TR06-153
| 19th October 2006
Michael Bauland, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer
Michael Bauland, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer
The Complexity of Generalized Satisfiability for Linear Temporal Logic
Revisions: 1
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 If, in contrast, the set of propositional operators is restricted, the complexity may decrease. This paper undertakes a systematic study ...
more >>>