Alternating-time temporal logic (ATL) is a branching time temporal logic in which statements about what coalitions of agents can achieve by strategic cooperation can be expressed. Alternating-time temporal epistemic logic (ATEL) extends ATL by adding knowledge modalities, with the usual possible worlds interpretation. This paper investigates how properties of agents’ actions can be expressed in ATL in general, and how properties of the interaction between action and knowledge can be expressed in ATEL in particular. One commonly discussed property is that (...) an agent should know about all available actions, i.e., that the same actions should be available in indiscernible states. Van der Hoek and Wooldridge suggest a syntactic expression of this semantic property. This paper shows that this correspondence in fact does not hold. Furthermore, it is shown that the semantic property is not expressible in ATEL at all. In order to be able to express common and interesting properties of action in general and of the interaction between action and knowledge in particular, a generalization of the coalition modalities of ATL is proposed. The resulting logics, ATL-A and ATEL-A, have increased expressiveness without loosing ATL’s and ATEL’s tractability of model checking. (shrink)

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.

This volume is a collection of papers presented at the colloquium, and it testifies to the growing importance of game theory as a tool that can capture concepts ...

The paper presents an infinite hierarchy PR m [ m = 1, 2, . . . ] of sound and complete axiomatic systems for modal logic with graded probabilistic modalities , which are to reflect what I have elsewhere called the Bolding-Ekelöf degrees of evidential strength as applied to the establishment of matters of fact in law-courts. Our present approach is seen to differ from earlier work by the author in that it treats the logic of these graded modalities not (...) only from a semantical or model-theoretic viewpoint but from a prooftheoretical and axiomatic stance as well. A paramount feature of the approach is its use of so-called systematic frame constants as labels of diverse grades of probability. Apart from this novel feature our approach can be seen to go back to pioneering work by Lou Goble in 1970. (shrink)

The paper presents an infinite hierarchy of sound and complete axiomatic systems for Two-Dimensional Modal Tense Logic with Historical Necessity, Agents and Acts. A main novelty of these logics is their capacity to represent formally (i) basic action-sentences asserting that such and such an act is performed/omitted by an agent, as well as (ii) causative action-sentences asserting that by performing/omitting a certain act, an agent causes that such and such a state-of-affairs is realized (e.g. comes about/ceases/remains/remains absent). We illustrate how (...) the formal machinery of our systems can be used to reconstruct a number of interesting ideas in the Logic of Agency and Action that have been proposed by authors like von Wright, von Kutschera, Belnap and Segerberg. (shrink)

We consider a version of so called T × W logic for historical necessity in the sense of R.H. Thomason (1984), which is somewhat special in three respects: (i) it is explicitly based on two-dimensional modal logic in the sense of Segerberg (1973); (ii) for reasons of applicability to interesting fields of philosophical logic, it conceives of time as being discrete and finite in the sense of having a beginning and an end; and (iii) it utilizes the technique of systematic (...) frame constants in order to handle the problem of irreflexivity in tense logics, well known since Gabbay (1981). Axiomatizations are given for two infinite hierarchies of two-dimensional modal tense logics, one without and one with the characteristic operators for historical necessity and possibility. Strong and weak completeness results are obtained for both hierarchies as well as a result to the effect that two approaches to their semantics are equivalent, much in the spirit of Di Maio and Zanardo (1996) and von Kutschera (1997). (shrink)

The paper deals with the problem of axiomatizing a system 1 of discrete tense logic, where one thinks of time as the set Z of all the integers together with the operations +1 (immediate successor) and -1 (immediate predecessor). 1 is like the Segerberg-Sundholm system W1 in working with so-called infinitary inference rules; on the other hand, it differs from W1 with respect to (i) proof-theoretical setting, (ii) presence of past tense operators and a now operator, and, most importantly, with (...) respect to (iii) the presence in of so-called systematic frame constants, which are meant to hold at exactly one point in a temporal structure and to enable us to express the irreflexivity of such structures. Those frame constants will be seen to play a paramount role in our axiomatization of 1. (shrink)

A set of axioms implicitly defining the standard, though not instant-based but interval-based, time topology is used as a basis to build a temporal modal logic of events. The whole apparatus contains neither past, present, and future operators nor indexicals, but only B-series relations and modal operators interpreted in the standard way. Determinism and indeterminism are then introduced into the logic of events via corresponding axioms. It is shown that, if determinism and indeterminism are understood in accordance with their core (...) meaning, the way in which they are formally introduced here represents the only right way to do this, given that we restrict ourselves to one real world and make no use of the many real worlds assumption. But then the result is that the very truth conditions for sentences about indeterministic events imply the existence of tensed truths, in spite of the fact that these conditions are formulated (in the indeterministic axiom) in terms of tenseless language. The tenseless theory of time implies determinism, while indeterminism requires the flow of time assumption. (shrink)

Dynamic topological logic provides a context for studying the confluence of the topological semantics for S4, topological dynamics, and temporal logic. The topological semantics for S4 is based on topological spaces rather than Kripke frames. In this semantics, is interpreted as topological interior. Thus S4 can be understood as the logic of topological spaces, and can be understood as a topological modality. Topological dynamics studies the asymptotic properties of continuous maps on topological spaces. Let a dynamic topological system be (...) a topological space X together wError: Corrupted memory profileError: read ICCBased color space profile errorith a continuous function f . f can be thought of in temporal terms, moving the points of the topological space from one moment to the next. Dynamic topological logics are the logics of dynamic topological systems, just as S4 is the logic of topological spaces. Dynamic topological logics are defined for a trimodal language with an S4-ish topological modality (interior), and two temporal modalities, (next) and ∗ (henceforth), both interpreted using the continuous function.. (shrink)

We propose two alternatives to Xu’s axiomatization of Chellas’s STIT. The first one simplifies its presentation, and also provides an alternative axiomatization of the deliberative STIT. The second one starts from the idea that the historic necessity operator can be defined as an abbreviation of operators of agency, and can thus be eliminated from the logic of Chellas’s STIT. The second axiomatization also allows us to establish that the problem of deciding the satisfiability of a STIT formula without temporal operators (...) is NP-complete in the single-agent case, and is NEXPTIME-complete in the multiagent case, both for the deliberative and Chellas’s STIT. (shrink)

A common and much-explored thought is ?ukasiewicz's idea that the future is ?indeterminate??i.e., ?gappy? with respect to some claims?and that such indeterminacy bleeds back into the present in the form of gappy ?future contingent? claims. What is uncommon, and to my knowledge unexplored, is the dual idea of an overdeterminate future?one which is ?glutty? with respect to some claims. While the direct dual, with future gluts bleeding back into the present, is worth noting, my central aim is simply to sketch (...) and briefly explore an alternative glutty-future view, one that is conservative?indeed, entirely classical?with respect to the present. The structure of the paper runs as follows. ?1 briefly sketches the target gap picture of an indeterminate future yielding gappy claims at the present. ?2 presents the direct dual idea?a glut picture of an overdeterminate future yielding glutty claims at present. ?3 sketches the central idea, a more interesting glut picture in which the future contains contradictory states but the present remains entirely classical. ?4 contains a general defence of the idea, leaving it open as to whether the gappy-future view enjoys substantive virtues over the proposed glutty-future view of ?3. (shrink)

The theory of belief revision deals with (rational) changes in beliefs in response to new information. In the literature a distinction has been drawn between belief revision and belief update (see [6]). The former deals with situations where the objective facts describing the world do not change (so that only the beliefs of the agent change over time), while the letter allows for situations where both the facts and the doxastic state of the agent change over time. We focus on (...) belief revision and propose a temporal framework that allows for iterated revision. We model the notion of “minimal” or “conservative” belief revision by considering logics of increasing strength. We move from one logic to the next by adding one or more axioms and show that the corresponding logic captures more stringent notions of minimal belief revision. The strongest logic that we propose provides a full axiomatization of the well-known AGM theory of belief revision. (shrink)

Since belief revision deals with the interaction of belief and information over time, branching-time temporal logic seems a natural setting for a theory of belief change. We propose two extensions of a modal logic that, besides the next-time temporal operator, contains a belief operator and an information operator. The first logic is shown to provide an axiomatic characterization of the first six postulates of the AGM theory of belief revision, while the second, stronger, logic provides an axiomatic characterization of the (...) full set of AGM postulates. © 2006 Elsevier B.V. All rights reserved. (shrink)

For branching-time temporal logic based on an Ockhamist semantics, we explore a temporal language extended with two additional syntactic tools. For reference to the set of all possible futures at a moment of time we use syntactically designated restricted variables called fan-names. For reference to all possible futures alternative to the actual one we use a modification of a difference modality, localized to the set of all possible futures at the actual moment of time.We construct an axiomatic system for this (...) extended branching-time logic and prove its soundness and completeness with respect to bundle tree semantics. Finally, we show how our axiomatic system can be extended with a variety of important additional operators, such as Since and Until, a global difference operator, operators for undivided and divided histories, reference pointers, etc. (shrink)

The aim of this paper is to consider some logical aspects of the debate between the view that the present is the only 'real' time, and the view that the present is not in any way metaphysically privileged. In particular I shall set out a language of first-order predicate tense logic with a now predicate, and a first order (extensional) language with an abstraction operator, in such a way that each language can be shewn to be exactly translatable into the (...) other. I shew that this translation is preserved at the metalinguistic level, so that equivalent truth conditions can be defined in a tensed metalanguage or an indexical metalanguage. I then make some remarks about the connection between proofs of relative consistency and metaphysical truth; and some historical remarks about Arthur Prior's use of formal logic in expressing his presentist views. (shrink)

It has been shown recently that monodic first-order temporal logic without functional symbols but with equality is incomplete, i.e., the set of the valid formulae of this logic is not recursively enumerable. In this paper we show that an even simpler fragment consisting of monodic monadic two-variable formulae is not recursively enumerable.

Temporal logic can be used to describe processes: their behaviour ischaracterized by a set of temporal models axiomatized by a temporaltheory. Two types of models are most often used for this purpose: linearand branching time models. In this paper a third approach, based onsocalled joint closure models, is studied using models which incorporateall possible behaviour in one model. Relations between this approach andthe other two are studied. In order to define constructions needed torelate branching time models, appropriate algebraic notions are (...) defined(in a category theoretical manner) and exploited. In particular, thenotion of joint closure is used to construct one model subsuming a setof models. Using this universal algebraic construction we show that aset of linear models can be merged to a unique branching time model.Logical properties of the described algebraic constructions are studied.The proposed approach has been successfully aplied to obtain anappropriate semantics for non-monotonic reasoning processes based ondefault logic. References are discussed that show the details of theseapplications. (shrink)

This paper assesses branching spacetime theories in light of metaphysical considerations concerning time. I present the A, B, and C series in terms of the temporal structure they impose on sets of events, and raise problems for two elements of extant branching spacetime theories—McCall’s ‘branch attrition’, and the ‘no backward branching’ feature of Belnap’s ‘branching space-time’—in terms of their respective A- and B-theoretic nature. I argue that McCall’s presentation of branch attrition can only be coherently formulated on a model with (...) at least two temporal dimensions, and that this results in severing the link between branch attrition and the flow of time. I argue that ‘no backward branching’ prohibits Belnap’s theory from capturing the modal content of indeterministic physical theories, and results in it ascribing to the world a time-asymmetric modal structure that lacks physical justification. (shrink)

With the past and future tense propositional operators in its syntax, a formal logical system for sortal quantifiers, sortal identity and (second order) quantification over sortal concepts is formulated. A completeness proof for the system is constructed and its absolute consistency proved. The completeness proof is given relative to a notion of logical validity provided by an intensional semantic system, which assumes an approach to sortals from a modern form of conceptualism.

In this paper we suggest adding to predicate modal and temporal logic a locality predicate W which gives names to worlds (or time points). We also study an equal time predicate D(x, y)which states that two time points are at the same distance from the root. We provide the systems studied with complete axiomatizations and illustrate the expressive power gained for modal logic by simulating other logics. The completeness proofs rely on the fairly intuitive notion of a configuration in order (...) to use a proof technique similar to a Henkin completion mixed with a tableau construction. The main elements of the completeness proofs are given for each case, while purely technical results are grouped in the appendix. (shrink)

Contextuality is trivially pervasive: all human experience takes place in endlessly changing environments and inexorably moving time frames. In order to have any meaning, the changing items must be placed within a more stable setting, a framework that is not subject to the same kind of contextual change. Total contextuality collapses into chaos, or becomes ineffable. While basic learning is highly contextual (one learns by example), what is learned transcends the examples used in the learning. Perhaps, in a similar manner, (...) artistic expression transcends context by fully embracing it. In any case, a philosophical account of contextuality is itself stated in a more absolute mode, not necessarily a picture from an “eternal” view point, but at least one that avoids the contextuality which it describes. (shrink)

This paper argues that the Einstein-Minkowski space-time of special relativity provides an adequate model for classical tense logic, including rigorous definitions of tensed becoming and of the logical priority of proper time. In addition, the extension of classical tense logic with an operator for predicate-term negation provides us with a framework for interpreting and defending the significance of future contingency in special relativity. The framework for future contingents developed here involves the dual falsehood of non-logical contraries, only one of which (...) becomes true. This has several methodological, metaphysical and physical advantages over the alternative traditional frameworks for handling future contingents. (shrink)

Branching-time temporal logics have proved to be an extraordinarily successful tool in the formal specification and verification of distributed systems. Much of their success stems from the tractability of the model checking problem for the branching time logic CTL, which has made it possible to implement tools that allow designers to automatically verify that systems satisfy requirements expressed in CTL. Recently, CTL was generalised by Alur, Henzinger, and Kupferman in a logic known as "Alternating-time Temporal Logic" (ATL). The key (...) insight in ATL is that the path quantifiers of CTL could be replaced by "cooperation modalities", of the form $\langle \langle \Gamma \rangle \rangle $ , where Γ is a set of agents. The intended interpretation of an ATL formula $\langle \langle \Gamma \rangle \rangle \varphi $ is that the agents Γ can cooperate to ensure that φ holds (equivalently, that Γ have a winning strategy for φ). In this paper, we extend ATL with knowledge modalities, of the kind made popular in the work of Fagin, Halpern, Moses, Vardi and colleagues. Combining these knowledge modalities with ATL, it becomes possible to express such properties as "group Γ can cooperate to bring about φ iff it is common knowledge in Γ that ψ". The resulting logic -- Alternating-time Temporal Epistemic Logic (ATEL) -- shares the tractability of model checking with its ATL parent, and is a succinct and expressive language for reasoning about game-like multiagent systems. (shrink)

Classical mereology (CM) is usually taken to be formulated in a tenseless language, and is therefore associated with a four-dimensionalist metaphysics. This paper presents three ways one might integrate the core idea of flat plenitude, i.e., that every suitable condition or property has exactly one mereological fusion, with a tensed logical setting. All require a revised notion of mereological fusion. The candidates differ over how they conceive parthood to interact with existence in time, which connects to the distinction between endurance (...) and perdurance. Similar issues arise for the integration of mereology with modality, and much of our discussion applies to this project as well. (shrink)

We consider the decision problem for cases of first-order temporal logic with function symbols and without equality. The monadic monodic fragment with flexible functions can be decided with EXPSPACE-complete complexity. A single rigid function is sufficient to make the logic not recursively enumerable. However, the monadic monodic fragment with rigid functions, where no two distinct terms have variables bound by the same quantifier, is decidable and EXPSPACE-complete.

The paper is devoted to the concise description of some Natural Deduction System (ND for short) for Linear Temporal Logic. The system's distinctive feature is that it is labelled and analytical. Labels convey necessary semantic information connected with the rules for temporal functors while the analytical character of the rules lets the system work as a decision procedure. It makes it more similar to Labelled Tableau Systems than to standard Natural Deduction. In fact, our solution of linearity representation is rather (...) independent of the underlying proof method, provided that some form of (analytic) cut is admissible. We will also discuss some generalisations of the system and compare it with other formalizations of linearity. (shrink)

We define bisimulations for temporal logic with Since and Until. This new notion is compared to existing notions of bisimulations, and then used to develop the basic model theory of temporal logic with Since and Until. Our results concern both invariance and definability. We conclude with a brief discussion of the wider applicability of our ideas.

The concept of a temporal phylogenetic network is a mathematical model of evolution of a family of natural languages. It takes into account the fact that languages can trade their characteristics with each other when linguistic communities are in contact, and also that a contact is only possible when the languages are spoken at the same time. We show how computational methods of answer set programming and constraint logic programming can be used to generate plausible conjectures about contacts between prehistoric (...) linguistic communities, and illustrate our approach by applying it to the evolutionary history of Indo-European languages. (shrink)

This paper presents an approach to artificial intelligence planning based on linear temporal logic (LTL). A simple and easy-to-use planning language is described, Planning Domain Description Language with control Knowledge (PDDL-K), which allows one to specify a planning problem together with heuristic information that can be of help for both pruning the search space and finding better quality plans. The semantics of the language is given in terms of a translation into a set of LTL formulae. Planning is then reduced (...) to “executing” the LTL encoding, i.e. to model search in LTL. The feasibility of the approach has been successfully tested by means of the system Pdk, an implementation of the proposed method. (shrink)

According to Hans Kamp and Frank Vlach, the two-dimensional tense operators "now" and "then" are ineliminable in quantified tense logic. This is often adduced as an argument against tense logic, and in favor of an extensional account that makes use of explicit quantification over times. The aim of this paper is to defend tense logic against this attack. It shows that "now" and "then" are eliminable in quantified tense logic, provided we endow it with enough quantificational structure. The operators might (...) not be redundant in some other systems of tense logic, but this merely indicates a lack of quantificational resources and does not show any deep-seated inability of tense logic to express claims about time. The paper closes with a brief discussion of the modal analogue of this issue, which concerns the role of the actuality operator in quantified modal logic. (shrink)

The aim of this paper is to draw attention to a conflict between two popular views about time: Arthur Prior’s proposal for treating tense on the model of modal logic, and the ‘Platonic’ thesis that some objects (God, forms, universals, or numbers) exist eternally.1 I will argue that anyone who accepts the former ought to reject the latter.

We suggest that developing automata theoretic foundations is relevant for knowledge theory, so that we study not only what is known by agents, but also the mechanisms by which such knowledge is arrived at. We define a class of epistemic automata , in which agents’ local states are annotated with abstract knowledge assertions about others. These are finite state agents who communicate synchronously with each other and information exchange is ‘perfect’. We show that the class of recognizable languages has good (...) closure properties, leading to a Kleene-type theorem using what we call regular knowledge expressions . These automata model distributed causal knowledge in the following way: each agent in the system has a partial knowledge of the temporal evolution of the system, and every time agents synchronize, they update each other’s knowledge, resulting in a more up-to-date view of the system state. Hence we show that these automata can be used to solve the satisfiability problem for a natural epistemic temporal logic for local properties. Finally, we characterize the class of languages recognized by epistemic automata as the regular consistent languages studied in concurrency theory. (shrink)

PREFACE This essay developed from ideas in my doctoral thesis submitted to the Hebrew University in 1977. Chapter three has been amended as regards one of ...

We present an axiomatisation for the first-order temporal logic with connectives Until and Since over the class of all linear flows of time. Completeness of the axiom system is proved.We also add a few axioms to find a sound and complete axiomatisation for the first order temporal logic of Until and Since over rational numbers time.

We investigate logical consequence in temporal logics in terms of logical consecutions. i.e., inference rules. First, we discuss the question: what does it mean for a logical consecution to be 'correct' in a propositional logic. We consider both valid and admissible consecutions in linear temporal logics and discuss the distinction between these two notions. The linear temporal logic LDTL, consisting of all formulas valid in the frame 〈L, ≤, ≥〉 of all integer numbers, is the prime object of our investigation. (...) We describe consecutions admissible LDTL in a semantic way—via consecutions valid in special temporal Kripke/Hintikka models. Then we state that any temporal inference rule has a reduced normal form which is given in terms of uniform formulas of temporal degree 1. Using these facts and enhanced semantic techniques we construct an algorithm, which recognizes consecutions admissible in LDTL. Also, we note that using the same technique it follows that the linear temporal logic L (N) of all natural numbers is also decidable w.r.t. inference rules. So, we prove that both logics LDTL and L (N) are decidable w.r.t. admissible consecutions. In particular, as a consequence, they both are decidable (Known fact), and the given deciding algorithms are explicit. (shrink)

A somewhat fictionalized account of several interpretations of implication is presented together with comparisons between classical, modal, tense, and intuitionistic logics.

I defend the A Theory of Time that there are tensed (and other indexical) facts, e.g., about what has happened, as well as tenseless facts, e.g., about what happened in the nineteenth century. I reject arguments of McTaggart and Grunbaum, but concentrate on Mellor’s argument that tenseless truth-conditions can be given for the truth of every tensed sentence. My rebuttal of this argument depends on a distinction between the ’proposition’ and the ’statement’ expressed by a sentence. Statements have changeless truth-value, (...) while propositions may change truth-value; but there is more to be known than knowledge of true statements can capture. (shrink)

From reviews of the first edition: 'Overall this is an admirable work.

It is proved that all bimodal tense logics which contain the logic of the weak orderings and have unbounded depth do not have the interpolation property.

The basic notions in Prior’s Ockhamist and Peircean logics of branching-time are the notion of moment and that of history (or course of events). In the tree semantics, histories are defined as maximal linearly ordered sets of moments. In the geometrical approach, both moments and histories are primitive entities and there is no set theoretical (and ontological) dependency of the latter on the former. In the topological approach, moments can be defined as the elements of a rank 1 base of (...) a non-Archimedean topology on the set of histories. In this paper, it will be shown that the topological approach, and hence the other approaches, can be reconstructed in a framework in which the basic notions are those of history and of relative closeness relation among histories. (shrink)