Browsing by Subject "Temporal logic"

Sort by: Order: Results:

  • Meier, Arne; Ordyniak, Sebastian; Sridharan, Ramanujan; Schindler, Irena (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2017)
    In the present paper, we introduce the backdoor set approach into the field of temporal logic for the global fragment of linear temporal logic. We study the parameterized complexity of the satisfiability problem parameterized ...
  • Bauland, Michael; Schneider, Thomas; Schnoor, Henning; Schnoor, Ilka; Vollmer, Heribert (Braunschweig : International Federation for Computational Logic, 2009)
    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 ...
  • Meier, Arne; Mundhenk, Martin; Thomas, Michael; Vollmer, Heribert (Amsterdam : Elsevier BV, 2008)
    The satisfiability problems for CTL and CTL⋆ are known to be EXPTIME-complete, resp. 2EXPTIME-complete (Fischer and Ladner (1979), Vardi and Stockmeyer (1985)). For fragments that use less temporal or propositional operators, ...
  • Beyersdorff, Olaf; Meier, Arne; Mundhenk, Martin; Schneider, Thomas; Thomas, Michael; Vollmer, Heribert (Braunschweig : International Federation for Computational Logic, 2011)
    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 use of temporal modalities or the use of ...
  • Lück, Martin; Meier, Arne; Schindler, Irena (Association for Computing Machinery, 2017)
    We apply the concept of formula treewidth and pathwidth to computation tree logic, linear temporal logic, and the full branching time logic. Several representations of formulas as graphlike structures are discussed, and ...
  • Krebs, Andreas; Meier, Arne; Virtema, Jonni; Zimmermann, Martin (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2018)
    We develop team semantics for Linear Temporal Logic (LTL) to express hyperproperties, which have recently been identified as a key concept in the verification of information flow properties. Conceptually, we consider an ...
  • Bauland, Michael; Mundhenk, Martin; Schneider, Thomas; Schnoor, Henning; Schnoor, Ilka; Vollmer, Heribert (Amsterdam : Elsevier, 2009)
    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 ...