Linear temporal logic

From Wikipedia, the free encyclopedia
(Redirected from Linear Temporal Logic)

In logic, linear temporal logic or linear-time temporal logic[1][2] (LTL) is a modal temporal logic with modalities referring to time. In LTL, one can encode formulae about the future of paths, e.g., a condition will eventually be true, a condition will be true until another fact becomes true, etc. It is a fragment of the more complex CTL*, which additionally allows branching time and quantifiers. LTL is sometimes called propositional temporal logic, abbreviated PTL.[3] In terms of expressive power, linear temporal logic (LTL) is a fragment of first-order logic.[4][5]

LTL was first proposed for the formal verification of computer programs by Amir Pnueli in 1977.[6]

Syntax[edit]

LTL is built up from a finite set of propositional variables AP, the logical operators ¬ and ∨, and the temporal modal operators X (some literature uses O or N) and U. Formally, the set of LTL formulas over AP is inductively defined as follows:

  • if pAP then p is an LTL formula;
  • if ψ and φ are LTL formulas then ¬ψ, φ ∨ ψ, X ψ, and φ U ψ are LTL formulas.[7]

X is read as next and U is read as until. Other than these fundamental operators, there are additional logical and temporal operators defined in terms of the fundamental operators, in order to write LTL formulas succinctly. The additional logical operators are ∧, →, ↔, true, and false. Following are the additional temporal operators.

  • G for always (globally)
  • F for finally
  • R for release
  • W for weak until
  • M for mighty release

Semantics[edit]

An LTL formula can be satisfied by an infinite sequence of truth valuations of variables in AP. These sequences can be viewed as a word on a path of a Kripke structure (an ω-word over alphabet 2AP). Let w = a0,a1,a2,... be such an ω-word. Let w(i) = ai. Let wi = ai,ai+1,..., which is a suffix of w. Formally, the satisfaction relation ⊨ between a word and an LTL formula is defined as follows:

  • wp if pw(0)
  • w ⊨ ¬ψ if wψ
  • wφψ if wφ or wψ
  • wX ψ if w1ψ (in the next time step ψ must be true)
  • wφ U ψ if there exists i ≥ 0 such that wiψ and for all 0 ≤ k < i, wkφ (φ must remain true until ψ becomes true)

We say an ω-word w satisfies an LTL formula ψ when wψ. The ω-language L(ψ) defined by ψ is {w | wψ}, which is the set of ω-words that satisfy ψ. A formula ψ is satisfiable if there exist an ω-word w such that wψ. A formula ψ is valid if for each ω-word w over alphabet 2AP, we have wψ.

The additional logical operators are defined as follows:

  • φψ ≡ ¬(¬φ ∨ ¬ψ)
  • φψ ≡ ¬φψ
  • φψ ≡ (φψ) ∧ ( ψφ)
  • truep ∨ ¬p, where pAP
  • false ≡ ¬true

The additional temporal operators R, F, and G are defined as follows:

  • ψ R φ ≡ ¬(¬ψ U ¬φ) ( φ remains true until and including once ψ becomes true. If ψ never becomes true, φ must remain true forever. ψ releases φ.)
  • F ψtrue U ψ (eventually ψ becomes true)
  • G ψfalse R ψ ≡ ¬F ¬ψ (ψ always remains true)

Weak until and strong release[edit]

Some authors also define a weak until binary operator, denoted W, with semantics similar to that of the until operator but the stop condition is not required to occur (similar to release).[8] It is sometimes useful since both U and R can be defined in terms of the weak until:

  • ψ W φ ≡ (ψ U φ) ∨ G ψψ U (φG ψ) ≡ φ R (φψ)
  • ψ U φFφ ∧ (ψ W φ)
  • ψ R φφ W (φψ)

The strong release binary operator, denoted M, is the dual of weak until. It is defined similar to the until operator, so that the release condition has to hold at some point. Therefore, it is stronger than the release operator.

  • ψ M φ ≡ ¬(¬ψ W ¬φ) ≡ (ψ R φ) ∧ F ψψ R (φF ψ) ≡ φ U (ψφ)

The semantics for the temporal operators are pictorially presented as follows.

Textual Symbolic Explanation Diagram
Unary operators:
X φ neXt: φ has to hold at the next state. LTL next operator
F φ Finally: φ eventually has to hold (somewhere on the subsequent path). LTL eventually operator
G φ Globally: φ has to hold on the entire subsequent path. LTL always operator
Binary operators:
ψ U φ Until: ψ has to hold at least until φ becomes true, which must hold at the current or a future position. LTL until operator
ψ R φ Release: φ has to be true until and including the point where ψ first becomes true; if ψ never becomes true, φ must remain true forever. LTL release operator (which stops)

LTL release operator (which does not stop)

ψ W φ Weak until: ψ has to hold at least until φ; if φ never becomes true, ψ must remain true forever. LTL weak until operator (which stops)

LTL weak until operator (which does not stop)

ψ M φ Strong release: φ has to be true until and including the point where ψ first becomes true, which must hold at the current or a future position. LTL strong release operator

Equivalences[edit]

Let φ, ψ, and ρ be LTL formulas. The following tables list some of the useful equivalences that extend standard equivalences among the usual logical operators.

Distributivity
X (φ ∨ ψ) ≡ (X φ) ∨ (X ψ) X (φ ∧ ψ) ≡ (X φ) ∧ (X ψ) XU ψ)≡ (X φ) U (X ψ)
F (φ ∨ ψ) ≡ (F φ) ∨ (F ψ) G (φ ∧ ψ) ≡ (G φ) ∧ (G ψ)
ρ U (φ ∨ ψ) ≡ (ρ U φ) ∨ (ρ U ψ) (φ ∧ ψ) U ρ ≡ (φ U ρ) ∧ (ψ U ρ)
Negation propagation
X is self-dual F and G are dual U and R are dual W and M are dual
¬X φ ≡ X ¬φ ¬F φ ≡ G ¬φ ¬ (φ U ψ) ≡ (¬φ R ¬ψ) ¬ (φ W ψ) ≡ (¬φ M ¬ψ)
¬G φ ≡ F ¬φ ¬ (φ R ψ) ≡ (¬φ U ¬ψ) ¬ (φ M ψ) ≡ (¬φ W ¬ψ)
Special temporal properties
F φ ≡ F F φ G φ ≡ G G φ φ U ψ ≡ φ UU ψ)
φ U ψ ≡ ψ ∨ ( φ ∧ XU ψ) ) φ W ψ ≡ ψ ∨ ( φ ∧ XW ψ) ) φ R ψ ≡ ψ ∧ (φ ∨ XR ψ) )
G φ ≡ φ ∧ X(G φ) F φ ≡ φ ∨ X(F φ)

Negation normal form[edit]

All the formulas of LTL can be transformed into negation normal form, where

  • all negations appear only in front of the atomic propositions,
  • only other logical operators true, false, ∧, and ∨ can appear, and
  • only the temporal operators X, U, and R can appear.

Using the above equivalences for negation propagation, it is possible to derive the normal form. This normal form allows R, true, false, and ∧ to appear in the formula, which are not fundamental operators of LTL. Note that the transformation to the negation normal form does not blow up the length of the formula. This normal form is useful in translation from an LTL formula to a Büchi automaton.

Relations with other logics[edit]

LTL can be shown to be equivalent to the monadic first-order logic of order, FO[<]—a result known as Kamp's theorem[9] or equivalently to star-free languages.[10]

Computation tree logic (CTL) and linear temporal logic (LTL) are both a subset of CTL*, but are incomparable. For example,

  • No formula in CTL can define the language that is defined by the LTL formula F(G p).
  • No formula in LTL can define the language that is defined by the CTL formulas AG( p → (EXq ∧ EX¬q) ) or AG(EF(p)).

Computational problems[edit]

Model checking and satisfiability against an LTL formula are PSPACE-complete problems. LTL synthesis and the problem of verification of games against an LTL winning condition is 2EXPTIME-complete.[11]

Applications[edit]

Automata-theoretic linear temporal logic model checking
An important way to model check is to express desired properties (such as the ones described above) using LTL operators and actually check if the model satisfies this property. One technique is to obtain a Büchi automaton that is equivalent to the model (accepts an ω-word precisely if it is the model) and another one that is equivalent to the negation of the property (accepts an ω-word precisely it satisfies the negated property) (cf. Linear temporal logic to Büchi automaton). The intersection of the two non-deterministic Büchi automata is empty if and only if the model satisfies the property.[12]
Expressing important properties in formal verification
There are two main types of properties that can be expressed using linear temporal logic: safety properties usually state that something bad never happens (G¬ϕ), while liveness properties state that something good keeps happening (GFψ or G(ϕFψ)).[13] More generally, safety properties are those for which every counterexample has a finite prefix such that, however it is extended to an infinite path, it is still a counterexample. For liveness properties, on the other hand, every finite path can be extended to an infinite path that satisfies the formula.
Specification language
One of the applications of linear temporal logic is the specification of preferences in the Planning Domain Definition Language for the purpose of preference-based planning.[citation needed]

Extensions[edit]

Parametric linear temporal logic extends LTL with variables on the until-modality.[14]

See also[edit]

References[edit]

  1. ^ Logic in Computer Science: Modelling and Reasoning about Systems: page 175
  2. ^ "Linear-time Temporal Logic". Archived from the original on 2017-04-30. Retrieved 2012-03-19.
  3. ^ Dov M. Gabbay; A. Kurucz; F. Wolter; M. Zakharyaschev (2003). Many-dimensional modal logics: theory and applications. Elsevier. p. 46. ISBN 978-0-444-50826-3.
  4. ^ Diekert, Volker. "First-order Definable Languages" (PDF). University of Stuttgart.
  5. ^ Kamp, Hans (1968). Tense Logic and the Theory of Linear Order (PhD). University of California Los Angeles.
  6. ^ Amir Pnueli, The temporal logic of programs. Proceedings of the 18th Annual Symposium on Foundations of Computer Science (FOCS), 1977, 46–57. doi:10.1109/SFCS.1977.32
  7. ^ Sec. 5.1 of Christel Baier and Joost-Pieter Katoen, Principles of Model Checking, MIT Press "Principles of Model Checking - the MIT Press". Archived from the original on 2010-12-04. Retrieved 2011-05-17.
  8. ^ Sec. 5.1.5 "Weak Until, Release, and Positive Normal Form" of Principles of Model Checking.
  9. ^ Abramsky, Samson; Gavoille, Cyril; Kirchner, Claude; Spirakis, Paul (2010-06-30). Automata, Languages and Programming: 37th International Colloquium, ICALP ... - Google Books. ISBN 9783642141614. Retrieved 2014-07-30.
  10. ^ Moshe Y. Vardi (2008). "From Church and Prior to PSL". In Orna Grumberg; Helmut Veith (eds.). 25 years of model checking: history, achievements, perspectives. Springer. ISBN 978-3-540-69849-4. preprint
  11. ^ A. Pnueli and R. Rosner. "On the synthesis of a reactive module" In Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of programming languages (POPL '89). Association for Computing Machinery, New York, NY, USA, 179–190. https://doi.org/10.1145/75277.75293
  12. ^ Moshe Y. Vardi. An Automata-Theoretic Approach to Linear Temporal Logic. Proceedings of the 8th Banff Higher Order Workshop (Banff'94). Lecture Notes in Computer Science, vol. 1043, pp. 238–266, Springer-Verlag, 1996. ISBN 3-540-60915-6.
  13. ^ Bowen Alpern, Fred B. Schneider, Defining Liveness, Information Processing Letters, Volume 21, Issue 4, 1985, Pages 181-185, ISSN 0020-0190, https://doi.org/10.1016/0020-0190(85)90056-0
  14. ^ Chakraborty, Souymodip; Katoen, Joost-Pieter (2014). Diaz, Josep; Lanese, Ivan; Sangiorgi, Davide (eds.). "Parametric LTL on Markov Chains". Theoretical Computer Science. Lecture Notes in Computer Science. 7908. Springer Berlin Heidelberg: 207–221. arXiv:1406.6683. Bibcode:2014arXiv1406.6683C. doi:10.1007/978-3-662-44602-7_17. ISBN 978-3-662-44602-7. S2CID 12538495.

External links[edit]