Efficient algorithms for computing transitive closure in CWB : Implementation and comparison of several variations

This paper presents a thesis work for the M. Sc degree in Computer Science at the University of Stockholm. Abstract: The work was accomplished at the Swedish Institute of Computer Science (SICS) during autumn and winter 1989-1990. Björn Lisper was supervisor at SICS and Yngve Sundblad at NADA/KTH. The task was to implement an efficient algorithm for computing the transitive closure of binary relations in the Concurrency Workbench (CWB). The CWB is a system that caters for the analysis of concurrent processes expressed in CCS. It was developed at the University of Edinburgh. Further development has and is being carried out both at Edinburgh, the University of Sussex and SICS. The system is written in Standard ML. I have studied a number of transitive closure algorithms. An algorithm by J. Eve and R. Kurki-Suonio seemed to be the most efficient. Two versions of this and of the classical Warhall algorithm have been implemented. One version use array representation and one version uses list representation