Kripke Semantics for Modal Substructural Logics

We introduce Kripke semantics for modal substructural logics, and provethe completeness theorems with respect to the semantics. Thecompleteness theorems are proved using an extended Ishihara's method ofcanonical model construction (Ishihara, 2000). The framework presentedcan deal with a broad range of modal substructural logics, including afragment of modal intuitionistic linear logic, and modal versions ofCorsi's logics, Visser's logic, Méndez's logics and relevant logics.     

Resource bisimilarity and graded bisimilarity coincide

Resource bisimilarity has been proposed in the literature on concurrency theory as a notion of bisimilarity over labeled transition systems that takes into account the number of choices that a system has. Independently, g-bisimilarity has been defined over Kripke models as a suitable notion of bisimilarity for graded modal logic. This note shows that these two notions of bisimilarity coincide over image-finite Kripke frames.     

Logics for Classes of Boolean Monoids

This paper presents the algebraic and Kripke modelsoundness and completeness ofa logic over Boolean monoids. An additional axiom added to thelogic will cause the resulting monoid models to be representable as monoidsof relations. A star operator, interpreted as reflexive, transitiveclosure, is conservatively added to the logic. The star operator isa relative modal operator, i.e., one that is defined in terms ofanother modal operator. A further example, relative possibility,of this type of operator is given. A separate axiom,antilogism, added to the logic causes the Kripke models to support acollection of abstract topological uniformities which become concretewhen the Kripke models are dual to monoids of relations. The machineryfor the star operator is shownto be a recasting of Scott-Montague neighborhood models. An interpretationof the Kripke frames and properties thereof is presented in terms ofcertain CMOS transister networks and some circuit transformation equivalences.The worlds of the Kripke frame are wires and the Kripke relation is a specializedCMOS pass transistor network.     

Preferential Accessibility and Preferred Worlds

Modal accounts of normality in non-monotonic reasoning traditionally have an underlying semantics based on a notion of preference amongst worlds. In this paper, we motivate and investigate an alternative semantics, based on ordered accessibility relations in Kripke frames. The underlying intuition is that some world tuples may be seen as more normal, while others may be seen as more exceptional. We show that this delivers an elegant and intuitive semantic construction, which gives a new perspective on defeasible necessity. Technically, the revisited logic does not change the expressive power of our previously defined preferential modalities. This conclusion follows from an analysis of both semantic constructions via a generalisation of bisimulations to the preferential case. Reasoners based on the previous semantics therefore also suffice for reasoning over the new semantics. We complete the picture by investigating different notions of defeasible conditionals in modal logic that can also be captured within our framework.     

Hybridizing a Logical Framework

Logical connectives familiar from the study of hybrid logic can be added to the logical framework LF, a constructive type theory of dependent functions. This extension turns out to be an attractively simple one, and maintains all the usual theoretical and algorithmic properties, for example decidability of type-checking. Moreover it results in a rich metalanguage for encoding and reasoning about a range of resource-sensitive substructural logics, analagous to the use of LF as a metalanguage for more ordinary logics.This family of applications of the language, contrary perhaps to expectations of how hybridized systems are typically used, does not require the usual modal connectives box and diamond, nor any internalization of a Kripke accessibility relation. It does, however, make essential use of distinctively hybrid connectives: universal quantifiation over worlds, truth of a proposition at a named world, and local binding of the current world. This supports the claim that the innovations of hybrid logic have independent value even apart from their traditional relationship to temporal and alethic modal logics.     

On open‐set lattices and some of their applications in semantics

In this article, we present the theory of Kripke semantics, along with the mathematical framework and applications of Kripke semantics. We take the Kripke‐Sato approach to define the knowledge operator in relation to Hintikka's possible worlds model, which is an application of the semantics of intuitionistic logic and modal logic. The applications are interesting from the viewpoint of agent interactives and process interaction. We propose (i) an application of possible worlds semantics, which enables the evaluation of the truth value of a conditional sentence without explicitly defining the operator “→” (implication), through clustering on the space of events (worlds) using the notion of neighborhood; and (ii) a semantical approach to treat discrete dynamic process using Kripke‐Beth semantics. Starting from the topological approach, we define the measure‐theoretical machinery, in particular, we adopt the methods developed in stochastic process—mainly the martingale—to our semantics; this involves some Boolean algebraic (BA) manipulations. The clustering on the space of events (worlds), using the notion of neighborhood, enables us to define an accessibility relation that is necessary for the evaluation of the conditional sentence. Our approach is by taking the neighborhood as an open set and looking at topological properties using metric space, in particular, the so‐called ε‐ball; then, we can perform the implication by computing Euclidean distance, whenever we introduce a certain enumerative scheme to transform the semantic objects into mathematical objects. Thus, this method provides an approach to quantify semantic notions. Combining with modal operators K_i operating on E set, it provides a more‐computable way to recognize the “indistinguishability” in some applications, e.g., electronic catalogue. Because semantics used in this context is a local matter, we also propose the application of sheaf theory for passing local information to global information. By looking at Kripke interpretation as a function with values in an open‐set lattice ??_U, which is formed by stepwise verification process, we obtain a topological space structure. Now, using the measure‐theoretical approach by taking the Borel set and Borel function in defining measurable functions, this can be extended to treat the dynamical aspect of processes; from the stochastic process, considered as a family of random variables over a measure space (the probability space triple), we draw two strong parallels between Kripke semantics and stochastic process (mainly martingales): first, the strong affinity of Kripke‐Beth path semantics and time path of the process; and second, the treatment of time as parametrization to the dynamic process using the technique of filtration, adapted process, and progressive process. The technique provides very effective manipulation of BA in the form of random variables and σ‐subalgebra under the cover of measurable functions. This enables us to adopt the computational algorithms obtained for stochastic processes to path semantics. Besides, using the technique of measurable functions, we indeed obtain an intrinsic way to introduce the notion of time sequence. © 2003 Wiley Periodicals, Inc.     

A Cut-Free Gentzen Formulation of Basic Propositional Calculus

We introduce a Gentzen style formulation of Basic Propositional Calculus(BPC), the logic that is interpreted in Kripke models similarly tointuitionistic logic except that the accessibility relation of eachmodel is not necessarily reflexive. The formulation is presented as adual-context style system, in which the left hand side of a sequent isdivided into two parts. Giving an interpretation of the sequents inKripke models, we show the soundness and completeness of the system withrespect to the class of Kripke models. The cut-elimination theorem isproved in a syntactic way by modifying Gentzen's method. Thisdual-context style system exemplifies the effectiveness of dual-contextformulation in formalizing various non-classical logics.     

A FRAMEWORK FOR LOGICS OF EXPLICIT BELIEF

The epistemic notions of knowledge and belief have most commonly been modeled by means of possible worlds semantics. In such approaches an agent knows (or believes) all logical consequences of its beliefs. Consequently, several approaches have been proposed to model systems of explicit belief, more suited to modeling finite agents or computers. In this paper a general framework is developed for the specification of logics of explicit belief. A generalization of possible worlds, called situations, is adopted. However the notion of an accessibility relation is not employed; instead a sentence is believed if the explicit proposition expressed by the sentence appears among a set of propositions associated with an agent at a situation. Since explicit propositions may be taken as corresponding to "belief contexts" or "frames of mind," the framework also provides a setting for investigating such approaches to belief. The approach provides a uniform and flexible basis from which various issues of explicit belief may be addressed and from which systems may be contrasted and compared. A family of logics is developed using this framework, which extends previous approaches and addresses issues raised by these earlier approaches. The more interesting of these logics are tractable, in that determining if a belief follows from a set of beliefs, given certain assumptions, can be accomplished in polynomial time.     

Knowledge structure approach to verification of authentication protocols

~~Knowledge structure approach to verification of authentication protocols1. Hintikka, J., Knowledge and Belief, Ithaca, NY. Cornell University Press, 1962. 2. Fagin, R., Halpern, J., Moses, Y. et al.,Reasoning About Knowledge, Cambridge, MA. MIT Press, 1995. 3. Halpern, I., Zuck, L., A little knowledge goes a long way. Simple knowledge based derivations and correctness proofs for a family of protocols. Journal of the ACM, 1992, 39(3): 449-478. 4. Stulp, F., Verbrugge, …     

Conceptual modeling in full computation‐tree logic with sequence modal operator

In this paper, we propose a method for modeling concepts in full computation‐tree logic with sequence modal operators. An extended full computation‐tree logic, CTLS*, is introduced as a Kripke semantics with a sequence modal operator. This logic can appropriately represent hierarchical tree structures in cases where sequence modal operators in CTLS* are applied to tree structures. We prove a theorem for embedding CTLS* into CTL*. The validity, satisfiability, and model‐checking problems of CTLS* are shown to be decidable. An illustrative example of biological taxonomy is presented using CTLS* formulas. © 2011 Wiley Periodicals, Inc.     

模态转移系统的三值逻辑模型检验

分析了现有的模型检验技术应用于模态转移系统的三值逻辑公式的模型检验中存在的问题.提出了把模态转移系统转换成Kripke结构的算法以及三值逻辑公式转换成2个二值逻辑的算法,经过转换后可用现有的模型检验技术进行模型检验.用该算法转换后,状态数、转移数和原子命题数目与原模型呈线性关系,没有增加模型检验的复杂度.     

Coalgebraic semantics of modal logics: An overview

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.     

The Dynamification of Modal Dependence Logic

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.     

Applying model-checking to solve queries on semistructured data

The large volume and nature of data available to the casual users and programs motivate the increasing interest of the database community in studying flexible and efficient techniques for extracting and querying semistructured data. On the other hand, efficient methods have been discovered for solving the so-called model-checking problem for some modal logics. The aim of this paper is to show how some of these methods can be used for querying semistructured data. For doing that we show that semistructured data can be naturally seen as Kripke Transition Systems. To keep the presentation independent of a specific language, we introduce a graphical query language that includes some of the features of the query languages based on graphs and patterns. We show how to associate CTL formulas to queries of this language. This allows us to see the problems of solving a query as an instance of the model-checking problem for CTL that can be solved in polynomial time. We have tested the method by using a model-checker, and have studied the applicability of the method to some existing languages for semistructured databases.     

Existential rigidity and many modalities in order-sorted logic

Order-sorted logic is a useful tool for knowledge representation and reasoning because it enables representation of sorted terms and formulas along with partially ordered sorts (called sort-hierarchy). However, this logic cannot represent more complex sorted expressions when they are true in any possible world (as rigid) or some possible worlds (as modality) such as time, space, belief, or situation. In this study, we extend order-sorted logic by introducing existential rigidity and many modalities. In the extended logic, sorted modal formulas are interpreted over the Cartesian product of sets of possible worlds. We present a new labeled tableau calculus to check the (un)satisfiability and validity of sorted modal formulas.     

A rational reconstruction of the domain of feature structures

Feature structures are employed in various forms in many areas of linguistics. Informally, one can picture a feature structure as a sort of tree decorated with information about constraints requiring that specific subtrees be identical (isomorphic). Here I show that this informal picture of feature structures can be used to characterize exactly the class of feature structures under their usual subsumption ordering. Furthermore, once a precise definition of tree is fixed, this characterization makes use only of standard domain-theoretic notions regarding the information borne by elements in a domain, thus removing (or better, explaining) all apparentlyad hoc choices in the original definition of feature structures. In addition, I show how this characterization can be parameterized in order to yield similar characterizations of various different notions of feature structure, including acyclic structures, structures with appropriateness conditions and structures with apartness conditions (used to model path inequations). The generalizations to other notions of feature structure also emphasize that the construction given here is in fact independent of the application to feature structures.This research has been supported by the Deutsche Forschungsgemeinschaft as part of Sonderforschungsbereich 314, Projekt N3.     

A modular approach to defining and characterising notions of simulation

We propose a modular approach to defining notions of simulation, and modal logics which characterise them. We use coalgebras to model state-based systems, relators to define notions of simulation for such systems, and inductive techniques to define the syntax and semantics of modal logics for coalgebras. We show that the expressiveness of an inductively defined logic for coalgebras w.r.t. a notion of simulation follows from an expressivity condition involving one step in the definition of the logic, and the relator inducing that notion of simulation. Moreover, we show that notions of simulation and associated characterising logics for increasingly complex system types can be derived by lifting the operations used to combine system types, to a relational level as well as to a logical level. We use these results to obtain Baltag’s logic for coalgebraic simulation, as well as notions of simulation and associated logics for a large class of non-deterministic and probabilistic systems.     

Resource bisimilarity and graded bisimilarity coincide

Resource bisimilarity has been proposed in the literature on concurrency theory as a notion of bisimilarity over labeled transition systems that takes into account the number of choices that a system has. Independently, g-bisimilarity has been defined over Kripke models as a suitable notion of bisimilarity for graded modal logic. This note shows that these two notions of bisimilarity coincide over image-finite Kripke frames.     

纤维逻辑

形式逻辑已经从简单命题逻辑发展到比较复杂的模态逻辑系列。但是在主体环境下,已有逻辑的复杂性仍然不能有效刻画主体复杂的心智。有一些人工智能研究者根据主体心智的多重性,在模态逻辑中引入多种模态算子,并借此对主体加以刻画。但是原来的可能世界语义却难以容纳如此复杂的语法,出现了很多不合理的地方。本文首先介绍了新近出现的纤维逻辑（fibring logics）,然后归纳了目前将此理论应用在主体BDI建模的研究现状,最后分析纤维逻辑的不足之处,讨论了其他可能的应用,并对今后的工作做了展望。     

A study on multi-dimensional products of graphs and hybrid logics

In this work, we address some issues related to products of graphs and products of modal logics. Our main contribution is the presentation of a necessary and sufficient condition for a countable and connected graph to be a product, using a property called intransitivity. We then proceed to describe this property in a logical language. First, we show that intransitivity is not modally definable and also that no necessary and sufficient condition for a graph to be a product can be modally definable. Then, we exhibit a formula in a hybrid language that describes intransitivity. With this, we get a logical characterization of products of graphs of arbitrary dimensions. We then use this characterization to obtain two other interesting results. First, we determine that it is possible to test in polynomial time, using a model-checking algorithm, whether a finite connected graph is a product. This test has cubic complexity in the size of the graph and quadratic complexity in its number of dimensions. Finally, we use this characterization of countable connected products to provide sound and complete axiomatic systems for a large class of products of modal logics. This class contains the logics defined by product frames obtained from Kripke frames that satisfy connectivity, transitivity and symmetry plus any additional property that can be defined by a pure hybrid formula. Most sound and complete axiomatic systems presented in the literature are for products of a pair of modal logics, while we are able, using hybrid logics, to provide sound and complete axiomatizations for many products of arbitrary dimensions.