Abstract derivation of transitive closure algorithms

L.M.G. Feijs, R.C. van Ommering

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
1 Downloads (Pure)


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.
Original languageEnglish
Pages (from-to)159-164
JournalInformation Processing Letters
Issue number3
Publication statusPublished - 1997


Dive into the research topics of 'Abstract derivation of transitive closure algorithms'. Together they form a unique fingerprint.

Cite this