Auflistung nach Autor/in "89e3e4bf-17fa-4088-8a71-4a5be55a4404"

Auflistung nach Autor/in "89e3e4bf-17fa-4088-8a71-4a5be55a4404"

Sortiert nach: Sortierung: Ergebnisse:

  • Dependence logic with a majority quantifier 
    Durand, Arnaud; Ebbing, Johannes; Kontinen, Juha; Vollmer, Heribert (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2011)
    We study the extension of dependence logic D by a majority quantifier M over finite structures. We show that the resulting logic is equi-expressive with the extension of second-order logic by second-order majority quantifiers ...
  • 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 ...