Browsing by Subject "Dependence logic"

Sort by: Order: Results:

  • Kontinen, Juha; Müller, Julian-Steffen; Schnoor, Henning; Vollmer, Heribert (Wadern : Schloss Dagstuhl- Leibniz-Zentrum für Informatik GmbH, 2015)
    The famous van Benthem theorem states that modal logic corresponds exactly to the fragment of first-order logic that is invariant under bisimulation. In this article we prove an exact analogue of this theorem in the framework ...
  • Sano, Katsuhiko; Virtema, Jonni (Wadern : Schloss Dagstuhl- Leibniz-Zentrum für Informatik GmbH, 2015)
    We give sound and complete Hilbert-style axiomatizations for propositional dependence logic (PD), modal dependence logic (MDL), and extended modal dependence logic (EMDL) by extending existing axiomatizations for propositional ...
  • Kontinen, Juha; Kuusisto, Antti; Virtema, Jonni (Saarbrücken : Dagstuhl Publishing, 2016)
    We study the complexity of predicate logics based on team semantics. We show that the satisfiability problems of two-variable independence logic and inclusion logic are both NEXPTIMEcomplete. Furthermore, we show that the ...
  • 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 ...
  • Hannula, Miika; Kontinen, Juha; Lück, Martin; Virtema, Jonni (Waterloo, NSW : Open Publishing Association, 2016)
    We study quantified propositional logics from the complexity theoretic point of view. First we introduce alternating dependency quantified boolean formulae (ADQBF) which generalize both quantified and dependency quantified ...
  • 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 ...