Temporal Logic

This essay is a contribution to the new trend and old tradition of analyzing theological fatalism in light of its relationship to logical fatalism. All results pertain to branching temporal systems that use the A-theory and assume presentism. The project focuses on two kinds of views about branching time. One position is true futurism, which designates what will occur regardless of contingency. The opposing view is open futurism, by which no possible course of events is privileged over others; that is, (...) there are no soft facts. -/- A contextualist theory of temporal standpoints, standpoint inheritance, is designed to enhance Priorian temporal logics. The proposal helps all branching time systems, not only those with an open future. Even though an account of temporal standpoints goes a long way towards aiding various analyses linguistically, theories that designate a true future ultimately succumb to philosophical difficulties. Under open futurism, standpoint inheritance commandeers the best semantic evidence for true futurism. Standpoint inheritance accounts for the evidence, but the evidence does not support true futurism's stronger claims. Furthermore, attempts to explain why one timeline is privileged as the actual future lead to fatalism. Open futurism and a related kind of open theism are the only viable alternatives under dynamic, branching time. If true futurism is feasible at all, it is so only with a static or eternalist basis. -/- Standpoint inheritance is very general. It is applied to every system discussed in this analysis to handle damning linguistic shortcomings of traditional logics. Standpoint inheritance yields several other fruitful results, too. The theory helps clarify what it is for characterizations of God's beliefs to be soft and how his beliefs must differ from normal beliefs to retain softness. For open futurism, all strings of consecutive will's and was's can be reduced to at most two such operators under standpoint inheritance, but not under traditional theories. The open futurist distinction between will and will-inevitably is clarified, too. Standpoint inheritance allows for a supervaluationist semantics using open futurism as its basis instead of the usual true futurism. The theory of standpoint inheritance enhances dynamic, branching accounts of time to better compete with their static correlates. (shrink)

We consider conditionals of the form A ⇒ B where A depends on the future and B on the present and past. We examine models for such conditional arising in Talmudic legal cases. We call such conditionals contrary to time conditionals.Three main aspects will be investigated: Inverse causality from future to past, where a future condition can influence a legal event in the past (this is a man made causality).Comparison with similar features in modern law.New types of temporal logics arising (...) from modelling the Talmudic examples. We shall see that we need a new temporal logic,which we call Talmudic temporal logic with linear open advancing future and parallel changing past, based on two parameters for time. (shrink)

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)

This paper contains a survey of the main definitions and results obtained to date related to Temporal Equilibrium Logic, a nonmonotonic hybrid approach that combines Equilibrium Logic (the best-known logical characterisation for the stable models semantics of logic programs) with Linear-Time Temporal Logic.

Temporal epistemic logics are known, from results of Halpern and Vardi, to have a wide range of complexities of the satisfiability problem: from PSPACE, through non-elementary, to highly undecidable. These complexities depend on the choice of some key parameters specifying, inter alia, possible interactions between time and knowledge, such as synchrony and agents' abilities for learning and recall. In this work we develop practically implementable tableau-based decision procedures for deciding satisfiability in single-agent synchronous temporal-epistemic logics with interactions between time and (...) knowledge. We discuss some complications that occur, even in the single-agent case, when interactions between time and knowledge are assumed and show how the method of incremental tableaux can be adapted to work in EXPSPACE, respectively 2EXPTIME, for these logics, thereby also matching the upper bounds obtained for them by Halpern and Vardi. (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 x 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 T1 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"). T1 is like the Segerberg-Sundholm system WI in working with so-called infinitary inference ruldes; on the other hand, it differs from W I 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 T1 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 T1. (shrink)

In their simplest form, hybrid languages are propositional modal languages which can refer to states. They were introduced by Arthur Prior, the inventor of tense logic, and played an important role in his work: because they make reference to specific times possible, they remove the most serious obstacle to developing modal approaches to temporal representation and reasoning. However very little is known about the computational complexity of hybrid temporal logics.In this paper we analyze the complexity of the satisfiability problem of (...) a number of hybrid temporal logics: the basic hybrid language over transitive trees; nominal Until logic; and referential interval logic. We discuss the effects of including nominals, the @ operator, the somewhere modality E, and the difference operator D. Adding nominals to tense logic leads for several frame-classes to an increase in complexity of the satisfiability problem from PSPACE to EXPTIME. On transitive trees, however, the satisfiability problem for this language can be decided in PSPACE. Along the way we make a detour through hybrid propositional dynamic logic: we establish upper bounds for a number of temporal logics by generalizing results due to Passy and Tinchev [29] and De Giacomo [16]. We conclude with some remarks on the relevance of our results to description logic, and draw attention to the utility of the spypoint technique for proving upper and lower bounds. (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, and two temporal modalities, and ∗, both interpreted using the continuous function. (shrink)

Conceptual realism acknowledges the existence of abstract objects: theoretical realism acknowledges the existence of non-observable objects; whereas classical realism acknowledges the existence of observable objects. Similarly, temporal realism accepts the existence of future and past events along with present ones, and spatial realism accepts the events which occur there (else-where) as well as those that occur here. We dealt earlier with the three former kinds of realism and their opposites: nominalism, instrumentalism and (ontological) idealism [2]. This paper contains an examination (...) of the two latter forms of realism: temporal and spatial, and their counterparts: temporal and spatial irrealisms. Analogies and connections between these standpoints will be the focus of the paper. (shrink)

The first-order temporal logics with □ and ○ of time structures isomorphic to ω (discrete linear time) and trees of ω-segments (linear time with branching gaps) and some of its fragments are compared: the first is not recursively axiomatizable. For the second, a cut-free complete sequent calculus is given, and from this, a resolution system is derived by the method of Maslov.

It is shown that the infinite-valued first-order Gödel logic G° based on the set of truth values {1/k: k ε w {0}} U {0} is not r.e. The logic G° is the same as that obtained from the Kripke semantics for first-order intuitionistic logic with constant domains and where the order structure of the model is linear. From this, the unaxiomatizability of Kröger's temporal logic of programs (even of the fragment without the nexttime operator O) and of the authors' temporal (...) logic of linear discrete time with gaps follows. (shrink)

We prove that a propositional Linear Temporal Logic with Until and Next has unitary unification. Moreover, for every unifiable in LTL formula A there is a most general projective unifier, corresponding to some projective formula B, such that A is derivable from B in LTL. On the other hand, it can be shown that not every open and unifiable in LTL formula is projective. We also present an algorithm for constructing a most general unifier.

Those inclined to positions in the philosophy of time that take tense seriously have typically assumed that not all regions of space-time are equal: one special region of space-time corresponds to what is presently happening. When combined with assumptions from modern physics this has the unsettling consequence that the shape of this favored region distinguishes people in certain places or people traveling at certain velocities. In this paper I shall attempt to avoid this result by developing a tensed picture of (...) reality that is nonetheless consistent with ‘hypersurface egalitarianism’—the view that all hypersurfaces are equal. (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)

In this paper I explore three related topics emerging from Prior's work on the logic of time. First, what is the proper province of logic, if any? Is temporal (modal) logic just logic, on a par with the paradigmatic case of first order quantication theory or even simple propositional logic? Second, what counts as an interpretation of a formal system? In particular, can formal semantics provide an interpretation? Third, what is the proper role of the meta-theory? In connection with this (...) last question we will see how Prior's attitude towards instants of time may teach us something about the analogous case of possible worlds. (shrink)

Hume argues that the idea of duration is just the idea of the manner in which several things in succession are arrayed. In other words, the idea of duration is the idea of successiveness. He concludes that all and only successions have duration. Hume also argues that there is such a thing as a steadfast object—something which co-exists with many things in succession, but which is not itself a succession. Thus, it seems that Hume has committed himself to a contradiction: (...) A steadfast object lacks duration because it is not a succession, but has duration because it co-exists with something which has duration. I am not going to discuss why Hume thinks these things. My goal is simply to show that what he thinks is consistent. To do so, I will offer a Humean temporal logic. (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)

This paper follows Part I of our essay on case-intensional first-order logic (CIFOL; Belnap and Müller (2013)). We introduce a framework of branching histories to take account of indeterminism. Our system BH-CIFOL adds structure to the cases, which in Part I formed just a set: a case in BH-CIFOL is a moment/history pair, specifying both an element of a partial ordering of moments and one of the total courses of events (extending all the way into the future) that that moment (...) is part of. This framework allows us to define the familiar Ockhamist temporal/modal connectives, most notably for past, future, and settledness. The novelty of our framework becomes visible in our discussion of substances in branching histories, i.e., in its first-order part. That discussion shows how the basic idea of tracing an individual thing from case to case via an absolute property is applicable in a branching histories framework. We stress the importance of keeping apart extensionality and moment-definiteness, and give a formal account of how the specification of natural sortals and natural qualities turns out to be a coordination task in BH-CIFOL. We also provide a detailed answer to Lewis’s well-known argument against branching histories, exposing the fallacy in that argument. (shrink)

ABSTRACT: The modal systems of the Stoic logician Chrysippus and the two Hellenistic logicians Philo and Diodorus Cronus have survived in a fragmentary state in several sources. From these it is clear that Chrysippus was acquainted with Philo’s and Diodorus’ modal notions, and also that he developed his own in contrast of Diodorus’ and in some way incorporated Philo’s. The goal of this paper is to reconstruct the three modal systems, including their modal definitions and modal theorems, and to make (...) clear the exact relations between them; moreover, to elucidate the philosophical reasons that may have led Chrysippus to modify his predessors’ modal concept in the way he did. It becomes apparent that Chrysippus skillfully combined Philo’s and Diodorus’ modal notions, with making only a minimal change to Diodorus’ concept of possibility; and that he thus obtained a modal system of modalities (logical and physical) which fit perfectly fit into Stoic philosophy. (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)

Interval temporal logics provide both an insight into a nature of time and a framework for temporal reasoning in various areas of computer science. In this paper we present sound and complete relational proof systems in the style of dual tableaux for relational logics associated with modal logics of temporal intervals and we prove that the systems enable us to verify validity and entailment of these temporal logics. We show how to incorporate in the systems various relations between intervals and/or (...) various time orderings. (shrink)