Temporal Logic: From Ancient Ideas to Artificial Intelligence deals with the history of temporal logic as well as the crucial systematic questions within the field. The book studies the rich contributions from ancient and medieval philosophy up to the downfall of temporal logic in the Renaissance. The modern rediscovery of the subject, which is especially due to the work of A. N. Prior, is described, leading into a thorough discussion of the use of (...) class='Hi'>temporal logic in computer science and the understanding of natural language. Temporal Logic: From Ancient Ideas to Artificial Intelligence thus interweaves linguistic, philosophical and computational aspects into an informative and inspiring whole. (shrink)

This much-needed book provides a thorough account of temporal logic, one of the most important areas of logic in computer science today. The book begins with a solid introduction to semantical and axiomatic approaches to temporal logic. It goes on to cover predicate temporal logic, meta-languages, general theories of axiomatization, many dimensional systems, propositional quantifiers, expressive power, Henkin dimension, temporalization of other logics, and decidability results. With its inclusion of cutting-edge results and unifying (...) methodologies, this book is an indispensable reference for both the pure logician and the theoretical computer scientist. (shrink)

Much previous work in artificial intelligence has neglected representing time in all its complexity. In particular, it has neglected continuous change and the indeterminacy of the future. To rectify this, I have developed a first‐order temporal logic, in which it is possible to name and prove things about facts, events, plans, and world histories. In particular, the logic provides analyses of causality, continuous change in quantities, the persistence of facts (the frame problem), and the relationship between tasks (...) and actions. It may be possible to implement a temporal‐inference machine based on this logic, which keeps track of several “maps” of a time line, one per possible history. (shrink)

This work concerns the use of operators for past and future contingency in Priorean temporal logic. We will develop a system named C_t, whose language includes a propositional constant and prove that (I) C_t is complete with respect to a certain class of general frames and (II) the usual operators for past and future necessity are definable in such system. Furthermore, we will introduce the extension C_t(lin) that can be interpreted on linear and transitive general frames. The theoretical (...) result of the current work is that contingency can be treated as a primitive notion in reasoning about temporal modalities. (shrink)

ABSTRACT A complete axiomatic system CTLrp is introduced for a temporal logic for finitely branching ω+ -trees in a language extended with so called reference pointers. Syntactic and semantic interpretations are constructed for the branching time computation tree logic CTL* into CTLrp. In particular, that yields a complete axiomatization for the translations of all valid CTL*-formulae. Thus, the temporal logic with reference pointers is brought forward as a simpler (with no path quantifiers), but in a (...) way more expressive medium for reasoning about branching time. (shrink)

A complete axiomatic system CTL$_{rp}$ is introduced for a temporal logic for finitely branching $\omega^+$-trees in a temporal language extended with so called reference pointers. Syntactic and semantic interpretations are constructed for the branching time computation tree logic CTL$^{*}$ into CTL$_{rp}$. In particular, that yields a complete axiomatization for the translations of all valid CTL$^{*}$-formulae. Thus, the temporal logic with reference pointers is brought forward as a simpler (with no path quantifiers), but in a (...) way more expressive medium for reasoning about branching time. (shrink)

This paper investigates modular combinations of temporal logic systems. Four combination methods are described and studied with respect to the transfer of logical properties from the component one-dimensional temporal logics to the resulting combined two-dimensional temporal logic. Three basic logical properties are analyzed, namely soundness, completeness, and decidability. Each combination method comprises three submethods that combine the languages, the inference systems, and the semantics of two one-dimensional temporal logic systems, generating families of two-dimensional (...) temporal languages with varying expressivity and varying degrees of transfer of logical properties. The temporalization method and the independent combination method are shown to transfer all three basic logical properties. The method of full join of logic systems generates a considerably more expressive language but fails to transfer completeness and decidability in several cases. So a weaker method of restricted join is proposed and shown to transfer all three basic logical properties. (shrink)

Temporal Logic: From Ancient Ideas to Artificial Intelligence deals with the history of temporal logic as well as the crucial systematic questions within the field. The book studies the rich contributions from ancient and medieval philosophy up to the downfall of temporal logic in the Renaissance. The modern rediscovery of the subject, which is especially due to the work of A. N. Prior, is described, leading into a thorough discussion of the use of (...) class='Hi'>temporal logic in computer science and the understanding of natural language. Temporal Logic: From Ancient Ideas to Artificial Intelligence thus interweaves linguistic, philosophical and computational aspects into an informative and inspiring whole. (shrink)

In this paper, we study temporal logic for finite linear structures and surjective bounded morphisms between them. We give a characterisation of such structures by modal formulas and show that every pair of linear structures with a bounded morphism between them can be uniquely characterised by a temporal formula up to an isomorphism. As the main result, we prove Kripke completeness of the logic with respect to the class of finite linear structures with bounded morphisms between (...) them. (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)

While specifications and verifications of concurrent systems employ Linear Temporal Logic , it is increasingly likely that logical consequence in image will be used in the description of computations and parallel reasoning. Our paper considers logical consequence in the standard image with temporal operations image and image . The prime result is an algorithm recognizing consecutions admissible in image, so we prove that image is decidable w.r.t. admissible inference rules. As a consequence we obtain algorithms verifying the (...) validity of consecutions in image and solving the satisfiability problem. We start by a simple reduction of logical consecutions of image to equivalent ones in the reduced normal form . Then we apply a semantic technique based on image-Kripke structures with formula definable subsets. This yields necessary and sufficient conditions for a consecution to be not admissible in image. These conditions lead to an algorithm which recognizes consecutions admissible in image by verifying the validity of consecutions in special finite Kripke structures of size square polynomial in reduced normal forms of the consecutions. As a consequence, this also solves the satisfiability problem for image. (shrink)

One of time's most puzzling aspects concerns its ontological status: on the one hand, it is a subjective and relative notion, based on our conscious experience of successive events; yet, on the other hand, our civilization and technology are based on the understanding that something like objective, absolute Time exists. Some philosophers have taken this paradox so far as to conclude that time is unreal; others, accepting the existence of absolute time, have engaged in heated debates regarding its structure, be (...) it linear or circular, bounded or unbounded, dense or discrete. (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.

This volume constitutes the proceedings of the First International Conference on Temporal Logic (ICTL '94), held at Bonn, Germany in July 1994. Since its conception as a discipline thirty years ago, temporal logic is studied by many researchers of numerous backgrounds; presently it is in a stage of accelerated dynamic growth. This book, as the proceedings of the first international conference particularly dedicated to temporal logic, gives a thorough state-of-the-art report on all aspects of (...) temporal logic research relevant for computer science and AI. It contains 27 technical contributions carefully selected for presentation at ICTL '94 as well as three surveys and position papers. (shrink)

I present a variant of with time, called, interpreted in standard Kripke semantics. On the syntactic level, is nothing but the extension of atemporal individual by: the future tense and past tense operators, and the operator of group agency for the grand coalition. A sound and complete axiomatisation for is given. Moreover, it is shown that supports reasoning about interesting normative concepts such as the concepts of achievement obligation and commitment.

We introduce and study hierarchies of extensions of the propositional modal and temporal languages with pairs of new syntactic devices: point of reference-reference pointer which enable semantic references to be made within a formula. We propose three different but equivalent semantics for the extended languages, discuss and compare their expressiveness. The languages with reference pointers are shown to have great expressive power (especially when their frugal syntax is taken into account), perspicuous semantics, and simple deductive systems. For instance, Kamp's (...) and Stavi's temporal operators, as well as nominals (names, clock variables), are definable in them. Universal validity in these languages is proved undecidable. The basic modal and temporal logics with reference pointers are uniformly axiomatized and a strong completeness theorem is proved for them and extended to some classes of their extensions. (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.

Hybridization is a method invented by Arthur Prior for extending the expressive power of modal languages. Although developed in interesting ways by Robert Bull, and by the Sofia school , the method remains little known. In our view this has deprived temporal logic of a valuable tool.The aim of the paper is to explain why hybridization is useful in temporal logic. We make two major points, the first technical, the second conceptual. First, we show that hybridization (...) gives rise to well-behaved logics that exhibit an interesting synergy between modal and classical ideas. This synergy, obvious for hybrid languages with full first-order expressive strength, is demonstrated for a weaker local language capable of defining the Until operator; we provide a minimal axiomatization, and show that in a wide range of temporally interesting cases extended completeness results can be obtained automatically. Second, we argue that the idea of sorted atomic symbols which underpins the hybrid enterprise can be developed further. To illustrate this, we discuss the advantages and disadvantages of a simple hybrid language which can quantify over paths. (shrink)

A succession of events is a sequence of events such that after one event is finished, the next one occurs successively. In this paper, we extended linear temporal logic with a new modality to capture the case that a sequence of events successively occurs. We compared the expressivity between this extended linear temporal logic and the standard linear temporal logic.

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. (shrink)

Temporal logic as a modern discipline is separate from classical logic; it is seen as an addition or expansion of the more basic propositional and predicate logics. This approach is in contrast with logic in the Middle Ages, which was primarily intended as a tool for the analysis of natural language. Because all natural language sentences have tensed verbs, medieval logic is inherently a temporal logic. This fact is most clearly exemplified in medieval (...) theories of supposition. As a case study, we look at the supposition theory of Lambert of Lagny, extracting from it a temporal logic and providing a formalization of that logic. (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 language of linear temporal logic can be interpreted on the class of dynamic topological systems, giving rise to the intuitionistic temporal logic ${\sf ITL}^{\sf c}_{\Diamond \forall }$, recently shown to be decidable by Fernández-Duque. In this article we axiomatize this logic, some fragments, and prove completeness for several familiar spaces.

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)

We introduce a two‐dimensional metric (interval) temporal logic whose internal and external time flows are dense linear orderings. We provide a suitable semantics and a sequent calculus with axioms for equality and extralogical axioms. Then we prove completeness and a semantic partial cut elimination theorem down to formulas of a certain type.

It is shown that the decision problem for the temporal logic with until and since connectives over real-numbers time is PSPACE-complete. This is the most practically useful dense time temporal logic.

Linear temporal logic is a widely used method for verification of model checking and expressing the system specifications. The relationship between theory of automata and logic had a great influence in the computer science. Investigation of the relationship between quantum finite automata and linear temporal logic is a natural goal. In this paper, we present a construction of quantum finite automata on finite words from linear-time temporal logic formulas. Further, the relation between quantum (...) finite automata and linear temporal logic is explored in terms of language recognition and acceptance probability. We have shown that the class of languages accepted by quantum finite automata are definable in linear temporal logic, except for measure-once one-way quantum finite automata. (shrink)

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.

A new combined temporal logic called synchronized linear-time temporal logic (SLTL) is introduced as a Gentzen-type sequent calculus. SLTL can represent the n -Cartesian product of the set of natural numbers. The cut-elimination and completeness theorems for SLTL are proved. Moreover, a display sequent calculus δ SLTL is defined.