Stuttering Equivalence

Stephan Merz 1
1 VERIDIS - Modeling and Verification of Distributed Algorithms and Systems
LORIA - FM - Department of Formal Methods , Inria Nancy - Grand Est, MPII - Max-Planck-Institut für Informatik
Abstract : Two omega-sequences are stuttering equivalent if they differ only by finite repetitions of elements. Stuttering equivalence is a fundamental concept in the theory of concurrent and distributed systems. Notably, Lamport argues that refinement notions for such systems should be insensitive to finite stuttering. Peled and Wilke show that all LTL (linear-time temporal logic) properties that are insensitive to stuttering equivalence can be expressed without the next-time operator. Stuttering equivalence is also important for certain verification techniques such as partial-order reduction for model checking. We formalize stuttering equivalence in Isabelle/HOL. Our development relies on the notion of a stuttering sampling function that identifies blocks of identical sequence elements.
Document type :
Reports
Liste complète des métadonnées

https://hal.inria.fr/hal-00760690
Contributor : Stephan Merz <>
Submitted on : Tuesday, December 4, 2012 - 11:43:19 AM
Last modification on : Tuesday, February 19, 2019 - 3:40:03 PM

Identifiers

  • HAL Id : hal-00760690, version 1

Collections

Citation

Stephan Merz. Stuttering Equivalence. [Research Report] 2012. ⟨hal-00760690⟩

Share

Metrics

Record views

218