Misplaced Pages

This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (July 2012) (Learn how and when to remove this message)

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

${\displaystyle \pi \sim _{st}\pi '}$,

can be seen as a partitioning of paths ${\displaystyle \pi }$ and ${\displaystyle \pi '}$ into blocks, so that states in the ${\displaystyle k^{\mathrm {th} }}$ block of one path are labeled (${\displaystyle L(\cdot )}$) the same as states in the ${\displaystyle k^{\mathrm {th} }}$ block of the other path. Corresponding blocks may have different lengths.

Formally, this can be expressed as two infinite paths ${\displaystyle \pi =s_{0},s_{1},\ldots }$ and ${\displaystyle \pi '=r_{0},r_{1},\ldots }$ being stuttering equivalent (${\displaystyle \pi \sim _{st}\pi '}$) if there are two infinite sequences of integers ${\displaystyle 0=i_{0}<i_{1}<i_{2}<\ldots }$ and ${\displaystyle 0=j_{0}<j_{1}<j_{2}<\ldots }$ such that for every block ${\displaystyle k\geq 0}$ holds ${\displaystyle 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/computation tree logic (branching time logic)(modal logic). So-called branching bisimulation has to be used.

References

1. Groote, Jan Friso; Vaandrager, Frits W. (1990). "An efficient algorithm for branching bisimulation and stuttering equivalence". In Paterson, Michael S. (ed.). Proceedings of the 17th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 443. Springer-Verlag. pp. 626–638. doi:10.1007/BFb0032063. ISBN 0-387-52826-1.

• v
• t
• e

• Formal methods
• Logic in computer science
• Theoretical computer science stubs