Browsing by Subject "Second-order logic"

Sort by: Order: Results:

  • 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 ...
  • On the complexity of horn and krom fragments of second-order boolean logic 
    Hannula, Miika; Kontinen, Juha; Lück, Martin; Virtema, Jonni (Saarbrücken/Wadern, Germany : Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, 2021)
    Second-order Boolean logic is a generalization of QBF, whose constant alternation fragments are known to be complete for the levels of the exponential time hierarchy. We consider two types of restriction of this logic: 1) ...
  • On the complexity of team logic and its two-variable fragment 
    Lück, Martin (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2018)
    We study the logic FO(∼), the extension of first-order logic with team semantics by unrestricted Boolean negation. It was recently shown to be axiomatizable, but otherwise has not yet received much attention in questions ...