Stutter bisimulation

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In theoretical computer science, a stutter bisimulation is a relationship between two transition systems, abstract machines that model computation. It is defined coinductively and generalizes the idea of bisimulations. A bisimulation matches up the states of a machine such that transitions correspond; a stutter bisimulation allows transitions to be matched to finite path fragments.

In theoretical computer science, a stutter bisimulation is a relationship between two transition systems, abstract machines that model computation. It is defined coinductively and generalizes the idea of bisimulations. A bisimulation matches up the states of a machine such that transitions correspond; a stutter bisimulation allows transitions to be matched to finite path fragments.

Definition

In Principles of Model Checking, Baier and Katoen define a stutter bisimulation for a single transition system and later adapt it to a relation on two transition systems. A stutter bisimulation for \text{TS}=(S, \text{Act}, \to, I, \text{AP}, L) is a binary relation R on S such that for all (s 1 ,s 2 ) in R: s_1, s_2 have the same labels If s_1\to s_1' is a valid transition and (s_1',s_2)\not\in R then there exists a finite path fragment s_2u_1\cdots u_n s_2' ( n\ge 0 ) such that each pair (s_1, u_i) is in R and (s_1',s_2') is in R If s_2\to s_2' is a valid transition and (s_1,s_2')\not\in R is not then there exists a finite path fragment s_1v_1\cdots v_n s_1' ( n\ge 0 ) such that each pair (v_i, s_2) is in R and (s_1',s_2') is in R

Generalizations

A generalization, the divergent stutter bisimulation, can be used to simplify the state space of a system with the tradeoff that statements using the linear temporal logic operator "next" may change truth value. A robust stutter bisimulation allows uncertainty over transitions in the system.

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1334467328 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.