Computation Tree Logic

The Computation Tree Logic ( CTL short ) is a temporal logic, which is specifically designed for the specification and verification of computer systems. A specific generalization to the logic described below, for which the name has CTL is designated as CTL *. CTL then it denotes a subset of CTL * formulas. Another important special subset of CTL * is the Linear Temporal Logic ( LTL short ).

As generally in temporal logics is not about the description of temporal processes (that would be the real-time logic), but the properties of states and their change in system processes. LTL, CTL and CTL * are extensions of propositional logic.

Syntax and Semantics

Atomic statements

(see also the section " Colloquial Introduction " in the article propositional logic )

The starting point are properties of states. Is AP a set of atomic propositions ( assertions ), every element p of AP is a state formula. Each p AP is a mapping from the set of states in the set of truth values ​​{ true, false }. They say a state s satisfies a p from AP iff.

Boolean operators

From the atomic formulas of propositional logic formulas can now be constructed. Through the unary operator and the double-digit operators, as with the usual propositional logic formulas in the new meaning of NOT, AND, OR, IMPLICATION and EQUIVALENCE be formed.

Temporaloperatoren

Instead of individual states can now consider infinite sequences of such states and define it a semantics. The formulas defined so far are satisfied by a path if the first state of the path they met. These formulas are now expanded by the following unary operations:

  • X for the immediately following state (English: neXt state)
  • F for sometime following state (English: some Future state)
  • G for all of the following conditions (English: Globally )

And the two double-digit operators:

  • U for up to reaching the state (English: Until )
  • R (English: Release)

Rarely does one define additionally the past tenses:

  • P for previous, (English: previous )
  • O for Once Upon a Time (English: once)
  • B was always (English: always completed )
  • S for since (English: since ).

Paths meet these formulas now iff ( colloquial)

For a given sequence of states, the operators are formally defined as follows:

For F, G and U is the premise of " future includes the present with a " valid, ie A formula is met in one of the following conditions, the same applies to the start state. The formulas defined here to form the so-called path formulas and the already above mentioned Linear Time Temporal Logic.

Pfadquantoren

Instead paths and trees of states can be considered, which are infinitely deep in each branch. To a path formula can be with the quantifiers for E along (at least) a path (English: exists ): win state formulas for along all paths (always in English ) and A. A tree satisfies E iff there is a path starting at the root of this, the met. A tree satisfies A if and only if every path starting at the root met.

The so- defined logic now forms CTL *.

The subset of CTL

For this logic, one can still define a subset, which is called as already mentioned above CTL. These occur when each Temporaloperator is quantified by exactly one path quantifier. CTL is therefore formed from the atomic state statements, the Boolean operators and pairs of path quantifier and Temporaloperator ( in that order). The propositional logic is thus extended by the operators:

  • EX ( in (at least ) the next condition is true )
  • EF ( in (at least ) one of the following conditions apply )
  • EC (there are (at least ) a path, such that along the entire path )
  • E [ U] ( there is a path for which is: to the first occurrence of otherwise),
  • AX ( applicable in all next state )
  • AF ( always to a state that satisfies )
  • AG ( on all paths applicable in each state ) and
  • A [ U] ( it is always up to the first occurrence of ).

If these operators are used as a starting point for a fixed point determination, it is sufficient to limit the number of operators through transformations to these three:

This is the case because the following equivalences apply:

Specification (technical standard) Propositional calculus
199383
de