Temporal logic of actions

The temporal logic of actions ( TLA ) is a further development of the Temporal Logic (English temporal logic) and the logic of actions ( engl. logic of actions ). It was developed by Leslie Lamport.

The temporal logic of actions is part of the propositional calculus ( propositional logic engl. ) and is used in computer science for the specification, reasoning and verification of systems ( eg programs). A specification in TLA is a logical formula describing all possible and correct behavior of a system. Based on these logical formula systems can be checked for unwanted and desired properties.

Symbols

There are the symbols of Boolean algebra and other symbols

Syntax and Semantics

Boolean expression of constants, variables, and painted (English primed ) variables. An action in this case represents a relation between two states, Painted variables refer to the new state. Will meet a pair of states that an action A A step called.

Without crossed variables Enabled (Action )

Nichtboolescher expression of constants, variables describing a state

Infinite sequence of states

Below are Z, U states F state functions, actions A, F, G formulas p predicates v variables, and behavior.

Let f be a state function or a predicate, f ' is then the expression f in which all variables have been replaced by painted variables.

Is a stutter step which makes the value of the variable unchanged (English stuttering step).

Is a step of changing the state function.

For every action A a predicate Enabled A is defined. It is in a state only true if it is possible to run from this state an A step. that is, Enabled A is in state z true if a condition exists u so that an A step. In a behavior is a predicate true only if it is true in the first state.

Behavioral characteristics

A safety feature ensures that undesirable conditions will never be met.

A liveness property guarantees that desired conditions are eventually reached.

In a concurrent system, a distinction between weak and strong fairness. Weak fairness (English weak fairness, justice) means that an action must be executed infinitely often, if the execution of this after a certain point is always possible. Anders: If an action is executed only finitely often, so this is a behavior infinitely often not feasible. It ensures that the action is eventually executed or that its execution is impossible - even if only for a certain period of time.

Strong fairness (English strong fairness, compassion ) means an action that must be executed infinitely often, if the execution of this is infinitely often possible. Anders: If an action is executed only finitely often, so this is a behavior only finitely many feasible. It assures that the action is eventually executed or that the execution of which eventually become impossible for ever.

If a behavior strongly fair with respect to an action, it is also weakly fair for this action.

Illustration and example

Var x = 0, y = 0

DoParallel ({ x: = x 1 }, { y: = y 1 })

Top -standing program in pseudo code is to add in parallel processing ( non-deterministically ) either x or y 1.

To a TLA - to indicate specification, only the state functions and actions must be defined.

In this example, a ranging state is the initial state at the same time.

The parallel running additions can be described in two actions.

Fairness conditions yet to be specified at the end. SF as strong fairness and WF as weak fairness.

From these three components, we obtain the following TLA formula: