5 found
Sort by:
  1. Gabriel Sandu & Merlijn Sevenster (forthcoming). Equilibrium Semantics. Annals of Pure and Applied Logic.
    Direct download  
     
    My bibliography  
     
    Export citation  
  2. Merlijn Sevenster (2010). Decidability of Independence-Friendly Modal Logic. Review of Symbolic Logic 3 (3):415-441.
    In this paper we consider an independence-friendly modal logic, IFML. It follows from results in the literature that qua expressive power, IFML is a fragment of second-order existential logic, , that cannot be translated into first-order logic. It is also known that IFML lacks the tree structure property. We show that IFML has the , a weaker version of the tree structure property, and that its satisfiability problem is solvable in 2NEXP. This implies that this paper reveals a new decidable (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  3. Merlijn Sevenster & Gabriel Sandu (2010). Equilibrium Semantics of Languages of Imperfect Information. Annals of Pure and Applied Logic 161 (5):618-631.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  4. Lauri Hella, Merlijn Sevenster & Tero Tulenheimo (2008). Partially Ordered Connectives and Monadic Monotone Strict Np. Journal of Logic, Language and Information 17 (3):323-344.
    Motivated by constraint satisfaction problems, Feder and Vardi (SIAM Journal of Computing, 28, 57–104, 1998) set out to search for fragments of satisfying the dichotomy property: every problem definable in is either in P or else NP-complete. Feder and Vardi considered in this connection two logics, strict NP (or SNP) and monadic, monotone, strict NP without inequalities (or MMSNP). The former consists of formulas of the form , where is a quantifier-free formula in a relational vocabulary; and the latter is (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  5. Merlijn Sevenster (2006). On the Computational Consequences of Independence in Propositional Logic. Synthese 149 (2):257 - 283.
    Sandu and Pietarinen [Partiality and Games: Propositional Logic. Logic J. IGPL 9 (2001) 101] study independence friendly propositional logics. That is, traditional propositional logic extended by means of syntax that allow connectives to be independent of each other, although the one may be subordinate to the other. Sandu and Pietarinen observe that the IF propositional logics have exotic properties, like functional completeness for three-valued functions. In this paper we focus on one of their IF propositional logics and study its properties, (...)
    No categories
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation