Get Simulation Preorder essential facts below. View Videos or join the Simulation Preorder discussion. Add Simulation Preorder to your PopFlock.com topic list for future reference or share this resource on social media.
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.
Given two states p and q in S, q simulates p, written p 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.
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.