Abstract. The simulation preorder for labeled transition systems is de ned locally as a game that relates states with their immediate successor states. Liveness assumptions about transition systems are typically modeled using fairness constraints. Existing notions of simulation for fair transition systems, however, are not local, and as a result, many appealing properties of the simulation preorder are lost. We extend the local de nition of simulation to account for fairness: system S fairly simulates system I i in the simulation game, there is a strategy that matches with each fair computation of I a fair computation of S. Our de nition enjoys a fully abstract semantics and has a logical characterization: S fairly simulates I i every fair computation tree embedded in the unrolling of I can be embedded also in the unrolling of S or, equivalently, i every Fair-8AFMC formula satis ed by I is satis ed also by S (8AFMC is the universal fragment of the alternation-free -calculus). The locality of the denition leads us to a polynomial-time algorithm for checking fair simulation for nite-state systems with weak and strong fairness constraints. Finally, fair simulation implies fair trace-containment, and is therefore useful as an e cientlycomputable local criterion for proving linear-time abstraction hierarchies.
• The verification of the fair refinement is linear in the size of the refined system, but the verification of the fair simulation is polynomial REF .
Fair Simulation
Information and Computation
Computer Science