| Simulation Preorder |
Article Index for Simulation |
Website Links For Simulation |
Information AboutSimulation Preorder |
| CATEGORIES ABOUT SIMULATION PREORDER | |
| theoretical computer science | |
|
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 (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. 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. In such a case, p and q are said to be ''similar'' and ≤ is called the ''similarity'' relation. The similarity relation ≤ is a Preorder . Furthermore, it is the largest simulation relation over a given transition system. 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 |
|
|