Compute the coarsest simulation preorder included in an initial preorder is used to reduce the resources needed to analyze a given transition system. This technique is applied on many models like Kripke structures, labeled graphs, labeled transition systems or even word and tree automata. Let (Q,→) be a given transition system and ℛ<inf>init</inf> be an initial preorder over Q. Until now, algorithms to compute ℛ<inf>sim</inf>, the coarsest simulation included in ℛ<inf>init</inf>, are either memory efficient or time efficient but not both. In this paper we propose the foundation for a series of efficient simulation algorithms with the introduction of the notion of maximal transitions and the notion of stability of a preorder with respect to a coarser one. As an illustration we solve an open problem by providing the first algorithm with the best published time complexity, O(|P<inf>sim</inf>|.|→|), and a bit space complexity in O(|P<inf>sim</inf>|².log(|P<inf>sim</inf>|)+|Q|.log(|Q|)), with P<inf>sim</inf> the partition induced by ℛ<inf>sim</inf>.

@inproceedings{abs-1709-01826,
  title = {Foundation for a series of efficient simulation algorithms},
  author = {Gerard Cece},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005069}
}