Tero Tulenheimo

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.

G. H. von Wright proposed that a temporal interval exemplifies a real contradiction if at least one part of any division of this interval involves the presence of contradictorily related (though non-simultaneous) states. In connection with intervals, two negations must be discerned: 'does not hold at an interval' and 'fails throughout an interval'. Von Wright did not distinguish the two. As a consequence, he made a mistake in indicating how to use his logical symbolism to express the notion of real contradiction. The present paper aims to reconstruct and philosophically motivate von Wright's argument for the possibility of real contradictions.

Hintikka's second generation epistemic logic introduces a syntactic device allowing to express independence relations between certain logical constants. De re knowledge attributions can be reformulated in terms of quantifier independence, but the reformulation does not extend to non-factive attitudes like belief. There, formulae with independent quantifiers serve to express a new type of attitude, intermediate between de dicto and de re, called ‘de objecto’: in each possible world compatible with the agent's belief, there is an individual with the specified property – in each world the same individual, which or who need not exist actually. The philosophical benefits of our analysis of propositional attitudes include a refined account of the behaviour of proper names as well as of indefinite and definite descriptions in attitude reports. Some remarks about perception and about the hallucination argument are also presented

When discussing knowledge, two relations are of interest: justified doxastic accessibility \ , she is in \ ) and justification equivalence \ exactly the same justified beliefs that she has in \ ). Speaking of compatibility with the agent’s justified beliefs is potentially ambiguous: either of the two relations \ or \ can be meant. I discuss the possibility of identifying the relation of epistemic accessibility \ , she is in \ ) with the union of \ and \ . Neither Gettier’s examples nor the ‘fake barn’ cases contradict this identification. However, the proposal leads to justification equivalent scenarios being symmetric with respect to knowledge: we cannot know a true proposition in a scenario if it is false in a justification equivalent scenario. This analysis may appear to render non-trivial knowledge impossible. This conclusion follows if the extra premise is granted that for all relevant true propositions there is a justification equivalent scenario in which the proposition is false. I provide a meaning-theoretic argument against this premise. I conclude by pointing out problems that would ensue from giving up the proposed connection between \ , \ and \ and allowing asymmetry of justification equivalent scenarios relative to knowledge

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.