×

Transformational design and implementation of a new efficient solution to the ready simulation problem. (English) Zbl 0832.68050

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.

MSC:

68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI