Executable Transitive Closures of Finite Relations

Christian Sternagel 📧 and René Thiemann 📧

March 14, 2011

Abstract

We provide a generic work-list algorithm to compute the transitive closure of finite relations where only successors of newly detected states are generated. This algorithm is then instantiated for lists over arbitrary carriers and red black trees (which are faster but require a linear order on the carrier), respectively. Our formalization was performed as part of the IsaFoR/CeTA project where reflexive transitive closures of large tree automata have to be computed.
GNU Lesser General Public License (LGPL)

Topics

Theories of Transitive-Closure