6 found
Order:
  1.  26
    Complexity Results for Modal Dependence Logic.Peter Lohmann & Heribert Vollmer - 2013 - Studia Logica 101 (2):343-366.
    Modal dependence logic was introduced recently by Väänänen. It enhances the basic modal language by an operator = (). For propositional variables p 1, . . . , p n , = (p 1, . . . , p n-1, p n ) intuitively states that the value of p n is determined by those of p 1, . . . , p n-1. Sevenster (J. Logic and Computation, 2009) showed that satisfiability for modal dependence logic is complete for nondeterministic (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  2.  27
    Proof Complexity of Propositional Default Logic.Olaf Beyersdorff, Arne Meier, Sebastian Müller, Michael Thomas & Heribert Vollmer - 2011 - Archive for Mathematical Logic 50 (7-8):727-742.
    Default logic is one of the most popular and successful formalisms for non-monotonic reasoning. In 2002, Bonatti and Olivetti introduced several sequent calculi for credulous and skeptical reasoning in propositional default logic. In this paper we examine these calculi from a proof-complexity perspective. In particular, we show that the calculus for credulous reasoning obeys almost the same bounds on the proof size as Gentzen’s system LK. Hence proving lower bounds for credulous reasoning will be as hard as proving lower bounds (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  3.  8
    Dependence Logic with a Majority Quantifier.Arnaud Durand, Johannes Ebbing, Juha Kontinen & Heribert Vollmer - 2015 - Journal of Logic, Language and Information 24 (3):289-305.
    We study the extension of dependence logic \ by a majority quantifier \ over finite structures. We show that the resulting logic is equi-expressive with the extension of second-order logic by second-order majority quantifiers of all arities. Our results imply that, from the point of view of descriptive complexity theory, \\) captures the complexity class counting hierarchy. We also obtain characterizations of the individual levels of the counting hierarchy by fragments of \\).
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  4.  4
    On the Parameterized Complexity of Non-Monotonic Logics.Arne Meier, Irina Schindler, Johannes Schmidt, Michael Thomas & Heribert Vollmer - 2015 - Archive for Mathematical Logic 54 (5-6):685-710.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  5.  1
    Modal Independence Logic.Juha Kontinen, Julian-Steffen Müller, Henning Schnoor & Heribert Vollmer - 2014 - In Rajeev Goré, Barteld Kooi & Agi Kurucz (eds.), Advances in Modal Logic, Volume 10. CSLI Publications. pp. 353-372.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  6. A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits.Anselm Haak & Heribert Vollmer - forthcoming - Annals of Pure and Applied Logic.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark