Browse by License

Sort by: Order: Results:

  • Ebbing, Johannes; Kontinen, Juha; Mueller, Julian-Steffen; Vollmer, Heribert (Braunschweig : Tech. Univ. Braunschweig, 2014)
    In this paper we study the expressive power of Horn-formulae in dependence logic and show that they can express NP-complete problems. Therefore we define an even smaller fragment D*-Horn and show that over finite successor ...
  • Boehler, Elmar; Creignou, Nadia; Galota, Matthias; Reith, Steffen; Schnoor, Henning; Vollmer, Heribert (Braunschweig : Tech. Univ. Braunschweig, 2012)
    We study Boolean circuits as a representation of Boolean functions and conskier different equivalence, audit, and enumeration problems. For a number of restricted sets of gate types (bases) we obtain efficient algorithms, ...
  • 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 ...
  • Kontinen, Juha; Vollmer, Heribert (Braunschweig : Tech. Univ. Braunschweig, 2010)
    We study logics defined in terms of second-order monadic monoidal and groupoidal quantifiers. These are generalized quantifiers defined by monoid and groupoid word-problems, equivalently, by regular and context-free ...
  • 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 ...