Complexity Results for Modal Dependence Logic

Modal dependence logic was introduced recently by Väänänen. It enhances the basic modal language by an operator = (). For propositional variables p ₁, . . . , p _n , = (p ₁, . . . , p _n-1, p _n ) intuitively states that the value of p _n is determined by those of p ₁, . . . , 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.     

On Sahlqvist Formulas in Relevant Logic

This paper defines a Sahlqvist fragment for relevant logic and establishes that each class of frames in the Routley-Meyer semantics which is definable by a Sahlqvist formula is also elementary, that is, it coincides with the class of structures satisfying a given first order property calculable by a Sahlqvist-van Benthem algorithm. Furthermore, we show that some classes of Routley-Meyer frames definable by a relevant formula are not elementary.     

Deterministic Chaos and Computational Complexity: the Case of Methodological Complexity Reductions

Some problems rarely discussed in traditional philosophy of science are mentioned: The empirical sciences using mathematico-quantitative theoretical models are frequently confronted with several types of computational problems posing primarily methodological limitations on explanatory and prognostic matters. Such limitations may arise from the appearances of deterministic chaos and (too) high computational complexity in general. In many cases, however, scientists circumvent such limitations by utilizing reductional approximations or complexity reductions for intractable problem formulations, thus constructing new models which are computationally tractable. Such activities are compared with reduction types (more) established in philosophy of science. This revised version was published online in August 2006 with corrections to the Cover Date.     

Inverse Images of Box Formulas in Modal Logic

We investigate, for several modal logics but concentrating on KT, KD45, S4 and S5, the set of formulas B for which ${\square B}$ is provably equivalent to ${\square A}$ for a selected formula A (such as p, a sentence letter). In the exceptional case in which a modal logic is closed under the (‘cancellation’) rule taking us from ${\square C \leftrightarrow \square D}$ to ${C \leftrightarrow D}$ , there is only one formula B, to within equivalence, in this inverse image, as we shall call it, of ${\square A}$ (relative to the logic concerned); for logics for which the intended reading of “ ${\square}$ ” is epistemic or doxastic, failure to be closed under this rule indicates that from the proposition expressed by a knowledge- or belief-attribution, the propositional object of the attitude in question cannot be recovered: arguably, a somewhat disconcerting situation. More generally, the inverse image of ${\square A}$ may comprise a range of non-equivalent formulas, all those provably implied by one fixed formula and provably implying another—though we shall see that for several choices of logic and of the formula A, there is not even such an ‘interval characterization’ of the inverse image (of ${\square A}$ ) to be found.     

Epistemic Operators in Dependence Logic

The properties of the ${\forall^{1}}$ quantifier defined by Kontinen and Väänänen in [13] are studied, and its definition is generalized to that of a family of quantifiers ${\forall^{n}}$ . Furthermore, some epistemic operators δ ⁿ for Dependence Logic are also introduced, and the relationship between these ${\forall^{n}}$ quantifiers and the δ ⁿ operators are investigated. The Game Theoretic Semantics for Dependence Logic and the corresponding Ehrenfeucht- Fraissé game are then adapted to these new connectives. Finally, it is proved that the ${\forall^{1}}$ quantifier is not uniformly definable in Dependence Logic, thus answering a question posed by Kontinen and Väänänen in the above mentioned paper.     

Dynamical Social Psychology: Complexity and Coherence in Human Experience

Human experience reflects the interplay of multiple influences operating on various time scales to promote constantly evolving patterns of thought, emotion, and action. Although the complexity and dynamism of personal and social phenomena have long been recognized, they are difficult to investigate using traditional research methods. This article provides an overview of dynamical social psychology, an approach adapted from dynamical systems theory that is designed to capture the complementary tendencies of stability and dynamism at different levels of social reality, from private thoughts to intergroup relations. Utilizing time-series analyses and computer simulations, this perspective documents the emergence of global properties from the interaction of basic elements in mental and social systems and investigates the time-dependent relation between external influences and a system’s internally generated dynamics. The dynamical approach enables social psychology to advance as a precise science while preserving the basic insights that launched the field over a century ago.     

One's Modus Ponens: Modality,Coherence and Logic

Recently, there has been a shift away from traditional truth‐conditional accounts of meaning towards non‐truth‐conditional ones, e.g., expressivism, relativism and certain forms of dynamic semantics. Fueling this trend is some puzzling behavior of modal discourse. One particularly surprising manifestation of such behavior is the alleged failure of some of the most entrenched classical rules of inference; viz., modus ponens and modus tollens. These revisionary, non‐truth‐conditional accounts tout these failures, and the alleged tension between the behavior of modal vocabulary and classical logic, as data in support of their departure from tradition, since the revisionary semantics invalidate some of these patterns. I, instead, offer a semantics for modality with the resources to accommodate the puzzling data while preserving classical logic, thus affirming the tradition that modals express ordinary truth‐conditional content. My account shows that the real lesson of the apparent counterexamples is not the one the critics draw, but rather one they missed: namely, that there are linguistic mechanisms, reflected in the logical form, that affect the interpretation of modal language in a context in a systematic and precise way, which have to be captured by any adequate semantic account of the interaction between discourse context and modal vocabulary. The semantic theory I develop specifies these mechanisms and captures precisely how they affect the interpretation of modals in a context, and do so in a way that both explains the appearance of the putative counterexamples and preserves classical logic.     

二阶扩展逻辑的复杂性与表达能力

本文研究了在所有有穷结构上SO．HORN＊,SO—HORNτ和SO-HORNτ的表达能力。我们证明了SO-HORNτ,SO—HORN＊τ和FO（LFP）的表达能力是一致的,SO—HORN＊是SO-HORNτ的一个严格子逻辑。为了证明这一结果,我们提出了DATALOG＊程序,DATALOGτ程序以及它们的分层版本S-DATALOG＊程序利S-DATALOGτ程序。我们证明了在所有有穷结构上DATALOGτ和S-DATALOGτ是等价的,并且DATALOG。足DATALOGτ的一个严格子逻辑。最后我们还用两种方法证明了SO-HORN的一个扩展版本SO—EHORNτ逻辑可以在所有有穷结构有有结构上刻画co—NP。     

Three Complexity Problems in Quantified Fuzzy Logic

We prove that the sets of standard tautologies of predicate Product Logic and of predicate Basic Logic, as well as the set of standard-satisfiable formulas of predicate Basic Logic are not arithmetical, thus finding a rather satisfactory solution to three problems proposed by Hájek in [H01].     

Infinitary Action Logic: Complexity, Models and Grammars

Action logic of Pratt [21] can be presented as Full Lambek Calculus FL [14, 17] enriched with Kleene star *; it is equivalent to the equational theory of residuated Kleene algebras (lattices). Some results on axiom systems, complexity and models of this logic were obtained in [4, 3, 18]. Here we prove a stronger form of *-elimination for the logic of *-continuous action lattices and the –completeness of the equational theories of action lattices of subsets of a finite monoid and action lattices of binary relations on a finite universe. We also discuss possible applications in linguistics. Presented by Jacek Malinowski     

Compositional Natural Language Semantics using Independence Friendly Logic or Dependence Logic

Independence Friendly Logic, introduced by Hintikka, is a logic in which a quantifier can be marked for being independent of other quantifiers. Dependence logic, introduced by Väänänen, is a logic with the complementary approach: for a quantifier it can be indicated on which quantifiers it depends. These logics are claimed to be useful for many phenomena, for instance natural language semantics. In this contribution we will compare these two logics by investigating their application in a compositional analysis of the de dicto - de re ambiguity in natural language. It will be argued that Independence Friendly logic is suitable, whereas Dependence Logic is not.     

Expressing Second-order Sentences in Intuitionistic Dependence Logic

Intuitionistic dependence logic was introduced by Abramsky and Väänänen [1] as a variant of dependence logic under a general construction of Hodges’ (trump) team semantics. It was proven that there is a translation from intuitionistic dependence logic sentences into second order logic sentences. In this paper, we prove that the other direction is also true, therefore intuitionistic dependence logic is equivalent to second order logic on the level of sentences.     

Probabilistic Logic Under Coherence, Conditional Interpretations, and Default Reasoning

We study a probabilistic logic based on the coherence principle of de Finetti and a related notion of generalized coherence (g-coherence). We examine probabilistic conditional knowledge bases associated with imprecise probability assessments defined on arbitrary families of conditional events. We introduce a notion of conditional interpretation defined directly in terms of precise probability assessments. We also examine a property of strong satisfiability which is related to the notion of toleration well known in default reasoning. In our framework we give more general definitions of the notions of probabilistic consistency and probabilistic entailment of Adams. We also recall a notion of strict p-consistency and some related results. Moreover, we give new proofs of some results obtained in probabilistic default reasoning. Finally, we examine the relationships between conditional probability rankings and the notions of g-coherence and g-coherent entailment.     

On The Computational Consequences of Independence in Propositional Logic

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.