Switch to: References

Add citations

You must login to add citations.
  1. Dichotomy result for independence-friendly prefixes of generalized quantifiers.Merlijn Sevenster - 2014 - Journal of Symbolic Logic 79 (4):1224-1246.
    We study the expressive power of independence-friendly quantifier prefixes composed of universal$\left$, existential$\left$, and majority quantifiers$\left$. We provide four quantifier prefixes that can express NP hard properties and show that all quantifier prefixes capable of expressing NP-hard properties embed at least one of these four quantifier prefixes. As for the quantifier prefixes that do not embed any of these four quantifier prefixes, we show that they are equivalent to a first-order quantifier prefix composed of$\forall x$,$\exists x$, and Mx. In unison, (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  • Signalling in independence-friendly logic.F. Barbero & G. Sandu - 2014 - Logic Journal of the IGPL 22 (4):638-664.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • Independence-friendly logic without Henkin quantification.Fausto Barbero, Lauri Hella & Raine Rönnholm - 2021 - Archive for Mathematical Logic 60 (5):547-597.
    We analyze the expressive resources of \ logic that do not stem from Henkin quantification. When one restricts attention to regular \ sentences, this amounts to the study of the fragment of \ logic which is individuated by the game-theoretical property of action recall. We prove that the fragment of prenex AR sentences can express all existential second-order properties. We then show that the same can be achieved in the non-prenex fragment of AR, by using “signalling by disjunction” instead of (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Complexity of syntactical tree fragments of Independence-Friendly logic.Fausto Barbero - 2021 - Annals of Pure and Applied Logic 172 (1):102859.
    A dichotomy result of Sevenster (2014) [29] completely classified the quantifier prefixes of regular Independence-Friendly (IF) logic according to the patterns of quantifier dependence they contain. On one hand, prefixes that contain “Henkin” or “signalling” patterns were shown to characterize fragments of IF logic that capture NP-complete problems; all the remaining prefixes were shown instead to be essentially first-order. In the present paper we develop the machinery which is needed in order to extend the results of Sevenster to non-prenex, regular (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Cooperation in Games and Epistemic Readings of Independence-Friendly Sentences.Fausto Barbero - 2017 - Journal of Logic, Language and Information 26 (3):221-260.
    In the literature on logics of imperfect information it is often stated, incorrectly, that the Game-Theoretical Semantics of Independence-Friendly quantifiers captures the idea that the players of semantical games are forced to make some moves without knowledge of the moves of other players. We survey here the alternative semantics for IF logic that have been suggested in order to enforce this “epistemic reading” of sentences. We introduce some new proposals, and a more general logical language which distinguishes between “independence from (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Independence friendly logic.Tero Tulenheimo - 2010 - Stanford Encyclopedia of Philosophy.
    Direct download  
     
    Export citation  
     
    Bookmark   9 citations