  One central issue in the formal design and analysis of reactive systems is
the notion of refinement that asks whether all behaviors of the implementation
is allowed by the specification. The local interpretation of behavior leads to
the notion of simulation. Alternating transition systems (ATSs) provide a
general model for composite reactive systems, and the simulation relation for
ATSs is known as alternating simulation. The simulation relation for fair
transition systems is called fair simulation. In this work our main
contributions are as follows: (1) We present an improved algorithm for fair
simulation with B\"uchi fairness constraints; our algorithm requires $O(n^3
\cdot m)$ time as compared to the previous known $O(n^6)$-time algorithm, where
$n$ is the number of states and $m$ is the number of transitions. (2) We
present a game based algorithm for alternating simulation that requires
$O(m^2)$-time as compared to the previous known $O((n \cdot m)^2)$-time
algorithm, where $n$ is the number of states and $m$ is the size of transition
relation. (3) We present an iterative algorithm for alternating simulation that
matches the time complexity of the game based algorithm, but is more space
efficient than the game based algorithm.
