Browsing by Subject "Formal 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 ...
  • Lück, Martin (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2016)
    A framework is developed that extends Hilbert-style proof systems for propositional and modal logics to comprehend their team-based counterparts. The method is applied to classical propositional logic and the modal logic ...
  • 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 ...
  • Meier, Arne; Ordyniak, Sebastian; Sridharan, Ramanujan; Schindler, Irena (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2017)
    In the present paper, we introduce the backdoor set approach into the field of temporal logic for the global fragment of linear temporal logic. We study the parameterized complexity of the satisfiability problem parameterized ...
  • 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 ...
  • Chandoo, Maurice (Saarbrücken : Dagstuhl Publishing, 2016)
    The implicit graph conjecture states that every sufficiently small, hereditary graph class has a labeling scheme with a polynomial-time computable label decoder. We approach this conjecture by investigating classes of label ...
  • Lück, Martin; Meier, Arne; Schindler, Irena (Association for Computing Machinery, 2017)
    We apply the concept of formula treewidth and pathwidth to computation tree logic, linear temporal logic, and the full branching time logic. Several representations of formulas as graphlike structures are discussed, and ...
  • 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 ...