In this paper, we introduce a new approach to independent quantifiers, as originally introduced in Informational independence as a semantic phenomenon by Hintikka and Sandu [9] under the header of independence-friendly languages. Unlike other approaches, which rely heavily on compositional methods, we shall analyze independent quantifiers via equilibriums in strategic games. In this approach, coined equilibrium semantics, the value of an IF sentence on a particular structure is determined by the expected utility of the existential player in any of the (...) game’s equilibriums. This approach was suggested in Henkin quantifiers and complete problems by Blass and Gurevich [2] but has not been taken up before. We prove that each rational number can be realized by an IF sentence. We also give a lower and upper bound on the expressive power of IF logic under equilibrium semantics. (shrink)

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, (...) our results imply a dichotomy result: every independence-friendly quantifier prefix is either decidable in LOGSPACE or NP hard. (shrink)

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, (...) by means of notions from computational complexity. This approach enables us to compare propositional logic before and after the IF make-over. We observe that all but one of the best-known decision problems experience a complexity jump, provided that the complexity classes at hand are not equal. Our results concern every discipline that incorporates some notion of independence such as computer science, natural language semantics, and game theory. A corollary of one of our theorems illustrates this claim with respect to the latter discipline. (shrink)

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 (...) the fragment of SNP whose formulas involve only negative occurrences of relation symbols, only monadic second-order quantifiers, and no occurrences of the equality symbol. It remains an open problem whether MMSNP enjoys the dichotomy property. In the present paper, SNP and MMSNP are characterized in terms of partially ordered connectives. More specifically, SNP is characterized using the logic D of partially ordered connectives introduced in Blass and Gurevich (Annals of Pure and Applied Logic, 32, 1–16, 1986), Sandu and Väänänen (Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 38, 361–372 1992), and MMSNP employing a generalization C of D introduced in the present paper. (shrink)

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 (...) fragment of . We also show that IFML becomes undecidable if we add the identity symbol to its vocabulary by means of a reduction from the tiling problem. (shrink)

In recent work, semantic games of independence-friendly logic were studied in strategic form in terms of Nash equilibria. The class of strategic games of independence-friendly logic is contained in the class of win-loss, zero-sum two-player games. In this note we draw on the theory of linear programming to develop tools to analyze the value of such games. We give two applications of these tools to independence-friendly logic under the so-called equilibrium semantics.