Bisimulation

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 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 bisimulation is a binary relation between state transition systems, associating systems that behave in the same way in that one system simulates the other and vice versa. Intuitively two systems are bisimilar if they, assuming we view them as playing a game according to some rules, match each other's moves. In this sense, each of the systems cannot be distinguished from the other by an observer.

In theoretical computer science, a bisimulation is a binary relation between state transition systems, associating systems that behave in the same way in that one system simulates the other and vice versa. Intuitively two systems are bisimilar if they, assuming we view them as playing a game according to some rules, match each other's moves.

In this sense, each of the systems cannot be distinguished from the other by an observer. R\ ;\ \overset{\lambda}{\rightarrow}\quad {\subseteq}\quad \overset{\lambda}{\rightarrow}\ ;\ R and R^{-1}\ ;\ \overset{\lambda}{\rightarrow}\quad {\subseteq}\quad \overset{\lambda}{\rightarrow}\ ;\ R^{-1} From the monotonicity and continuity of relation composition, it follows immediately that the set of bisimulations is closed under unions (joins in the poset of relations), and a simple algebraic calculation shows that the relation of bisimilarity—the join of all bisimulations—is an equivalence relation.

This definition, and the associated treatment of bisimilarity, can be interpreted in any involutive quantale. \forall \lambda\in \Lambda. \, \forall p' \in S. \, p \overset{\lambda}{\rightarrow} p' \, \Rightarrow \, \exists q' \in S. \, q \overset{\lambda}{\rightarrow} q' \,\textrm{ and }\, (p',q') \in R and \forall \lambda\in \Lambda. \, \forall q' \in S. \, q \overset{\lambda}{\rightarrow} q' \, \Rightarrow \, \exists p' \in S. \, p \overset{\lambda}{\rightarrow} p' \,\textrm{ and }\, (p',q') \in R Bisimilarity is then defined to be the greatest fixed point of F . (p,q) \overset{\lambda}{\rightarrow} (p',q) or (p,q) \overset{\lambda}{\rightarrow} (p,q') The "Defender" must then attempt to match that transition, \lambda from either (p',q) or (p,q') depending on the attacker's move. I.e., they must find an \lambda such that: (p',q) \overset{\lambda}{\rightarrow} (p',q') or (p,q') \overset{\lambda}{\rightarrow} (p',q') Attacker and defender continue to take alternating turns until: The defender is unable to find any valid transitions to match the attacker's move.

In this case the attacker wins. The game reaches states (p,q) that are both 'dead' (i.e., there are no transitions from either state) In this case the defender wins The game goes on forever, in which case the defender wins. The game reaches states (p,q) , which have already been visited.

This is equivalent to an infinite play and counts as a win for the defender. By the above definition the system is a bisimulation if and only if there exists a winning strategy for the defender. p \mapsto \{ (\lambda, q) \in \Lambda \times S : p \overset{\lambda}{\rightarrow} q \}.

Let \pi_i \colon S \times S \to S be i -th projection, mapping (p, q) to p and q respectively for i = 1, 2 ; and \mathcal{P}(\Lambda \times \pi_1) the forward image of \pi_1 defined by dropping the third component P \mapsto \{ (\lambda, p) \in \Lambda \times S : \exists q . (\lambda, p, q) \in P \} where P is a subset of \Lambda \times S \times S . Similarly for \mathcal{P}(\Lambda \times \pi_2) . Using the above notations, a relation R \subseteq S \times S is a bisimulation on a transition system (S, \Lambda, \rightarrow) if and only if there exists a transition system \gamma \colon R \to \mathcal{P}(\Lambda \times R) on the relation R such that the diagram commutes, i.e. for i = 1, 2 , the equations \xi_\rightarrow \circ \pi_i = \mathcal{P}(\Lambda \times \pi_i) \circ \gamma hold where \xi_{\rightarrow} is the functional representation of (S, \Lambda, \rightarrow) . \forall p, q. \quad (p,q) \in \mathcal{S} \Rightarrow p \stackrel{\tau}{\rightarrow} p' \Rightarrow \exists q' . \quad q \stackrel{\tau^\ast}{\rightarrow} q' \wedge (p',q') \in \mathcal{S} \forall p, q. \quad (p,q) \in \mathcal{S} \Rightarrow p \stackrel{a}{\rightarrow} p' \Rightarrow \exists q' . \quad q \stackrel{\tau^\ast a \tau^\ast}{\rightarrow} q' \wedge (p',q') \in \mathcal{S} This is closely related to the notion of bisimulation "up to" a relation.

Typically, if the state transition system gives the operational semantics of a programming language, then the precise definition of bisimulation will be specific to the restrictions of the programming language. Therefore, in general, there may be more than one kind of bisimulation (respectively bisimilarity) relationship depending on the context.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374639842 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.