Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao https://doi.org/10.1...arrow_drop_down
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
https://doi.org/10.1017/cbo978...
Part of book or chapter of book . 2016 . Peer-reviewed
License: Cambridge Core User Agreement
Data sources: Crossref
versions View all 1 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Linear-Time Temporal Logics

Authors: Martin Lange; Valentin Goranko; Stéphane Demri;

Linear-Time Temporal Logics

Abstract

Linear-time temporal logics formalise reasoning about single computations in transition systems, represented by linear models over natural numbers, that is, infinite sequences of states of length ω . With linear-time formulae one can specify a rich variety of important properties of infinite computations; not only local ones, like BML, but also related to their limit behaviour , such as safety, liveness or fairness. In fact, a classical result by Hans Kamp implies that the most popular linear-time logic LTL, which will be introduced and studied in this chapter, is as expressive as first-order logic on single computations Kamp (1968). Alinear-time formula is normally used in order to specify a property for all computations in a given interpreted transition system, reflecting the view of a program as the collection of all its possible executions. This means that LTL cannot express basic branching-time properties, so the expressiveness of LTL on nonlinear transition systems is incomparable to the one of BML (see Chapter 10). In this chapter we present and study the linear-time logic LTL and some of its most interesting extensions: with past-time operators, automata-based operators, propositional quantification, etc. We will focus on the logical and computational properties of these logics, viz. their semantics, expressiveness, model checking and testing of satisfiability and validity. We will establish the fundamental ultimately periodic model property of LTL: every satisfiable formula of that logic is satisfiable in an ultimately periodic linear model, that is, in a computation that, after a certain initial segment, starts repeating forever. Moreover, effective upper bounds, in the worst-case exponential in the length of the formula, can be computed for the length of both the initial segment and the period. Thus, the ultimately periodicmodel property implies decidability of the satisfiablity (and, hence, of validity, too) in LTL and provides a decision method for that problem. Eventually, that method can be refined and transformed into an optimal decision procedure which will be presented here. Alternative decision procedures, essentially using the same property but based respectively on tablehis chapter we present and study the linear-time logic LTL and some of its most interesting extensions: with past-time operators, automata-based operators, propositional quantification, etc.

  • BIP!
    Impact byBIP!
    citations
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
citations
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!