Simulation (computer science). In theoretical computer science a simulation is a relation between state transition systems associating systems that behave in the same way in the sense that one system simulates the other.

Intuitively, a system simulates another system if it can match all of its moves.

The basic definition relates states within one transition system, but this is easily adapted to relate two separate transition systems by building a system consisting of the disjoint union of the corresponding components.

Formal definition
Given a labelled state transition system (, , →),
where  is a set of states,  is a set of labels and → is a set of labelled transitions (i.e., a subset of ),
a relation  is a simulation if and only if for every pair of states  in  and all labels λ in :

 if , then there is  such that 

Equivalently, in terms of relational composition:

Given two states  and  in ,  can be simulated by , written , if and only if there is a simulation  such that . The relation  is called the simulation preorder, and it is the union of all simulations:  precisely when  for some simulation .

The set of simulations is closed under union; therefore, the simulation preorder is itself a simulation. Since it is the union of all simulations, it is the unique largest simulation. Simulations are also closed under reflexive and transitive closure; therefore, the largest simulation must be reflexive and transitive. From this follows that the largest simulation—the simulation preorder—is indeed a preorder relation. Note that there can be more than one relation that is both a simulation and a preorder; the term simulation preorder refers to the largest one of them (which is a superset of all the others).

Two states  and  are said to be similar, written , if and only if  can be simulated by  and  can be simulated by . Similarity is thus the maximal symmetric subset of the simulation preorder, which means it is reflexive, symmetric, and transitive; hence an equivalence relation. However, it is not necessarily a simulation, and precisely in those cases when it is not a simulation, it is strictly coarser than bisimilarity (meaning it is a superset of bisimilarity).
To witness, consider a similarity that is a simulation. Since it is symmetric, it is a bisimulation. It must then be a subset of bisimilarity, which is the union of all bisimulations. Yet it is easy to see that similarity is always a superset of bisimilarity. From this follows that if similarity is a simulation, it equals bisimilarity. And if it equals bisimilarity, it is naturally a simulation (since bisimilarity is a simulation). Therefore, similarity is a simulation if and only if it equals bisimilarity. If it does not, it must be its strict superset; hence a strictly coarser equivalence relation.

Similarity of separate transition systems
When comparing two different transition systems (S', Λ', →') and (S", Λ", →"), the basic notions of simulation and similarity can be used by forming the disjoint composition of the two machines, (S, Λ, →) with S = S' ∐ S", Λ = Λ' ∪ Λ" and → = →' ∪ →", where ∐ is the disjoint union operator between sets.

See also
 State transition system
 Bisimulation
 Coinduction
 Operational semantics

Notes

References 
 
 

Theoretical computer science
Transition systems