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)

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.

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)

Excessive fear generalisation is a feature characteristic of clinical anxiety and has been linked to its aetiology. Previous animal studies have shown that the mere passage of time increases fear generalisation and that brief exposure to training cues prior to long-term testing reverses this effect. The current study examined these phenomena in humans. Healthy participants learned the relationship between the presentation of a picture of a neutral male face and the delivery of a mild shock. One group was immediately tested (...) with a novel picture of a somewhat different male face (generalisation test). Another group was tested one week later. A third group was also tested one week later and was additionally exposed to the training picture prior to testing. During picture presentations, shock-expectancy ratings were obtained as a measure of fear. Fear generalisation increased from the immediate test to the 1-week follow-up test. This result could not be attributed to level of neuroticism or a general increase in fear (incubation). Furthermore, the time-dependent increase in fear generalisation vanished following brief exposure to the training picture. Results indicate that human fear generalisation is a temporally dynamic process and that memory for stimulus details can be re-established following a reminder treatment. (shrink)

Background Genuine uncertainty on superiority of one intervention over the other is called equipoise. Physician-investigators in randomized controlled trials need equipoise at least in studies with more than minimal risks. Ideally, this equipoise is also present in patient-participants. In pediatrics, data on equipoise are lacking. We hypothesize that 1) lack of equipoise at enrolment among parents may reduce recruitment; 2) lack of equipoise during participation may reduce retention in patients assigned to a less favoured treatment-strategy. Methods We compared preferences of (...) parents/patients at enrolment, documented by a questionnaire, with preferences developed during follow-up by an interview-study to investigate equipoise of child-participants and parents in the BeSt-for-Kids-study. This trial in new-onset Juvenile Idiopathic Arthritis-patients consists of three strategies. One strategy comprises initial treatment with a biological disease-modifying-antirheumatic-drug, currently not standard-of-care. Semi-structured interviews were conducted with 23 parents and 7 patients, median 11 months after enrolment. Results Initially most parents and children were not in equipoise. Parents/patients who refused participation, regularly declined due to specific preferences. Many participating families preferred the biological-first-strategy. They participated to have a chance for this initial treatment, and would even consider stopping trial-participation when not randomized for it. Their conviction of superiority of the biological-first strategy was based on knowledge from internet and close relations. According to four parents, the physician-investigator preferred the biological-first-strategy, but the majority stated that she had no preferred strategy. In phase 2, preferences tended to change to the treatment actually received. Conclusions Lack of equipoise during enrolment did not reduce study recruitment, mainly due to the fact that preferred treatment was only available within the study. Still, when developing a trial it is important to evaluate whether the physicians’ research question is in line with preferences of the patient-group. By exploring so-called ‘informed patient-group’-equipoise, successful recruitment may be enhanced and bias avoided. In our study, lack of equipoise during trial-participation did not reduce retention in those assigned to a less favoured option. We observed a change for preference towards treatment actually received, possibly explained by comparable outcomes in all three arms. (shrink)

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 IF sentences. This involves shifting attention from quantifier prefixes to a (rather general) class of syntactical tree prefixes. We partially classify the fragments of regular IF logic that are thus determined by syntactical trees; in particular, a) we identify four classes of tree prefixes that are neither signaling nor Henkin, and yet express NP-complete problems and other second-order concepts; and b) we give more general criteria for checking the first-orderness of an IF sentence. (shrink)

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 exponential time.In this paper we consider fragments of modal dependence logic obtained by restricting the set of allowed propositional connectives. We show that satisfiability for poor man’s dependence logic, the language consisting of formulas built from literals and dependence atoms using ${\wedge, \square, \lozenge}$ (i. e., disallowing disjunction), remains NEXPTIME-complete. If we only allow monotone formulas (without negation, but with disjunction), the complexity drops to PSPACE-completeness.We also extend Väänänen’s language by allowing classical disjunction besides dependence disjunction and show that the satisfiability problem remains NEXPTIME-complete. If we then disallow both negation and dependence disjunction, satisfiability is complete for the second level of the polynomial hierarchy. Additionally we consider the restriction of modal dependence logic where the length of each single dependence atom is bounded by a number that is fixed for the whole logic. We show that the satisfiability problem for this bounded arity dependence logic is PSPACE-complete and that the complexity drops to the third level of the polynomial hierarchy if we then disallow disjunction.In this way we completely classify the computational complexity of the satisfiability problem for all restrictions of propositional and dependence operators considered by Väänänen and Sevenster. (shrink)

This essay series attempts to stimulate the debate about the moral challenges that internationalisation confronts us with, both in the Netherlands and abroad, and in particular for Artist-in-Residencies (AIRs). The publication is a reflection on how the crisis is reconsidering our international ambitions, starting from a post-COVID society. Internationalisation is an inevitable reality, inherent to the art landscape. The current time calls for a critical reflection on major issues such as climate inequality, plurality and the Western-dominant canon. 0With contributions and (...) critical insights by Jeanne van Heeswijk, Jack Segbars, Erik Hagoort, Pascal Gielen, Cecilia Bengtsson, Merlijn Twaalfhoven, Hicham Khalidi, reinaart vanhoe and Suzanne van der Beek. Thanks to Jan van Eyck Academie, Mondriaan Fonds, Prins Bernhard Cultuurfonds en het Amsterdams Fonds voor de Kunst for their support. (shrink)

We present a compositional semantics for first-order logic with imperfect information that is equivalent to Sevenster and Sandu’s equilibrium semantics (under which the truth value of a sentence in a finite model is equal to the minimax value of its semantic game). Our semantics is a generalization of an earlier semantics developed by the first author that was based on behavioral strategies, rather than mixed strategies.

The hybrid logic and the independence friendly modal logic IFML are compared for their expressive powers. We introduce a logic IFML c having a non-standard syntax and a compositional semantics; in terms of this logic a syntactic fragment of IFML is singled out, denoted IFML c . (In the Appendix it is shown that the game-theoretic semantics of IFML c coincides with the compositional semantics of IFML c .) The hybrid logic is proven to be strictly more expressive than IFML (...) c . By contrast, and the full IFML are shown to be incomparable for their expressive powers. Building on earlier research (Tulenheimo and Sevenster 2006), a PSPACE -decidable fragment of the undecidable logic is disclosed. This fragment is not translatable into the hybrid logic and has not been studied previously in connection with hybrid logics. In the Appendix IFML c is shown to lack the property of ‘quasi-positionality’ but proven to enjoy the weaker property of ‘ bounded quasi-positionality’. The latter fact provides from the IFML internal perspective an account of what makes the compositional semantics of IFML c possible. (shrink)

The present paper provides novel results on the model theory of Independence friendly modal logic. We concentrate on its particularly well-behaved fragment that was introduced in Tulenheimo and Sevenster (Advances in Modal Logic, 2006). Here we refer to this fragment as ‘Simple IF modal logic’ (IFML s ). A model-theoretic criterion is presented which serves to tell when a formula of IFML s is not equivalent to any formula of basic modal logic (ML). We generalize the notion of bisimulation (...) familiar from ML; the resulting asymmetric simulation concept is used to prove that IFML s is not closed under complementation. In fact we obtain a much stronger result: the only IFML s formulas admitting their classical negation to be expressed in IFML s itself are those whose truth-condition is in fact expressible in ML. (shrink)