{
  "id": "enwiki-001334467328",
  "slug": "stutter-bisimulation",
  "title": "Stutter bisimulation",
  "qid": "",
  "lead": "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.",
  "body": "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==",
  "categories": [
    "107802972",
    "20346051",
    "23468805",
    "23603337",
    "26220375"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1334467328",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1769190234.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001334467328",
    "type": "webpage",
    "title": "Stutter 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/stutter-bisimulation",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          17
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          17
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001334467328",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1334467328",
    "note": "Immutable snapshot enwiki-001334467328"
  }
}