{
  "id": "enwiki-001374639842",
  "slug": "bisimulation",
  "title": "Bisimulation",
  "qid": "",
  "lead": "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.",
  "body": "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. ==Further reading== ==External links==",
  "categories": [
    "107802972",
    "20284999",
    "22936995",
    "22960150",
    "23603337",
    "24043274",
    "25574325",
    "26220375",
    "29050536"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1374639842",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1789276302.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001374639842",
    "type": "webpage",
    "title": "Bisimulation",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/bisimulation",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001374639842",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1374639842",
    "note": "Immutable snapshot enwiki-001374639842"
  }
}