A general tableau method for propositional interval temporal logics: Theory and implementation

In this paper, we focus our attention on tableau methods for propositional interval temporal logics. These logics provide a natural framework for representing and reasoning about temporal properties in several areas of computer science. However, while various tableau methods have been developed for linear and branching time point-based temporal logics, not much work has been done on tableau methods for interval-based ones. We develop a general tableau method for Venema's CDT logic interpreted over partial orders (BCDT⁺ for short). It combines features of the classical tableau method for first-order logic with those of explicit tableau methods for modal logics with constraint label management, and it can be easily tailored to most propositional interval temporal logics proposed in the literature. We prove its soundness and completeness, and we show how it has been implemented.     

Theory matrices (for modal logics) using alphabetical monotonicity

In this paper I give conditions under which a matrix characterisation of validity is correct for first order logics where quantifications are restricted by statements from a theory. Unfortunately the usual definition of path closure in a matrix is unsuitable and a less pleasant definition must be used. I derive the matrix theorem from syntactic analysis of a suitable tableau system, but by choosing a tableau system for restricted quantification I generalise Wallen's earlier work on modal logics. The tableau system is only correct if a new condition I call alphabetical monotonicity holds. I sketch how the result can be applied to a wide range of logics such as first order variants of many standard modal logics, including non-serial modal logics.     

An analytic tableau calculus for a temporalised belief logic

A tableau is a refutation-based decision procedure for a related logic, and is among the most popular proof procedures for modal logics. In this paper, we present a labelled tableau calculus for a temporalised belief logic called TML⁺, which is obtained by adding a linear-time temporal logic onto a belief logic by the temporalisation method of Finger and Gabbay. We first establish the soundness and the completeness of the labelled tableau calculus based on the soundness and completeness results of its constituent logics. We then sketch a resolution-type proof procedure that complements the tableau calculus and also propose a model checking algorithm for TML⁺ based on the recent results for model checking procedures for temporalised logics. TML⁺ is suitable for formalising trust and agent beliefs and reasoning about their evolution for agent-based systems. Based on the logic TML⁺, the proposed labelled tableau calculus could be used for analysis, design and verification of agent-based systems operating in dynamic environments.     

Analytic Tableau Systems and Interpolation for the Modal Logics KB, KDB, K5, KD5

We give complete sequent-like tableau systems for the modal logics KB, KDB, K5, and KD5. Analytic cut rules are used to obtain the completeness. Our systems have the analytic superformula property and can thus give a decision procedure. Using the systems, we prove the Craig interpolation lemma for the mentioned logics.     

On Modal Logics Characterized by Models with Relative Accessibility Relations: Part II

This work is divided in two papers (Part I and Part II). In Part I, we introduced the class of Rare-logics for which the set of terms indexing the modal operators are hierarchized in two levels: the set of Boolean terms and the set of terms built upon the set of Boolean terms. By investigating different algebraic properties satisfied by the models of the Rare-logics, reductions for decidability were established by faithfully translating the Rare-logics into more standard modal logics (some of them contain the universal modal operator).In Part II, we push forward the results from Part I. For Rare-logics with nominals (present at the level of formulae and at the level of modal expressions), we show that the constructions from Part I can be extended although it is technically more involved. We also characterize a class of standard modal logics for which the universal modal operator can be eliminated as far as satifiability is concerned. Although the previous results have a semantic flavour, we are also able to define proof systems for Rare-logics from existing proof systems for the corresponding standard modal logics. Last, but not least, decidability results for Rare-logics are established uniformly, in particular for information logics derived from rough set theory.Since this paper is the continuation of Part I, we do not recall here the definitions of Part I although we refer to them.     

走向模型论的模态逻辑

增加特定的基数量词,扩张一阶语言,就可以导致实质性地增强语言的表达能力,这样许多超出一阶逻辑范围的数学概念就能得到处理。由于在模型的层次上基本模态逻辑可以看作一阶逻辑的互模拟不变片断,显然它不能处理这些数学概念。因此,增加说明后继状态类上基数概念的模态词,原则上我们就能以模态的方式处理所有基数。我们把讨论各种模型论逻辑的方式转移到模态方面。     

Best Unifiers in Transitive Modal Logics

This paper offers a brief analysis of the unification problem in modal transitive logics related to the logic S4: S4 itself, K4, Grz and Gödel-Löb provability logic GL. As a result, new, but not the first, algorithms for the construction of ??best?? unifiers in these logics are being proposed. The proposed algorithms are based on our earlier approach to solve in an algorithmic way the admissibility problem of inference rules for S4 and Grz. The first algorithms for the construction of ??best?? unifiers in the above mentioned logics have been given by S. Ghilardi in [16]. Both the algorithms in [16] and ours are not much computationally efficient. They have, however, an obvious significant theoretical value a portion of which seems to be the fact that they stem from two different methodological approaches.     

Process and Action: Relevant Theory and Logics

Whileprocess andaction are fundamental notions, in ubiquitous use, they lack satisfactory logical treatment in two critical respects: in analyses of the fundamentals themselves and in logical development. For what treatment they have so far received, under classical systematisation, leaves significant lacunae and induces much paradox. A relevant logical relocation, carried through in detail here, removes such problems, and provides solid ground-work for a satisfactory treatment.Firstly, as to fundamentals: processes should be explicated, so it is argued, as certain sorts of (time) directed functions (from inputs to outputs); thus they can be represented through certain ordered pairs of relations. Significant logical structures they can enter into are investigated: notably, process lattice and coupled logics, and a generalized category theory (tolerating nonassociativity of composition).Actions are types of processes, agent-ascribed process. As stock analyses of the differentia, operators and agency, through intentionality, rationality and so on, demonstrably fail, new causal analyses are proposed.Secondly, as to logical developments: for the most part, the apparently diverse offering of process and action logics to be encountered in the literature are but multiple modal logics: modal logics enriched with further functors of interesting modal sorts. Some, for example, like advertised process logics are dynamic logics (themselves basically multiple modal logics) enriched by tense logical functors, themselves modal in character. In a way that is now becoming nonstandardly standard, these modal enterprises can be reworked on relevant logical bases. A main point to such exercises resembles that of other relevant reworkings: namely, the search for correctness, for adequacy to pre-analytic and linguistic data, and therewith removal of paradoxes and anomalies that accumulate under modal analyses.Logical components from a properly expanded Humean model of action are supplied with relevant logics and semantics, in particulardoing, trying andstriving, intention andmotivation. The difficult question of formalising practical inference is then addressed.Relevant dynamic logics, paralleling modal developments, are built up piece by piece, relevant theory change is considered within a dynamic framework, and work on relevant temporal and process logics of programming cast, including functors such asbefore, during andthroughout, is initiated. The present state of logical play is assessed.I have been much encouraged in this work by Krister Segerberg, who deserves and has my considerable thanks. It will be evident that his fine investigative work, which I want to seefurthered, has served as a foil in much of what follows.     

Ground and Free-Variable Tableaux for Variants of Quantified Modal Logics

In this paper we study proof procedures for some variants of first-order modal logics, where domains may be either cumulative or freely varying and terms may be either rigid or non-rigid, local or non-local. We define both ground and free variable tableau methods, parametric with respect to the variants of the considered logics. The treatment of each variant is equally simple and is based on the annotation of functional symbols by natural numbers, conveying some semantical information on the worlds where they are meant to be interpreted.This paper is an extended version of a previous work where full proofs were not included. Proofs are in some points rather tricky and may help in understanding the reasons for some details in basic definitions.     

Coinductive models and normal forms for modal logics (or how we learned to stop worrying and love coinduction)

We present a coinductive definition of models for modal logics and show that it provides a homogeneous framework in which it is possible to include different modal languages ranging from classical modalities to operators from hybrid and memory logics. Moreover, results that had to be proved separately for each different language—but whose proofs were known to be mere routine—now can be proved in a general way. We show, for example, that we can have a unique definition of bisimulation for all these languages, and prove a single invariance-under-bisimulation theorem.We then use the new framework to investigate normal forms for modal logics. The normal form we introduce may have a smaller modal depth than the original formula, and it is inspired by global modalities like the universal modality and the satisfiability operator from hybrid logics. These modalities can be extracted from under the scope of other operators. We provide a general definition of extractable modalities and show how to compute extracted normal forms. As it is the case with other classical normal forms—e.g., the conjunctive normal form of propositional logic—the extracted normal form of a formula can be exponentially bigger than the original formula, if we require the two formulas to be equivalent. If we only require equi-satisfiability, then every modal formula has an extracted normal form which is only polynomially bigger than the original formula, and it can be computed in polynomial time.     

K Altn的另一族正规扩张

Bellissima证明KAltn的正规扩张都是典范的,并且给出了一族连续统多的无有穷模型性的逻辑,本文构造出了KAltn的另一族连续统多的正规扩张,并且证明它们与Bellissima给出的颇为不同,它们要小得多,并且都具有有穷模型性。     

Tableaus for many-valued modal logic

We continue a series of papers on a family of many-valued modal logics, a family whose Kripke semantics involves many-valued accessibility relations. Earlier papers in the series presented a motivation in terms of a multiple-expert semantics. They also proved completeness of sequent calculus formulations for the logics, formulations using a cut rule in an essential way. In this paper a novel cut-free tableau formulation is presented, and its completeness is proved.Research partly supported by NSF Grant CCR-9104015.     

The <Emphasis Type="Italic">γ</Emphasis>-admissibility of Relevant Modal Logics I — The Method of Normal Models

The admissibility of Ackermann’s rule γ is one of the most important problems in relevant logic. While the γ-admissibility of normal modal logics based on the relevant logic R has been previously discussed, the case for weaker relevant modal logics has not yet been considered. The method of normal models has often been used to prove the γ-admissibility. This paper discusses which relevant modal logics admit γ from the viewpoint of the method of normal models.     

The Monodic Fragment of Propositional Term Modal Logic

We study term modal logics, where modalities can be indexed by variables that can be quantified over. We suggest that these logics are appropriate for reasoning about systems of unboundedly many reasoners and define a notion of bisimulation which preserves propositional fragment of term modal logics. Also we show that the propositional fragment is already undecidable but that its monodic fragment (formulas using only one free variable in the scope of a modality) is decidable, and expressive enough to include interesting assertions.

     

Cut-Free Tableau Calculi for some Intuitionistic Modal Logics

In this paper we provide cut-free tableau calculi for the intuitionistic modal logics IK, ID, IT, i.e. the intuitionistic analogues of the classical modal systems K, D and T. Further, we analyse the necessity of duplicating formulas to which rules are applied. In order to develop these calculi we extend to the modal case some ideas presented by Miglioli, Moscato and Ornaghi for intuitionistic logic. Specifically, we enlarge the language with the new signs Fc and CR near to the usual signs T and F. In this work we establish the soundness and completeness theorems for these calculi with respect to the Kripke semantics proposed by Fischer Servi.     

ExpTime Tableau Decision Procedures for Regular Grammar Logics with Converse

Grammar logics were introduced by Fariñas del Cerro and Penttonen in 1988 and have been widely studied. In this paper we consider regular grammar logics with converse (REG ^c logics) and present sound and complete tableau calculi for the general satisfiability problem of REG ^c logics and the problem of checking consistency of an ABox w.r.t. a TBox in a REG ^c logic. Using our calculi we develop ExpTime (optimal) tableau decision procedures for the mentioned problems, to which various optimization techniques can be applied. We also prove a new result that the data complexity of the instance checking problem in REG ^c logics is coNP-complete.     

A uniform tableau method for intuitionistic modal logics I

We present tableau systems and sequent calculi for the intuitionistic analoguesIK, ID, IT, IKB, IKDB, IB, IK4, IKD4, IS4, IKB4, IK5, IKD5, IK45, IKD45 andIS5 of the normal classical modal logics. We provide soundness and completeness theorems with respect to the models of intuitionistic logic enriched by a modal accessibility relation, as proposed by G. Fischer Servi. We then show the disjunction property forIK, ID, IT, IKB, IKDB, IB, IK4, IKD4, IS4, IKB4, IK5, IK45 andIS5. We also investigate the relationship of these logics with some other intuitionistic modal logics proposed in the literature.Work carried out in the framework of the agreement between the Italian PT Administration and the Fondazione Ugo Bordoni.Presented byDov Gabbay