Browsing Fakultät für Elektrotechnik und Informatik by Author "02174040-49e0-414d-9bf3-b20a45dc32fd"

Browsing Fakultät für Elektrotechnik und Informatik by Author "02174040-49e0-414d-9bf3-b20a45dc32fd"

Sort by: Order: Results:

  • Backdoors for linear temporal logic 
    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 ...
  • The Complexity of Satisfiability for Fragments of CTL and CTL⋆ 
    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, ...
  • Model checking and validity in propositional and modal inclusion logics 
    Hella, Lauri; Kuusisto, Antti; Meier, Arne; Virtema, Jonni (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2017)
    Propositional and modal inclusion logic are formalisms that belong to the family of logics based on team semantics. This article investigates the model checking and validity problems of these logics. We identify complexity ...
  • Model checking CTL is almost always inherently sequential 
    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 ...
  • Parameterised complexity of model checking and satisfiability in propositional dependence logic 
    Mahmood, Yasir; Meier, Arne (Dordrecht [u.a.] : Springer Science + Business Media B.V, 2021)
    Dependence Logic was introduced by Jouko Väänänen in 2007. We study a propositional variant of this logic (PDL) and investigate a variety of parameterisations with respect to central decision problems. The model checking ...
  • Parameterised Counting in Logspace 
    Haak, Anselm; Meier, Arne; Prakash, Om; Rao, B. V. Raghavendra (New York, NY : Springer, 2023)
    Logarithmic space-bounded complexity classes such as L and NL play a central role in space-bounded computation. The study of counting versions of these complexity classes have lead to several interesting insights into the ...
  • Parameterized complexity of weighted team definability 
    Kontinen, Juha; Mahmood, Yasir; Meier, Arne; Vollmer, Heribert (Cambridge : Cambridge Univ. Press, 2024)
    In this article, we study the complexity of weighted team definability for logics with team semantics. This problem is a natural analog of one of the most studied problems in parameterized complexity, the notion of weighted ...
  • Parametrised enumeration 
    Meier, Arne (Hannover : Institutionelles Repositorium der Leibniz Universität Hannover, 2020)
    In this thesis, we develop a framework of parametrised enumeration complexity. At first, we provide the reader with preliminary notions such as machine models and complexity classes besides proving them to be well-chosen. ...
  • Team semantics for the specification and verification of hyperproperties 
    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 ...

Search the repository


Browse

My Account

Usage Statistics