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.

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

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

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

Typical applications of Hintikka’s game-theoretical semantics give rise to semantic attributes—truth, falsity—expressible in the $\Sigma^{1}_{1}$-fragment of second-order logic. Actually a much more general notion of semantic attribute is motivated by strategic considerations. When identifying such a generalization, the notion of classical negation plays a crucial role. We study two languages, $L_{1}$ and $L_{2}$, in both of which two negation signs are available: $\rightharpoondown $ and $\sim$. The latter is the usual GTS negation which transposes the players’ roles, while the former will be interpreted via the notion of mode. Logic $L_{1}$ extends independence-friendly logic; $\rightharpoondown $ behaves as classical negation in $L_{1}$. Logic $L_{2}$ extends $L_{1}$, and it is shown to capture the $\Sigma^{2}_{1}$-fragment of third-order logic. Consequently the classical negation remains inexpressible in $L_{2}$