Complete Axiomatizations for Reasoning about Knowledge and Branching Time

Sound and complete axiomatizations are provided for a number of different logics involving modalities for the knowledge of multiple agents and operators for branching time, extending previous work of Halpern, van der Meyden and Vardi [to appear, SIAM Journal on Computing] for logics of knowledge and linear time. The paper considers the system constraints of synchrony, perfect recall and unique initial states, which give rise to interaction axioms. The language is based on the temporal logic CTL*, interpreted with respect to a version of the bundle semantics.     

Combinations of tense and deontic modality: On the approach to temporal logic with historical necessity and conditional obligation

We consider three infinite hierarchies of what I call “two-dimensional temporal logics with explicit realization operators”, viz. (i) one without historical or deontic modalities, (ii) one with historical but without deontic modalities, and (iii) one with historical and with dyadic deontic modalities for conditional obligation and permission. Sound and complete axiomatizations are obtained for all three hierarchies relative to a simplified version of the finite co-ordinate-system semantics given for so-called T × W logic of historical necessity in [L. Åqvist, The logic of historical necessity as founded on two-dimensional modal tense logic, J. Philos. Logic 28 (1999) 329–369].     

Kripke Semantics, Undecidability and Standard Completeness for Esteva and Godo's Logic MTL∀

The present paper deals with the predicate version MTL of the logic MTL by Esteva and Godo. We introduce a Kripke semantics for it, along the lines of Ono's Kripke semantics for the predicate version of FL_ew (cf. [O85]), and we prove a completeness theorem. Then we prove that every predicate logic between MTL and classical predicate logic is undecidable. Finally, we prove that MTL is complete with respect to the standard semantics, i.e., with respect to Kripke frames on the real interval [0,1], or equivalently, with respect to MTL-algebras whose lattice reduct is [0,1] with the usual order.     

Term-Modal Logics

Many powerful logics exist today for reasoning about multi-agent systems, but in most of these it is hard to reason about an infinite or indeterminate number of agents. Also the naming schemes used in the logics often lack expressiveness to name agents in an intuitive way.To obtain a more expressive language for multi-agent reasoning and a better naming scheme for agents, we introduce a family of logics called term-modal logics. A main feature of our logics is the use of modal operators indexed by the terms of the logics. Thus, one can quantify over variables occurring in modal operators. In term-modal logics agents can be represented by terms, and knowledge of agents is expressed with formulas within the scope of modal operators.This gives us a flexible and uniform language for reasoning about the agents themselves and their knowledge. This article gives examples of the expressiveness of the languages and provides sequent-style and tableau-based proof systems for the logics. Furthermore we give proofs of soundness and completeness with respect to the possible world semantics.     

Pure Extensions, Proof Rules, and Hybrid Axiomatics

In this paper we argue that hybrid logic is the deductive setting most natural for Kripke semantics. We do so by investigating hybrid axiomatics for a variety of systems, ranging from the basic hybrid language (a decidable system with the same complexity as orthodox propositional modal logic) to the strong Priorean language (which offers full first-order expressivity).We show that hybrid logic offers a genuinely first-order perspective on Kripke semantics: it is possible to define base logics which extend automatically to a wide variety of frame classes and to prove completeness using the Henkin method. In the weaker languages, this requires the use of non-orthodox rules. We discuss these rules in detail and prove non-eliminability and eliminability results. We also show how another type of rule, which reflects the structure of the strong Priorean language, can be employed to give an even wider coverage of frame classes. We show that this deductive apparatus gets progressively simpler as we work our way up the expressivity hierarchy, and conclude the paper by showing that the approach transfers to first-order hybrid logic.A preliminary version of this paper was presented at the fifth conference on Advances in Modal Logic (AiML 2004) in Manchester. We would like to thank Maarten Marx for his comments on an early draft and Agnieszka Kisielewska for help with the proof reading.Special Issue Ways of Worlds II. On Possible Worlds and Related Notions Edited by Vincent F. Hendricks and Stig Andur Pedersen     

线性时态逻辑的决策问题复杂性

不同的时态逻辑能够适应不同的推理任务。为了符合应用,关于时间的模型从离散的自然数和整数,延伸到稠密的线性实数,甚至扩展到区间代数和树代数。如果简单的时态连接词的表达力已经足够,就只需使用这些简单的时态连接词来构造的时态逻辑。在能够承担降低运算速度的风险下,我们可以为实现更强的表达力而使用更多的连接词,也可以加上度量信息或者固定点。作者近期提出了一个令人惊讶的结论:建立在实数时间上的具有足够表达力的语言和基于自然数离散时间流的传统简单算子,它们推理的计算复杂性是一样的。在这篇论文中,作者试图对建立在标准时态连接词和线性时间流的普通类上的时态逻辑中所有决策问题的计算复杂性作新的说明。尤其是,文中指出,所有标准逻辑在PSPACE中都存在决策问题。     

内涵与外延之辩:基于含糊性语义解释演进的分析

在含糊性问题研究领域,多值语义解释和超赋值语义解释是两个经典的研究进路。相较多值语义中的经典三值解释和基于概率赋值的模糊逻辑解释,范启德(1975)给出的超赋值语义由于引入了基于可能世界语义的可精确化结构,具有更强的表达力,能够弥补三值和模糊逻辑处理的很多不足。距离超赋值语义发表40余年后,秋叶研(2017)给出了同样满足可精确化结构条件的一个布尔多值解释。由于超赋值语义一直被当作典型的内涵语义处理方式,而在含糊性问题研究领域,布尔多值方法却在大多数时候被认为是模糊逻辑这个基于概率处理的典型的外延语义的复杂版本,内涵语义与外延语义的殊途同归,非常值得仔细思考和探究。本文将结合含糊性问题研究领域的多值语义解释和超赋值语义解释的演进过程,以内涵语义和外延语义的区分为切入点,最终指出,(当下主流定义下的)内涵语义与外延语义的界限是模糊的,而在原有界定基础上,对内涵语义增加“内涵语义要可以表达非线序的偏序结构”这一限制,能够进一步对内涵语义和外延语义进行区分。     

Complexity Results of STIT Fragments

We provide a Kripke semantics for a STIT logic with the ??next?? operator. As the atemporal group STIT is undecidable and unaxiomatizable, we are interested in strict fragments of atemporal group STIT. First we prove that the satisfiability problem of a formula of the fragment made up of individual coalitions plus the grand coalition is also NEXPTIME-complete. We then generalize this result to a fragment where coalitions are in a given lattice. We also prove that if we restrict the language to nested coalitions the satisfiability problem is NP-complete if the number of agents is fixed and PSPACEcomplete if the number of agents is variable. Finally we embed individual STIT with the ??next?? operator into a fragment of atemporal group STIT.     

Game Logic - An Overview

Game Logic is a modal logic which extends Propositional Dynamic Logic by generalising its semantics and adding a new operator to the language. The logic can be used to reason about determined 2-player games. We present an overview of meta-theoretic results regarding this logic, also covering the algebraic version of the logic known as Game Algebra.     

Fibred Security Language

We study access control policies based on the says operator by introducing a logical framework called Fibred Security Language (FSL) which is able to deal with features like joint responsibility between sets of principals and to identify them by means of first-order formulas. FSL is based on a multimodal logic methodology. We first discuss the main contributions from the expressiveness point of view, we give semantics for the language both for classical and intuitionistic fragment), we then prove that in order to express well-known properties like ‘speaks-for’ or ‘hand-off’, defined in terms of says, we do not need second-order logic (unlike previous approaches) but a decidable fragment of first-order logic suffices. We propose a model-driven study of the says axiomatization by constraining the Kripke models in order to respect desirable security properties, we study how existing access control logics can be translated into FSL and we give completeness for the logic.     

Improving the semantics of the Software Cost Reduction method

Although the Software Cost Reduction (SCR) method has been successfully used in many projects and organizations to specify software requirements, surprisingly, its semantics is not well defined. The symbols used in this method are ambiguous, especially those that serve to denote SCR events. The aim of this work is to address this ambiguity and improve the SCR semantics by enabling events in first-order logic via two symbols pred and succ. This slight extension of first-order logic allows us to increase the readability of the SCR tables, eliminate their ambiguous semantics, facilitate the verification and validation process, and improve the toolset supporting the SCR method, just to name a few. Moreover, our extension is simple and avoids the complexity of temporal logic.     

Three-Valued Temporal Logic <Emphasis Type="Italic">Q</Emphasis><Subscript><Emphasis Type="Italic">t</Emphasis></Subscript> and Future Contingents

Prior’s three-valued modal logic Q was developed as a philosophically interesting modal logic. Thus, we should be able to modify Q as a temporal logic. Although a temporal version of Q was suggested by Prior, the subject has not been fully explored in the literature. In this paper, we develop a three-valued temporal logic Q _t and give its axiomatization and semantics. We also argue that Q _t provides a smooth solution to the problem of future contingents. Presented by Daniele Mundici     

The Decision Problem of Modal Product Logics with a Diagonal,and Faulty Counter Machines

In the propositional modal (and algebraic) treatment of two-variable first-order logic equality is modelled by a ‘diagonal’ constant, interpreted in square products of universal frames as the identity (also known as the ‘diagonal’) relation. Here we study the decision problem of products of two arbitrary modal logics equipped with such a diagonal. As the presence or absence of equality in two-variable first-order logic does not influence the complexity of its satisfiability problem, one might expect that adding a diagonal to product logics in general is similarly harmless. We show that this is far from being the case, and there can be quite a big jump in complexity, even from decidable to the highly undecidable. Our undecidable logics can also be viewed as new fragments of first-order logic where adding equality changes a decidable fragment to undecidable. We prove our results by a novel application of counter machine problems. While our formalism apparently cannot force reliable counter machine computations directly, the presence of a unique diagonal in the models makes it possible to encode both lossy and insertion-error computations, for the same sequence of instructions. We show that, given such a pair of faulty computations, it is then possible to reconstruct a reliable run from them.     

Semantics for existential graphs

This paper examines Charles Peirce's graphical notation for first-order logic with identity. The notation forms a part of his system of existential graphs, which Peirce considered to be his best work in logic. In this paper a Tarskian semantics is provided for the graphical system.     

Competitive equilibrium with intuitionistic agents

This paper studies an economy whose agents perceive their consumption possibilities subjectively, and whose preferences are defined on what they subjectively experience, rather than on those alternatives that are objectively present. The model of agents’ perceptions is based on intuitionistic logic. Roughly, this means that agents reason constructively: a solution to a problem exists only if there is a construction by which the problem can be solved. The theorems that can be proved determine how an agent perceives a set of alternatives. A dual model relates perceived alternatives to a shared language, which the agents use in trading. So perceptions relate objective alternatives to an agent’s subjective view of them, and reporting dually relates an agent’s subjective world to a shared language. It turns out that an appropriately modified notion of competitive equilibrium always exists. However, in contrast with standard results in economic theory, competitive equilibrium need not be efficient.

     

Competitive equilibrium with intuitionistic agents

This paper studies an economy whose agents perceive their consumption possibilities subjectively, and whose preferences are defined on what they subjectively experience, rather than on those alternatives that are objectively present. The model of agents’ perceptions is based on intuitionistic logic. Roughly, this means that agents reason constructively: a solution to a problem exists only if there is a construction by which the problem can be solved. The theorems that can be proved determine how an agent perceives a set of alternatives. A dual model relates perceived alternatives to a shared language, which the agents use in trading. So perceptions relate objective alternatives to an agent’s subjective view of them, and reporting dually relates an agent’s subjective world to a shared language. It turns out that an appropriately modified notion of competitive equilibrium always exists. However, in contrast with standard results in economic theory, competitive equilibrium need not be efficient.