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 ℛinitbe an initial preorder over Q. Until now, algorithms to compute ℛsim, the coarsest simulation included in ℛinit, 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(|Psim|.|→|), and a bit space complexity in O(|Psim|2.log(|Psim|)+|Q|.log(|Q|)), with Psimthe partition induced by ℛsim.

We consider the problem of verifying correctness of finite state machines that communicate with each other over unbounded FIFO channels that are unreliable. Various problems regarding verification of FIFO channels that can lose messages have been considered by Finkel [10], and by Abdulla and Johnson [1, 2]. We consider, in this paper, other possible unreliable behaviors of communication channels, viz. (a) duplication and (b) insertion errors. Furthermore, we also consider various combinations of duplication, insertion and lossiness errors.Finite state machines that communicate over unbounded FIFO buffers is a model of computation that forms the backbone of ISO standard protocol specification languages Estelle and SDL. While an assumption of a perfect communication medium is reasonable at the higher levels of the OSI protocol stack, the lower levels have to deal with an unreliable communication medium; hence our motivation for the present work.The verification problems that are of interest are reachability, unboundedness, deadlock, and model-checking against CTL. All of these problems are undecidable for machines communicating over reliable unbounded FIFO channels. So, it is perhaps surprising that some of these problems become decidable when unreliable channels are modeled. The contributions of this paper are: (a) An investigation of solutions to these problems for machines with insertion errors, duplication errors, or a combination of duplication, insertion and lossiness errors, and (b) A comparison of the relative expressive power of the various errors.