Combining relation algebra and data refinement to develop rectangle-based functional programs for reflexivetransitive closures
We develop a generic relational algorithm for reflexivetransitive closures. The generic algorithm bases on the notion of a rectangle. By data refinement we develop Haskell programs for two choices of rectangles. We show that one of them has cubic running time as Warshall's algorithm. We apply our approach to operations of relation algebra and graph problems.
relation algebra rectangle functional programming haskell directed graphs reflexive-transitive closure