Axiomatisation and decidability ofF andP in cyclical time

We present a Hilert style axiomatisation for the set of formulas in the temporal language withF andP which are valid over non-transitive cyclical flows of time.We also give a simpler axiomatisation using the slightly controversial irreflexivity rule and go on to prove the decidability of any temporal logic over cyclical time provided it uses only connectives with first-order tables.     

Monodic Packed Fragment with Equality is Decidable

We prove decidability of satisfiability of sentences of the monodic packed fragment of first-order temporal logic with equality and connectives Until and Since, in models with various flows of time and domains of arbitrary cardinality. We also prove decidability over models with finite domains, over flows of time including the real order.     

Cut-free sequent and tableau systems for propositional Diodorean modal logics

We present sound, (weakly) complete and cut-free tableau systems for the propositional normal modal logicsS4.3, S4.3.1 andS4.14. When the modality is given a temporal interpretation, these logics respectively model time as a linear dense sequence of points; as a linear discrete sequence of points; and as a branching tree where each branch is a linear discrete sequence of points.Although cut-free, the last two systems do not possess the subformula property. But for any given finite set of formulaeX the superformulae involved are always bounded by a finite set of formulaeX* _L depending only onX and the logicL. Thus each system gives a nondeterministic decision procedure for the logic in question. The completeness proofs yield deterministic decision procedures for each logic because each proof is constructive.Each tableau system has a cut-free sequent analogue proving that Gentzen's cut-elimination theorem holds for these latter systems. The techniques are due to Hintikka and Rautenberg.Presented byDov M. Gabbay     

The semantics of Hoare's Iteration Rule

Hoare's Iteration Rule is a principle of reasoning that is used to derive correctness assertions about the effects of implementing a while-command. We show that the propositional modal logic of this type of command is axiomatised by Hoare's rule in conjunction with two additional axioms. The proof also establishes decidability of the logic. The paper concludes with a discussion of the relationship between the logic of while and Segerberg's axiomatisation of propositional dynamic logic.     

An axiomatization for until and since over the reals without the IRR rule

We give a Hilbert style axiomatization for the set of formulas in the temporal language with Until and Since which are valid over the real number flow of time. The axiomatization, which is orthodox in the sense of only having the usual temporal rules of inference, is complete with respect to single formulas.The author would like to thank Dov Gabbay, Yde Venema, the referee and especially Ian Hodkinson for helpful comments during the development of this work. The work was supported by the U.K. Science and Engineering Research Council under the Metatem project (GR/F/28526).     

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.     

Notes on Logics of Metric Spaces

In [14], we studied the computational behaviour of various first-order and modal languages interpreted in metric or weaker distance spaces. [13] gave an axiomatisation of an expressive and decidable metric logic. The main result of this paper is in showing that the technique of representing metric spaces by means of Kripke frames can be extended to cover the modal (hybrid) language that is expressively complete over metric spaces for the (undecidable) two-variable fragment of first-order logic with binary pred-icates interpreting the metric. The frame conditions needed correspond rather directly with a Boolean modal logic that is, again, of the same expressivity as the two-variable fragment. We use this representation to derive an axiomatisation of the modal hybrid variant of the two-variable fragment, discuss the compactness property in distance logics, and derive some results on (the failure of) interpolation in distance logics of various expressive power. Presented by Melvin Fitting     

Multi-Modal CTL: Completeness,Complexity, and an Application

We define a multi-modal version of Computation Tree Logic (ctl) by extending the language with path quantifiers E ^δ and A ^δ where δ denotes one of finitely many dimensions, interpreted over Kripke structures with one total relation for each dimension. As expected, the logic is axiomatised by taking a copy of a ctl axiomatisation for each dimension. Completeness is proved by employing the completeness result for ctl to obtain a model along each dimension in turn. We also show that the logic is decidable and that its satisfiability problem is no harder than the corresponding problem for ctl. We then demonstrate how Normative Systems can be conceived as a natural interpretation of such a multi-dimensional ctl logic. Presented by Jacek Malinowski     

Synchronization of Logics

Motivated by applications in software engineering, we propose two forms of combination of logics: synchronization on formulae and synchronization on models. We start by reviewing satisfaction systems, consequence systems, one-step derivation systems and theory spaces, as well as their functorial relationships. We define the synchronization on formulae of two consequence systems and provide a categorial characterization of the construction. For illustration we consider the synchronization of linear temporal logic and equational logic. We define the synchronization on models of two satisfaction systems and provide a categorial characterization of the construction. We illustrate the technique in two cases: linear temporal logic versus equational logic; and linear temporal logic versus branching temporal logic. Finally, we lift the synchronization on formulae to the category of logics over consequences systems.     

Relevant identity

We begin to fill a lacuna in the relevance logic enterprise by providing a foundational analysis of identity in relevance logic. We consider rival interpretations of identity in this context, settling on the relevant indiscernibility interpretation, an interpretation related to Dunn's relevant predication project. We propose a general test for the stability of an axiomatisation of identity, relative to this interpretation, and we put various axiomatisations to this test. We fill our discussion out with both formal and philosophical remarks on identity in relevance logic.     

Semantics for Dual Preferential Entailment

We introduce and explore the notion of duality for entailment relations induced by preference orderings on states. We discuss the relationship between these preferential entailment relations from the perspectives of Boolean algebra, inference rules, and modal axiomatisation. Interpreting the preference relations as accessibility relations establishes modular Gödel-Löb logic as a suitable modal framework for rational preferential reasoning.     

Glivenko Type Theorems for Intuitionistic Modal Logics

In this article we deal with Glivenko type theorems for intuitionistic modal logics over Prior's MIPC. We examine the problems which appear in proving Glivenko type theorems when passing from the intuitionistic propositional logic Intto MIPC. As a result we obtain two different versions of Glivenko's theorem for logics over MIPC. Since MIPCcan be thought of as a one-variable fragment of the intuitionistic predicate logic Q-Int, one of the versions of Glivenko's theorem for logics over MIPCis closely related to that for intermediate predicate logics obtained by Umezawa [27] and Gabbay [15]. Another one is rather surprising.     

An Axiomatisation for the Multi-modal Logic of Knowledge and Linear Time LTK

The paper aims at providing the multi-modal propositional logicLTK with a sound and complete axiomatisation. This logic combinestemporal and epistemic operators and focuses on m odeling thebehaviour of a set of agents operating in a system on the backgroundof a temporal framework. Time is represented as linear and discrete,whereas knowledge is modeled as an S₅-like modality. A furthermodal operator intended to represent environment knowledge isadded to the system in order to achieve the expressive powersufficient to describe the piece of information available tothe agents at each moment in the flow of time.     

Constraint Satisfaction, Irredundant Axiomatisability and Continuous Colouring

We observe a number of connections between recent developments in the study of constraint satisfaction problems, irredundant axiomatisation and the study of topological quasivarieties. Several restricted forms of a conjecture of Clark, Davey, Jackson and Pitkethly are solved: for example we show that if, for a finite relational structure M, the class of M-colourable structures has no finite axiomatisation in first order logic, then there is no set (even infinite) of first order sentences characterising the continuously M-colourable structures amongst compact totally disconnected relational structures. We also refute a rather old conjecture of Gorbunov by presenting a finite structure with an infinite irredundant quasi-identity basis.     

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     

Nonmonotonic reasoning: from finitary relations to infinitary inference operations

A. Tarski [22] proposed the study of infinitary consequence operations as the central topic of mathematical logic. He considered monotonicity to be a property of all such operations. In this paper, we weaken the monotonicity requirement and consider more general operations, inference operations. These operations describe the nonmonotonic logics both humans and machines seem to be using when infering defeasible information from incomplete knowledge. We single out a number of interesting families of inference operations. This study of infinitary inference operations is inspired by the results of [12] on nonmonotonic inference relations, and relies on some of the definitions found there.This work was partially supported by a grant from the Basic Research Foundation, Israel Academy of Sciences and Humanities and by the Jean and Helene Alfassa fund for research in Artificial Intelligence. Its final write-up was performed while the second author visited the Laboratoire d'Informatique Théorique et de Programmation, Université Paris 6.Presented byDov M. Gabbay     

Temporalising Tableaux

As a remedy for the bad computational behaviour of first-order temporal logic (FOTL), it has recently been proposed to restrict the application of temporal operators to formulas with at most one free variable thereby obtaining so-called monodic fragments of FOTL. In this paper, we are concerned with constructing tableau algorithms for monodic fragments based on decidable fragments of first-order logic like the two-variable fragment or the guarded fragment. We present a general framework that shows how existing decision procedures for first-order fragments can be used for constructing a tableau algorithm for the corresponding monodic fragment of FOTL. Some example instantiations of the framework are presented.     

Beyond Social and Temporal Comparisons: The Role of Temporal Inter-Group Comparisons in the Context of Dramatic Social Change in Mongolia

ABSTRACT

In this paper, we argue that the target of comparison should be taken into consideration when evaluating the associated outcomes of negative comparisons in the context of dramatic social change. To achieve this general goal, we considered five distinct targets of comparison: social (my group versus another group), temporal (my group across time), and temporal inter-group (my group versus another group across time). We hypothesised that in times of constant social change, two points of anchors (social and temporal) are simultaneously needed to evaluate one's position. A total of 236 high school and university students from Mongolia participated in the study. We used hierarchical regression analysis to test our hypotheses. As predicted, we found that temporal inter-group comparisons are better predictor of collective esteem than their social and temporal counterparts. Moreover, the link from past and future temporal inter-group comparisons to collective esteem was negative as hypothesized. Results are discussed in terms of theoretical implications.     

Children’s Memory for Temporal Information: The Roles of Temporal Language and Executive Function

Abstract

The ability to recall the temporal order of events develops much more slowly than the ability to recall facts about events. To explore what processes facilitate memory for temporal information, we tested 3- to 6-year-old children (N?=?40) for immediate memory of the temporal order of events from a storybook, using a visual timeline task and a yes/no recognition task. In addition, children completed tasks assessing their understanding of before and after and the executive functions of inhibition using the Day/Night Stroop task and cognitive shifting using the Dimensional Change Card Sort (DCCS) task. Older children (Mage?=?69.25?months) outperformed younger children (Mage?=?52.35?months) on all measures; however, the only significant predictor of memory for the temporal ordering of events was cognitive shifting. The findings suggest that the difficulty in memory for temporal information is related to development of a general cognitive ability, as indexed by the DCCS, rather than specific temporal abilities.