Search

The fragment of the language of modal logic that consists of all implications A → B, where A and B are built from variables, the constant ⊤ (truth), and the connectives ∧ and ◊1,◊2,...,◊m. For the polymodal logic S5m (the logic of m equivalence relations) and the logic K4.3 (the logic of irreflexive linear orders), an axiomatization of such fragments is found and their algorithmic decidability in polynomial time is proved. [ABSTRACT FROM AUTHOR]

Model checking is a powerful method widely explored in formal verification. Given a model of a system, e.g., a Kripke structure, and a formula specifying its expected behaviour, one can verify whether the system meets the behaviour by checking the formula against the model. Classically, system behaviour is expressed by a formula of a temporal logic, such as LTL and the like. These logics are 'point-wise' interpreted, as they describe how the system evolves state-by-state. However, there are relevant properties, such as those constraining the temporal relations between pairs of temporally extended events or involving temporal aggregations, which are inherently 'interval-based', and thus asking for an interval temporal logic. In this paper, we give a formalization of the model checking problem in an interval logic setting. First, we provide an interpretation of formulas of Halpern and Shoham's interval temporal logic HS over finite Kripke structures, which allows one to check interval properties of computations. Then, we prove that the model checking problem for HS against finite Kripke structures is decidable by a suitable small model theorem, and we provide a lower bound to its computational complexity. [ABSTRACT FROM AUTHOR]

A number of algorithms for computing the simulation preorder (and equivalence) on Kripke structures are available. Let $$\varSigma $$ denote the state space, $${\rightarrow }$$ the transition relation and $$P_{\mathrm {sim}}$$ the partition of $$\varSigma $$ induced by simulation equivalence. While some algorithms are designed to reach the best space bounds, whose dominating additive term is $$|P_{\mathrm {sim}}|^2$$ , other algorithms are devised to attain the best time complexity $$O(|P_{\mathrm {sim}}||{\rightarrow }|)$$ . We present a novel simulation algorithm which is both space and time efficient: it runs in $$O(|P_ {\mathrm {sim}}|^2 \log |P_{\mathrm {sim}}| + |\varSigma |\log |\varSigma |)$$ space and $$O(|P_{\mathrm {sim}}||{\rightarrow }|\log |\varSigma |)$$ time. Our simulation algorithm thus reaches the best space bounds while closely approaching the best time complexity. [ABSTRACT FROM AUTHOR]

In this paper we investigate Kripke models, used to model knowledge or belief in a static situation, and action models, used to model communicative actions that change this knowledge or belief. The appropriate notion for structural equivalence between modal structures such as Kripke models is bisimulation: Kripke models that are bisimilar are modally equivalent. We would like to find a structural relation that can play the same role for the action models that play a prominent role in information updating. Two action models are equivalent if they yield the same results when updating Kripke models. More precisely, two action models are equivalent if it holds for all Kripke models that the result of updating with one action model is bisimilar to the result of updating with the other action model. We propose a new notion of action emulation that characterizes the structural equivalence of the important class of canonical action models. Since every action model has an equivalent canonical action model, this gives a method to decide the equivalence of any pair of action models. We also give a partial result that holds for the class of all action models. Our results extend the work in van Eijck et al. (Synthese 185(1):131–151, 2012 ). [ABSTRACT FROM AUTHOR]

The present work is motivated by two questions. (1) What should an intuitionistic epistemic logic look like? (2) How should one interpret the knowledge operator in a Kripke-model for it? In what follows we outline an answer to (2) and give a model-theoretic definition of the operator K. This will shed some light also on (1), since it turns out that K, defined as we do, fulfills the properties of a necessity operator for a normal modal logic. The interest of our construction also lies in a better insight into the intuitionistic solution to Fitch's paradox, which is discussed in the third section. In particular we examine, in the light of our definition, DeVidi and Solomon's proposal of formulating the verification thesis as $\phi \rightarrow \neg \neg K\phi$. We show, as our main result, that this definition excapes the paradox, though it is validated only under restrictive conditions on the models. [ABSTRACT FROM AUTHOR]

The fragment of the polymodal provability logic GLP in the language with connectives ┬, Λ, and 〈 n〉 for all n ∈ ω is considered. For this fragment, a deductive system is constructed, a Kripke semantics is proposed, and a polynomial bound for the complexity of a decision procedure is obtained. [ABSTRACT FROM AUTHOR]

The standard Kripkean semantic theories for quantified modal logic allow the individuals that exist at other worlds to vary from those that exist at the actual world. This causes a problem for those who deny the existence of non-actual individuals. I focus on two prominent strategies for solving this problem, due respectively to Bernard Linsky and Edward Zalta (who identify the possible individuals with the actual individuals) and Alvin Plantinga (who identifies the possible individuals with the individual essences). I argue, contra various commentators, that both of these solutions are acceptable by the lights of those who deny the existence of mere possibilia. [ABSTRACT FROM AUTHOR]

Standard Kripke models are inadequate to model situations of inexact knowledge with introspection, since positive and negative introspection force the relation of epistemic indiscernibility to be transitive and euclidean. Correlatively, Williamson’s margin for error semantics for inexact knowledge invalidates axioms 4 and 5. We present a new semantics for modal logic which is shown to be complete for K45, without constraining the accessibility relation to be transitive or euclidean. The semantics corresponds to a system of modular knowledge, in which iterated modalities and simple modalities are not on a par. We show how the semantics helps to solve Williamson’s luminosity paradox, and argue that it corresponds to an integrated model of perceptual and introspective knowledge that is psychologically more plausible than the one defended by Williamson. We formulate a generalized version of the semantics, called token semantics, in which modalities are iteration-sensitive up to degree n and insensitive beyond n. The multi-agent version of the semantics yields a resource-sensitive logic with implications for the representation of common knowledge in situations of bounded rationality. [ABSTRACT FROM AUTHOR]

By introducing the intensional mappings and their properties, we establish a new semantical approach of characterizing intermediate logics. First prove that this new approach provides a general method of characterizing and comparing logics without changing the semantical interpretation of implication connective. Then show that it is adequate to characterize all Kripke_complete intermediate logics by showing that each of these logics is sound and complete with respect to its (unique) ‘weakest characterization property’ of intensional mappings. In particular, we show that classical logic has the weakest characterization property $$cl$$ , which is the strongest among all possible weakest characterization properties of intermediate logics. Finally, it follows from this result that a translation is an embedding of classical logic into intuitionistic logic, iff. its semantical counterpart has the property $$cl$$ . [ABSTRACT FROM AUTHOR]

Several philosophers—including C. S. Peirce, William James, Hilary Putnam and Crispin Wright—have proposed various versions of the notion that truth is an epistemic ideal. More specifically, they have held that a proposition is true if and only if it can be fixedly warranted by human inquirers, given certain ideal epistemic conditions. This paper offers a general critique of that idea, modeling conceptions of ideality and fixed warrant within the semantics that Kripke developed for intuitionistic logic. It is shown that each of the two plausible notions of fixed warrant faces difficulties and that, moreover, “truth” defined in terms of either of them is distressingly dependent upon one’s conception of idealized inquiry and perhaps also upon one’s standards of warrant. [ABSTRACT FROM AUTHOR]

Intervals in boolean algebras enter into the study of conditional assertions (or events) in two ways: directly, either from intuitive arguments or from Goodman, Nguyen and Walker's representation theorem, as suitable mathematical entities to bear conditional probabilities, or indirectly, via a representation theorem for the family of algebras associated with de Finetti's three-valued logic of conditional assertions/events. Further representation theorems forge a connection with rough sets. The representation theorems and an equivalent of the boolean prime ideal theorem yield an algebraic completeness theorem for the three-valued logic. This in turn leads to a Henkin-style completeness theorem. Adequacy with respect to a family of Kripke models for de Finetti's logic, Lukasiewicz's three-valued logic and Priest's Logic of Paradox is demonstrated. The extension to first-order yields a short proof of adequacy for Körner's logic of inexact predicates. [ABSTRACT FROM AUTHOR]

We define dual and symmetric combinatory calculi (inequational and equational ones), and prove their consistency. Then, we introduce algebraic and set theoretical – relational and operational – semantics, and prove soundness and completeness. We analyze the relationship between these logics, and argue that inequational dual logics are the best suited to model computation. [ABSTRACT FROM AUTHOR]

The concept of quantum logic is extended so that it covers a more general set of propositions that involve non-trivial probabilities. This structure is shown to be embedded into a multi-modal framework, which has desirable logical properties such as an axiomatization, the finite model property and decidability. [ABSTRACT FROM AUTHOR]