Science Fair Project Encyclopedia

Science Fair Project Encyclopedia Contents Page

Categories: Theoretical computer science

Stuttering equivalence

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 $k th$ block of one path are labeled ( $L(\sdot)$ ) the same as states in the $k th$ 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.

Categories: Theoretical computer science

Last updated: 05-27-2005 18:06:08

Science Fair Project Encyclopedia Contents Page

10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details

All Science Fair Projects

Science Fair Project Encyclopedia for Schools!

Science Fair Project Encyclopedia

Stuttering equivalence