Composing Implementations

This implies that any correct run of the imple-mentation that stutters indefinitely has infinitely many opportunities to activatethe specification. Under the standard assumption that an opportunity that ispresented infinitely often is eventually seized, a live implementation does notdeadlock as it eventually activates the specification.

Live

Complete

Safe

implementedtransition system (henceforth – specification),

An implementation is correct if it is safe, complete and live.

Given two transition systems T S = (S, s0, T ) and T S′ = (S′, s′0, T ′) an im-plementation of T S by T S′ is a function σ : S′ → S where σ(s′0) = s0.

empty if s = s′

Also note that T and T f are not necessarydisjoint, for the same reason that even a broken clock shows the correct houronce in a while

We denote by s ∗−→ s′ ∈ T the existence of a correctcomputation (empty if s = s′) from s to s′

A transition in T f \ T is faulty, and a computation is faulty if it

A transition s → s′ ∈ T is correct, and a computation of correct transitionsis correct.

a run of T S is a computation that starts froms0.

A computation of T S is a sequenceof transitions s −→ s′ −→ · · · ,

Atransition system T S = (S, s0, T, T f ) consists of a set of states S, an initialstate s0 ∈ S, a set of (correct) transitions T ⊆ S2 and a set of faulty transitionsT f ⊆ S2. If T f = ∅ then it may be omitted

the transitions over S are all pairs (s, s′) ∈ S2, also written s → s′.

Given a set S, referred to asstates,

→