Summary: A number of algorithms for computing the simulation preorder and equivalence are available. Let \(\Sigma \) denote the state space, \(\rightarrow \) the transition relation and \(P_{\text{sim}}\) the partition of \(\Sigma \) induced by simulation equivalence. The algorithms by Henzinger, Henzinger, Kopke and by Bloom and Paige run in \(O(|\Sigma ||\rightarrow |)\) time and, as far as time complexity is concerned, they are the best available algorithms. However, these algorithms have the drawback of a space complexity that is more than quadratic in the size of the state space \(\Sigma \). The algorithm by Gentilini, Piazza, Policriti – subsequently corrected by van Glabbeek and Ploeger – appears to provide the best compromise between time and space complexity. Gentilini et al.’s algorithm runs in \(O(|P_{\text{sim}}|^{2}|\rightarrow |)\) time while the space complexity is in \(O(|P_{\text{sim}}|^{2}+|\Sigma |\log |P_{\text{sim}}|)\). We present here a new efficient simulation algorithm that is obtained as a modification of Henzinger et al.’s algorithm and whose correctness is based on some techniques used in applications of abstract interpretation to model checking. Our algorithm runs in \(O(|P_{\text{sim}}||\rightarrow |)\) time and \(O(|P_{\text{sim}}||\Sigma | \log |\Sigma |)\) space. Thus, this algorithm improves the best known time bound while retaining an acceptable space complexity that is in general less than quadratic in the size of the state space \(|\Sigma |\). An experimental evaluation showed good comparative results with respect to Henzinger, Henzinger and Kopke’s algorithm.