Browsing by Subject "descriptive complexity"

Browsing by Subject "descriptive complexity"

Sort by: Order: Results:

  • Descriptive complexity of circuit-based counting classes 
    Haak, Anselm (Hannover : Institutionelles Repositorium der Leibniz Universität Hannover, 2021)
    In this thesis, we study the descriptive complexity of counting classes based on Boolean circuits. In descriptive complexity, the complexity of problems is studied in terms of logics required to describe them. The focus ...
  • A fragment of dependence logic capturing polynomial time 
    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 ...
  • On second-order monadic monoidal and groupoidal quantifiers 
    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 ...