TY - JOUR
T1 - Abstract derivation of transitive closure algorithms
AU - Feijs, L.M.G.
AU - van Ommering, R.C.
PY - 1997
Y1 - 1997
N2 - We state Warshall's algorithm in an abstract form and prove its correctness, while postponing the choices of representation. This is achieved by the use of relations and algebraic operations on relations, avoiding the use of vectors, matrix elements and indices. By choosing specific forms for the loop-body we derive Warshall's algorithm, the grid algorithm and generalisations of the latter. The derivation illustrates the point that nontrivial algorithms need not have difficult derivations, provided the right abstractions are chosen and provided the right notation is employed.
AB - We state Warshall's algorithm in an abstract form and prove its correctness, while postponing the choices of representation. This is achieved by the use of relations and algebraic operations on relations, avoiding the use of vectors, matrix elements and indices. By choosing specific forms for the loop-body we derive Warshall's algorithm, the grid algorithm and generalisations of the latter. The derivation illustrates the point that nontrivial algorithms need not have difficult derivations, provided the right abstractions are chosen and provided the right notation is employed.
U2 - 10.1016/S0020-0190(97)00113-0
DO - 10.1016/S0020-0190(97)00113-0
M3 - Article
SN - 0020-0190
VL - 63
SP - 159
EP - 164
JO - Information Processing Letters
JF - Information Processing Letters
IS - 3
ER -