Calculational graph algorithmics: reconciling two approaches with dynamic algebra
One concern in making the calculation of algorithms a formal mathematical activity is succinctness of notation and proof. Here we consider two recent contributions to this concern that we believe to be valuable. The contributions show how matrix algebra and relation algebra, respectively, enhance succinctness in the formal calculation of algorithms for path problems (amongst others) in graphs. The contributions are independent, and use different notations and proof strategies. However, the differences can be reconciled. Here we show how to make this reconciliation. The reconciliation is valuable for two reasons. First, it provides a straightforward synthesis of overlapping aspects of the two independent pieces of work, revealing the common ground behind superficially different appearances. Second, it prompts consideration of a unifying abstract framework as the basis for further algorithm calculations. An appropriate unifying framework is shown to be dynamic algebra.
|Department of Computer Science [CS]|
Clenaghan, K. (1995). Calculational graph algorithmics: reconciling two approaches with dynamic algebra. Department of Computer Science [CS]. CWI.