Auflistung nach Schlagwort "dependence logic"

Sortiert nach: Sortierung: Ergebnisse:

  • 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 ...
  • 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 ...
  • The power of the filtration technique for modal logics with team semantics 
    Lück, Martin (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2017)
    Modal Team Logic (MTL) extends Väänänen's Modal Dependence Logic (MDL) by Boolean negation. Its satisfiability problem is decidable, but the exact complexity is not yet understood very well. We investigate a model-theoretical ...