Search

Aristotelian diagrams, such as the square of opposition, are well-known in the context of normal modal logics (i.e., systems of modal logic which can be given a relational semantics in terms of Kripke models). This paper studies Aristotelian diagrams for non-normal systems of modal logic (based on neighborhood semantics, a topologically inspired generalization of relational semantics). In particular, we investigate the phenomenon of logic-sensitivity of Aristotelian diagrams. We distinguish between four different types of logic-sensitivity, viz. with respect to (i) Aristotelian families, (ii) logical equivalence of formulas, (iii) contingency of formulas, and (iv) Boolean subfamilies of a given Aristotelian family. We provide concrete examples of Aristotelian diagrams that illustrate these four types of logic-sensitivity in the realm of normal modal logic. Next, we discuss more subtle examples of Aristotelian diagrams, which are not sensitive with respect to normal modal logics, but which nevertheless turn out to be highly logic-sensitive once we turn to non-normal systems of modal logic.

Propositional and modal inclusion logic are formalisms that belong to the family of logics based on team semantics. This article investigates the model checking and validity problems of these logics. We identify complexity bounds for both problems, covering both lax and strict team semantics. By doing so, we come close to finalizing the programme that aims to completely classify the complexities of the basic reasoning problems for modal and propositional dependence, independence and inclusion logics.

We shall be concerned with the modal logic BK—which is based on the Belnap–Dunn four-valued matrix, and can be viewed as being obtained from the least normal modal logic K by adding ‘strong negation’. Though all four values ‘truth’, ‘falsity’, ‘neither’ and ‘both’ are employed in its Kripke semantics, only the first two are expressible as terms. We show that expanding the original language of BK to include constants for ‘neither’ or/and ‘both’ leads to quite unexpected results. To be more precise, adding one of these constants has the effect of eliminating the respective value at the level of BK-extensions. In particular, if one adds both of these, then the corresponding lattice of extensions turns out to be isomorphic to that of ordinary normal modal logics.

The majority of works on modal many-valued logics consider Kripke-style possible worlds frames as the principal semantics despite their well-known axiomatizability issues when considering non-Boolean accessibility relations. The present work explores a more general semantical picture, namely a many-valued version of the classical neighborhood semantics. We present it in two levels of generality. First, we work with modal languages containing only the two usual unary modalities, define neighborhood frames over algebras of the logic FL ew with operators, and show their relation with the usual Kripke semantics (this is actually the highest level of generality where one can give a straightforward definition of the Kripke-style semantics). Second, we define generalized neighborhood frames for arbitrary modal languages over a given class of algebras for an arbitrary protoalgebraic logic and, assuming certain additional conditions, axiomatize the logic of all such frames (which generalizes the completeness theorem of the classical modal logic E with respect to classical neighborhood frames).

Decidability of the validity problem is established for a family of many-valued modal logics, notably Godel modal logics, where propositional connectives are evaluated according to the order of values in a complete sublattice of the real unit interval [ 0 , 1 ] , and box and diamond modalities are evaluated as infima and suprema over (many-valued) Kripke frames. If the sublattice is infinite and the language is sufficiently expressive, then the standard semantics for such a logic lacks the finite model property. It is shown here, however, that, given certain regularity conditions, the finite model property holds for a new semantics for the logic, providing a basis for establishing decidability and PSPACE-completeness. Similar results are also established for S5 logics that coincide with one-variable fragments of first-order many-valued logics. In particular, a first proof is given of the decidability and co-NP-completeness of validity in the one-variable fragment of first-order Godel logic.

In the literature, little attention has been paid to the development of solvers for systems of mathematical fuzzy logic, and in particular, there are few works concerned with infinitely-valued logics. In this paper it is presented mNiBLoS (a modal Nice BL-Logics Solver): a modular SMT-based solver complete with respect to a wide family of continuous t-norm based fuzzy modal logics (both with finite and infinite universes), restricting the modal structures to the finite ones. At the propositional level, the solver works with some of the best known infinitely-valued fuzzy logics (including BL, Łukasiewicz, Gödel and product logics), and with all the continuous t-norm based logics that can be finitely expressed in terms of the previous ones; concerning the modal expansion, mNiBLoS imposes no boundary on the cardinality of the modal structures considered. The solver allows to test 1-satisfiability of equations, tautologicity and logical consequence problems. The logical language supported extends the usual one of fuzzy modal logics with rational constants and the Monteiro-Baaz Δ operator. The code of mNiBLoS is of free distribution and can be found in the web page of the author. © 2016 Elsevier Inc., This work was supported by the CSIC Intramural project 201450E045:“Logal: Lógica y algoritmos”, the joint project of Austrian Science Fund (FWF) I1897-N25 and Czech Science Foundation (GACR) 15-34650L, the institutional support RVO:67985807 and the MINECO project EdeTRI:TIN2012-39348-C02-01. The author wishes to thank the anonymous reviewers for their useful commentaries.

Starting off from the usual language of modal logic for multi-agent systems dealing with the agents’ knowledge/belief and common knowledge/belief we define so-called epistemic Kripke structures for intu- itionistic (common) knowledge/belief. Then we introduce corresponding deductive systems and show that they are sound and complete with respect to these semantics.

Two conjectures on the covering-based rough set semantics for modal logics in 35 are answered. The C 2 and C 5 semantics give rise to the same modal system S4. There are Galois connections between C 2 and C 5 which lead to the covering-based semantics for the temporal logic system S4t. The P 1 and C 4 semantics give rise to the same modal system KTB.

Connections between certain types of categories (logoses and toposes) and intuitionistic predicate logic was established in 1960–1970 by Lowvere. The possibility of extending this connection to some types of modal logics by using the internal structure of categories of particular type (logos) was also established. Category-theoretical constructs were hence used as one of the possible semantic interpretations of intuitionistic logic. This interpretation has also included intuionistic modal logics using different semantical tools such as adjoint pair of functors. In this paper, we discuss one of the possible extension of intuitionistic logic.

Justification logics connect with modal logics, replacing unstructured modal operators with justification terms explicitly representing interdependence and flow of reasoning. The number of justification logics quickly grew from an initial single instance to a handful to about a dozen examples. In this paper we provide very general, though partly non-constructive, methods that cover all previous examples, and extend to an infinite family of modal logics. The full range of the phenomenon is not known. The extent to which constructive methods apply is also not known, but it is related to the availability of cut-free proof methods for modal logics.

We consider the family of logics from NExt(KTB) which are determined by linear frames with reflexive and symmetric relation of accessibility. The condition of linearity in such frames was first defined in the paper [9]. We prove that the cardinality of the logics under consideration is uncountably infinite.

We present a graph approach to intuitionistic modal logics, which provides uniform formalisms for expressing, analysing and comparing Kripke-like semantics. This approach uses the flexibility of graph calculi to express directly and intuitively possible-world semantics for intuitionistic modal logics. We illustrate the benefits of these ideas by applying them to some familiar cases of intuitionistic multi-modal semantics.

We translate unconstrained and constrained input/output logics as introduced by Makinson and van der Torre to modal logics, using adaptive logics for the constrained case. The resulting reformulation has some additional benefits. First, we obtain a proof-theoretic (dynamic) characterization of input/output logics. Second, we demonstrate that our framework naturally gives rise to useful variants and allows to express important notions that go beyond the expressive means of input/output logics, such as violations and sanctions.

In this work, we combine features from Justification Logics and Logics of Plausibility-Based Beliefs to build a logic for Multi-Agent Systems where each agent can explicitly state his justification for believing in a given sentence. Our logic is a normal modal logic based on the standard Kripke semantics, where we provide a semantic definition for the evidence terms and define the notion of plausible evidence for an agent, based on plausibility relations in the model. As we deal with beliefs, justifications can be faulty and unreliable. In our logic, agents can disagree not only over whether a sentence is true or false, but also on whether some evidence is a valid justification for a sentence or not. After defining our logic and its semantics, we provide a strongly complete axiomatic system for it, show that it has the finite model property, analyze the complexity of its Model-Checking Problem and show that its Satisfiability Problem has the same complexity as the one from basic modal logics. Thus, this logic seems to be a good first step for the development of a dynamic logic that can model the processes of argumentation and debate in Multi-Agent Systems.

Combining multi-valued and modal logics into a single system is a long-standing concern in mathematical logic and computer science, see for example [7] and the literature cited there. Recent work in this trend [15, 17, 14] develops modal expansions of many-valued systems that are also inconsistencytolerant, along the tradition initiated by Belnap with his “useful four-valued logic” [3]. Our contribution continues on this line, and the specific problem we address is that of defining and axiomatizing the least modal logic over the four-element Belnap lattice. The problem was inspired by [5], but our solution is quite different from (and in some respects more satisfactory than) that of [5] in that we make an extensive and profitable use of algebraic and topological techniques. In fact, our algebraic and topological analyses of the logic have, in our opinion, an independent interest and contribute to the appeal of our approach. Kripke frames provide a semantics for modal logics that is both flexible with regards to intended applications and interpretations, and highly intuitive. When the non-modal part is multi-valued, though, one may wonder whether the accessibility relation between worlds should remain two-valued or be allowed to assume the same range of truth values as the logic itself. Starting from the point of view of AI applications, [7] argues forcefully that multiple values are an appropriate and useful modeling device. This is the approach taken in [5] and here, too. Our aim is to study the least modal logic over the Belnap lattice, that is, the logic determined by the class of all Kripke frames where the accessibility relation as well as semantic valuations are four-valued.

This paper presents an implementation of an automated theorem prover for first-order modal logic that works for the constant, cumulative, and varying domain of the modal logics D, T, S4, and S5. It is based on the connection calculus for classical logic and uses prefixes representing world paths and a prefix unification algorithm to capture the restrictions given by the Kripke semantics of the standard modal logics. This permits a modular and elegant treatment of the considered modal logics and yields an efficient implementation. Details of the calculus, the implementation and performance results on the QMLTP problem library are presented.

A new semantics with the finite model property is provided and used to establish decidability for Gödel modal logics based on (crisp or fuzzy) Kripke frames combined locally with Gödel logic. A similar methodology is also used to establish decidability, indeed co-NP-completeness, for a Gödel S5 logic that coincides with the one-variable fragment of first-order Gödel logic.

It is a celebrated result of McKinsey and Tarski [28] that S4 is the logic of the closure algebra Χ+ over any dense-in-itself separable metrizable space. In particular, S4 is the logic of the closure algebra over the reals R, the rationals Q, or the Cantor space C. By [5], each logic above S4 that has the finite model property is the logic of a subalgebra of Q+, as well as the logic of a subalgebra of C+. This is no longer true for R, and the main result of [5] states that each connected logic above S4 with the finite model property is the logic of a subalgebra of the closure algebra R+.In this paper we extend these results to all logics above S4. Namely, for a normal modal logic L, we prove that the following conditions are equivalent: (i) L is above S4, (ii) L is the logic of a subalgebra of Q+, (iii) L is the logic of a subalgebra of C+. We introduce the concept of a well-connected logic above S4 and prove that the following conditions are equivalent: (i) L is a well-connected logic, (ii) L is the logic of a subalgebra of the closure algebra $\xi _2^ + $ over the infinite binary tree, (iii) L is the logic of a subalgebra of the closure algebra ${\bf{L}}_2^ + $ over the infinite binary tree with limits equipped with the Scott topology. Finally, we prove that a logic L above S4 is connected iff L is the logic of a subalgebra of R+, and transfer our results to the setting of intermediate logics.Proving these general completeness results requires new tools. We introduce the countable general frame property (CGFP) and prove that each normal modal logic has the CGFP. We introduce general topological semantics for S4, which generalizes topological semantics the same way general frame semantics generalizes Kripke semantics. We prove that the categories of descriptive frames for S4 and descriptive spaces are isomorphic. It follows that every logic above S4 is complete with respect to the corresponding class of descriptive spaces. We provide several ways of realizing the infinite binary tree with limits, and prove that when equipped with the Scott topology, it is an interior image of both C and R. Finally, we introduce gluing of general spaces and prove that the space obtained by appropriate gluing involving certain quotients of L2 is an interior image of R.

One of natural combinations of Kripke complete modal logics is the product, an operation that has been extensively investigated over the last 15 years. In this paper we consider its analogue for arbitrary modal logics: to this end, we use product-like constructions on general frames and modal algebras. This operation was first introduced by Y. Hasimoto in 2000; however, his paper remained unnoticed until recently. In the present paper we quote some important Hasimoto's results, and reconstruct the product operation in an algebraic setting: the Boolean part of the resulting modal algebra is exactly the tensor product of original algebras (regarded as Boolean rings). Also, we propose a filtration technique for Kripke models based on tensor products and obtain some decidability results.

The family of temporal logics has recently been extended with logics for the specification of hyperproperties, such as noninterference or observational determinism. Hyperproperties relate multiple computation paths of a system by requiring that they satisfy a certain relationship, such as an identical valuation of the low-security outputs. Unlike classic temporal logics like LTL or CTL*, which refer to one computation path at a time, temporal logics for hyperproperties like HyperLTL and HyperCTL* can express such relationships by explicitly quantifying over multiple computation paths simultaneously. In this paper, we study the extended spectrum of temporal logics by relating the new logics to the linear-branching spectrum of process equivalences.

In his 1964 note, ‘Two Additions to Positive Implication’, A. N. Prior showed that standard axioms governing conjunction yield a nonconservative extension of the pure implicational intermediate logic OIC (order implicational calculus) of R. A. Bull. Here, after reviewing the situation with the aid of an adapted form of the Kripke semantics for intuitionistic and intermediate logics, we proceed to illuminate this example by transposing it to the setting of modal logic, and then relate it to the propositional logic of what have been called ‘Hilbert algebras with infimum’.

This paper develops sequent calculi for several classical modal logics. Utilizing a polymodal translation of the standard modal language, we are able to establish a base system for the minimal classical modal logic E from which we generate extensions (to include M, C, and N) in a modular manner. Our systems admit contraction and cut admissibility, and allow a systematic proof-search procedure of formal derivations.

International audience; This paper introduces and studies extensions of modal logics by investigating the soundness of classical modal axioms in a weighted framework. It discusses the notion of relevant weight values, in a specific weighted Kripke semantics and exploits accessibility relation properties. Different generalisations of the classical axioms are constructed and, from these, a typology of weighted axioms is built, distinguishing between four types, depending on their relations to their classical counterparts and to the, possibly equivalent, frame conditions.

Sequent calculi are proof systems that are exceptionally suitable for proving the decidability of a logic. Several relevance logics were proved decidable using a technique attributable to Curry and Kripke. Further enhancements led to a proof of the decidability of implicational ticket entailment by Bimbo and Dunn in [12, 13]. This paper uses a different adaptation of the same core proof technique to prove a group of positive modal logics (with disjunction but no conjunction) decidable.

The first step of the development of the idea of intuitionistic fuzziness (see [1]), was related to introducing an intuitionistic fuzzy interpretation of the classical (standard) modal operators “necessity” and “possibility” (see, e.g., [2, 3, 4, 5]). In the period 1988–1993, we defined eight new operators, extending the first two ones. In the end of last and in the beginning of this century, a lot of new operators were introduced. Here, we discuss the most interesting ones of them and study their basic properties.

This paper combines a non-contingency logic with an epistemic logic by means of fusions and products of modal systems. Some consequences of these interplays are pointed out.

International audience; In the literature there are at least two main formal structures to deal with situations of interactive epistemology: Kripke models and type spaces. As shown in many papers (see Aumann and Brandenburger in Econometrica 36:1161–1180, 1995; Baltag et al. in Synthese 169:301–333, 2009; Battigalli and Bonanno in Res Econ 53(2):149–225, 1999; Battigalli and Siniscalchi in J Econ Theory 106:356–391, 2002; Klein and Pacuit in Stud Log 102:297–319, 2014; Lorini in J Philos Log 42(6):863–904, 2013), both these frameworks can be used to express epistemic conditions for solution concepts in game theory. The main result of this paper is a formal comparison between the two and a statement of semantic equivalence with respect to two different logical systems: a doxastic logic for belief and an epistemic–doxastic logic for belief and knowledge. Moreover, a sound and complete axiomatization of these logics with respect to the two equivalent Kripke semantics and type spaces semantics is provided. Finally, a probabilistic extension of the result is also presented. A further result of the paper is a study of the relationship between the epistemic–doxastic logic for belief and knowledge and the logic STIT (the logic of “seeing to it that”) by Belnap and colleagues (Facing the future: agents and choices in our indeterminist world, 2001).

Provability logic GLP is well-known to be incomplete w.r.t. Kripke semantics. A natural topological semantics of GLP interprets modalities as derivative operators of a polytopological space. Such spaces are called GLP-spaces whenever they satisfy all the axioms of GLP . We develop some constructions to build nontrivial GLP-spaces and show that GLP is complete w.r.t. the class of all GLP-spaces.

We introduce a natural classification of normal extensions of the modal logic S4 in accordance to the volumes of clusters in the Kripke frames and prove the decidability of the classification. We distinguish the main logics in this classification and establish their important properties: finite axiomatizability, finite approximability, and recognizability.

The paper provides a preliminary study of algebraic semantics for modal and superintuitionistic non-monotonic logics. The main question answered is: how can non-monotonic inference be understood algebraically?

We examine the transitions between sets of possible worlds described by the compositional semantics of Modal Dependence Logic, and we use them as the basis for a dynamic version of this logic. We give a game theoretic semantics, a (compositional) transition semantics and a power game semantics for this new variant of modal Dependence Logic, and we prove their equivalence; and furthermore, we examine a few of the properties of this formalism and show that Modal Dependence Logic can be recovered from it by reasoning in terms of reachability. Then we show how we can generalize this approach to a very general formalism for reasoning about transformations between pointed Kripke models.

There are several known Lindstrom-style characterization results for basic modal logic. This paper proves a generic Lindstrom theorem that covers any normal modal logic corresponding to a class of Kripke frames definable by a set of formulas called strict universal Horn formulas. The result is a generalization of a recent characterization of modal logic with the global modality. A negative result is also proved in an appendix showing that the result cannot be strengthened to cover every first-order elementary class of frames. This is shown by constructing an explicit counterexample.

In this paper we introduce non-normal modal extensions of the sub-classical logics CLoN, CluN and CLaN, in the same way that S0.50 extends classical logic. The first modal system is both paraconsistent and paracomplete, while the second one is paraconsistent and the third is paracomplete. Despite being non-normal, these systems are sound and complete for a suitable Kripke semantics. We also show that these systems are appropriate for interpreting □ as “is provable in classical logic”. This allows us to recover the theorems of propositional classical logic within three sub-classical modal systems.

Monomodal logic has exactly two maximally normal logics, which are also the only quasi-normal logics that are Post complete, and they are complete for validity in Kripke frames. Here we show that addition of a propositional constant to monomodal logic allows the construction of continuum many maximally normal logics that are not valid in any Kripke frame, or even in any complete modal algebra. We also construct continuum many quasi-normal Post complete logics that are not normal. The set of extensions of S4.3 is radically altered by the addition of a constant: we use it to construct continuum many such normal extensions of S4.3, and continuum many non-normal ones, none of which have the finite model property. But for logics with weakly transitive frames there are only eight maximally normal ones, of which five extend K4 and three extend S4.

Solovay proved the arithmetical completeness theorem for the system GL of propositional modal logic of provability. Montagna proved that this completeness does not hold for a natural extension QGL of GL to the predicate modal logic. Let Th(QGL) be the set of all theorems of QGL, Fr(QGL) be the set of all formulas valid in all transitive and conversely well-founded Kripke frames, and let PL(T) be the set of all predicate modal formulas provable in Tfor any arithmetical interpretation. Montagna’s results are described as Th(QGL) ⊊ (Fr(QGL), PL(PA) ⊈ Fr(QGL), and Th(QGL) ⊊ PL(PA).In this paper, we prove the following three theorems: (1) Fr(QGL) ⊈ PL(T) for any Σ1-sound recursively enumerable extension T of I Σ1, (2) PL(T) ⊈ Fr(QGL) for any recursively enumerable A-theory T extending I Σ1, and (3) Th(QGL) ⊊ Fr(QGL) ∩ PL(T) for any recursively enumerable A-theory T extending I Σ2.To prove these theorems, we use iterated consistency assertions and nonstandard models of arithmetic, and we improve Artemov’s lemma which is used to prove Vardanyan’s theorem on the Π02-completeness of PL(T).

In our paper we investigate the possibilities of modal logics in coalgebras of program systems. We deal with a simplified model of an intrusion detection system. We model an intrusion detection system as a coalgebra and construct its Kripke model of coalgebraic modal linear logic using powerset endofunctor. In this model we present our idea how a fragment of epistemic linear logic can provide knowledge and belief of intrusion attempt.

It has been argued that a combination of game-theoretic semantics and independence-friendly (IF) languages can provide a novel approach to the conceptual foundations of mathematics and the sciences. I introduce and motivate an IF first-order modal language endowed with a game-theoretic semantics of perfect information. The resulting interpretive independence-friendly logic (IIF) allows to formulate some basic model-theoretic notions that are inexpressible in the ordinary quantified modal logic. Moreover, I argue that some key concepts of Kripke’s new theory of reference are adequately modeled within IIF. Finally, I compare the logic IIF to David Lewis counterpart theory, drawing some morals concerning the interrelation between metaphysical and semantic issues in possible-world semantics.

In this chapter the author gives completeness theorems for some basic reactive Kripke models and semantics.

It is well known that rough set-based approximations of concepts and possible world semantics of modal logics are closely related. In this chapter, we review the relationships between two types of possible world semantic models, i.e., Kripke model and measure-based model, and two variation of rough sets, i.e., Pawlak’s rough set and variable precision rough set.

It is observed that a consistent congruential modal logic is not guaranteed to have a consistent extension in which the Box operator becomes a truth-functional connective for one of the four one-place (two-valued) truth functions.

We describe how we machine-checked the admissibility of the standard structural rules of weakening, contraction and cut for multiset-based sequent calculi for the unimodal logics S4, S4.3 and K4De, as well as for the bimodal logic \(\mathrm {S4C}\) recently investigated by Mints. Our proofs for both S4 and S4.3 appear to be new while our proof for \(\mathrm {S4C}\) is different from that originally presented by Mints, and appears to avoid the complications he encountered. The paper is intended to be an overview of how to machine-check proof theory for readers with a good understanding of proof theory.

We extend unified correspondence theory to Kripke frames with impossible worlds and their associated regular modal logics. These are logics the modal connectives of which are not required to be normal: only the weaker properties of additivity ◊x∨◊y=◊(x∨y) and multiplicativity □x∧□y=□(x∧y) are required. Conceptually, it has been argued that their lacking necessitation makes regular modal logics better suited than normal modal logics at the formalization of epistemic and deontic settings. From a technical viewpoint, regularity proves to be very natural and adequate for the treatment of algebraic canonicity Jónsson-style. Indeed, additivity and multiplicativity turn out to be key to extend Jónsson’s original proof of canonicity to the full Sahlqvist class of certain regular distributive modal logics naturally generalizing distributive modal logic. Most interestingly, additivity and multiplicativity are key to Jónsson-style canonicity also in the original (i.e. normal DML. Our contributions include: the definition of Sahlqvist inequalities for regular modal logics on a distributive lattice propositional base; the proof of their canonicity following Jónsson’s strategy; the adaptation of the algorithm ALBA to the setting of regular modal logics on two non-classical (distributive lattice and intuitionistic) bases; the proof that the adapted ALBA is guaranteed to succeed on a syntactically defined class which properly includes the Sahlqvist one; finally, the application of the previous results so as to obtain proofs, alternative to Kripke’s, of the strong completeness of Lemmon’s epistemic logics E2-E5 with respect to elementary classes of Kripke frames with impossible worlds.

The majority of works on modal fuzzy logics consider Kripke-style possible worlds semantics as the principal semantics despite its well known axiomatizability issues when considering fuzzy accessibility relations. The present work offers the first (two) steps towards exploring a more general semantical picture, namely a fuzzified version of the classical neighborhood semantics. First we prove the fuzzy version of the classical relationship between Kripke and neighborhood semantics. Second, for any axiomatic extension of MTL (one of the main fuzzy logics), we define its modal expansion by a \(\Box \)-like modality, and, in the presence of some additional conditions, we prove that the resulting logic can be axiomatized by adding the \({\mathrm {(E)}}\)-rule to the corresponding Hilbert-style calculus of the starting logic.

Modal logic is a paradigm for several useful and applicable formal systems in computer science, and, in particular, for temporal logics of various kinds. It generally retains the low complexity of classical propositional logic, but notable exceptions exist that present higher complexity or are even undecidable. In search of computationally well-behaved fragments, clausal forms and other sub-propositional restrictions of temporal and description logics have been recently studied. It is known that the Horn fragments of the modal logics between K and S4 are PSPACE-complete, keeping the same complexity of the the full propositional versions. In this paper, inspired by similar results in the temporal case, we sharpen the above result by showing that if we allow only box modalities in the language the Horn fragments of the modal logics between K and S4 become P-complete. Exploring the innermost reasons for the tractability of sub-Horn modal logics is a necessary condition to understand the behaviour of more expressive temporal and spatial languages under similar restrictions.

Earlier algebraic semantics for Belnapian modal logics were defined in terms of twist-structures over modal algebras. In this paper we introduce the class of BK-lattices, show that this class coincides with the abstract closure of the class of twist-structures, and it forms a variety. We prove that the lattice of subvarieties of the variety of BK-lattices is dually isomorphic to the lattice of extensions of Belnapian modal logic BK. Finally, we describe invariants determining a twist-structure over a modal algebra.

Logical inferentialism claims that the meaning of the logical constants should be given, not model-theoretically, but by the rules of inference of a suitable calculus. It has been claimed that certain proof-theoretical systems, most particularly, labelled deductive systems for modal logic, are unsuitable, on the grounds that they are semantically polluted and suffer from an untoward intrusion of semantics into syntax. The charge is shown to be mistaken. It is argued on inferentialist grounds that labelled deductive systems are as syntactically pure as any formal system in which the rules define the meanings of the logical constants.

This paper extends previous work on the modal logic CK as a reference system, both proof-theoretically and model-theoretically, for a correspondence theory of constructive modal logics. First, the fundamental nature of CK is discussed and compared with the intuitionistic modal logic IK which is traditionally taken to be the base line. Then, it is shown, that CK admits of a cut-free Gentzen sequent calculus G-CK which has (i) a local interpretation in constructive Kripke models and (ii) does not require explicit world labels. Finally, the paper demonstrates how non-classical modal logics such as IK, CS4, CL, or [email protected]?s deontic system of 2-sequents arise as theories of CK, presented both as special rules and as frame classes.

Coalgebras can be seen as a natural abstraction of Kripke frames. In the same sense, coalgebraic logics are generalised modal logics. In this paper, we give an overview of the basic tools, techniques and results that connect coalgebras and modal logic. We argue that coalgebras unify the semantics of a large range of different modal logics (such as probabilistic, graded, relational, conditional) and discuss unifying approaches to reasoning at this level of generality. We review languages defined in terms of the so-called cover modality, languages induced by predicate liftings as well as their common categorical abstraction, and present (abstract) results on completeness, expressiveness and complexity in these settings, both for basic languages as well as a number of extensions, such as hybrid languages and fixpoints. © 2011 Published by Elsevier B.V.