Bloom, Bard; Paige, Robert Transformational design and implementation of a new efficient solution to the ready simulation problem. (English) Zbl 0832.68050 Sci. Comput. Program. 24, No. 3, 189-220 (1995). Summary: A transformational methodology is described for simultaneously designing algorithms and developing programs. The methodology makes use of three transformational tools – dominated convergence, finite differencing, and real-time simulation of a set machine on a RAM. We illustrate the 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 substantial improvement on the \(\Theta (mn^6)\) algorithm presented by the first author in his Thesis (1989). The methodology is also used to derive a program whose performance, 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. Cited in 15 Documents MSC: 68W10 Parallel algorithms in computer science Keywords:ready simulation problem PDFBibTeX XMLCite \textit{B. Bloom} and \textit{R. Paige}, Sci. Comput. Program. 24, No. 3, 189--220 (1995; Zbl 0832.68050) Full Text: DOI