TRANSFORMATIONAL DESIGN AND IMPLEMENTATION OF A NEW EFFICIENT SOLUTION TO THE READY SIMULATION PROBLEM

A transformational methodology is described for simultaneously designi ng algorithms and developing programs. The methodology makes use of th ree transformational tools - dominated convergence, finite differencin g, and real-time simulation of a set machine on a RAM. We ilustrate th e methodology to design a new O(mn + n(2))-time algorithm for deciding when n-state, m-transition processes are ready similar, which is a su bstantial improvement on the Theta(mn(6)) algorithm presented in Bloom (1989). The methodology is also used to derive a program whose perfor mance, we believe, is competitive with the most efficient hand-crafted implementation of our algorithm. Ready simulation is the finest fully abstract notion of process equivalence in the CCS setting.