Formal Definition
Given a labelled state transition system (S, Λ, →), a simulation relation is a binary relation R over S (i.e. R ⊆ S × S) such that for every pair of elements p, q ∈ S, if (p,q)∈ R then for all α ∈ Λ, and for all p' ∈ S,
implies that there is a q' ∈ S such that
and (p',q') ∈ R.
Equivalently, in terms of relational composition:
Given two states p and q in S, q simulates p, written p ≤ q if there is a simulation R such that (p, q) ∈ R. The relation ≤ is a preorder, and is usually called the simulation preorder. It is the largest simulation relation over a given transition system.
Two states p and q are said to be similar, written p ≤≥ q, if p simulates q and q simulates p. Similarity is an equivalence relation, but it is coarser than bisimilarity.
Read more about this topic: Simulation Preorder
Famous quotes containing the words formal and/or definition:
“I will not let him stir
Till I have used the approvèd means I have,
With wholesome syrups, drugs, and holy prayers,
To make of him a formal man again.”
—William Shakespeare (1564–1616)
“The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.”
—Jean Baudrillard (b. 1929)