Stuttering equivalence

From Wikipedia, the free encyclopedia

In theoretical computer science, stuttering equivalence, a relation written as

\pi\sim_{st}\pi',

can be seen as a partitioning of path π and π' into blocks, so that states in the kth block of one path are labeled (L(\sdot)) the same as states in the kth block of the other path. Corresponding blocks may have different lengths.

Formally, this can be expressed as two infinite paths \pi=s_0, s_1, \ldots and \pi'=r_0, r_1, \ldots which are stuttering equivalent (\pi \sim_{st} \pi') if there are two infinite sequences of integers 0 = i_0 < i_1 < i_2 < \ldots and 0 = j_0 < j_1 < j_2 < \ldots such that for every block k \geq 0 holds L(s_{i_k}) = L(s_{i_k+1}) = \ldots = L(s_{i_{k+1}-1}) = L(r_{j_k}) = L(r_{j_k+1}) = \ldots = L(r_{j_{k+1}-1}).

Stuttering equivalence is not the same as bisimulation, since bisimulation cannot capture the semantics of the 'eventually' (or 'finally') operator found in linear temporal/branching time logic (modal logic). So-called branching bisimulation has to be used.

 This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.