Executable Transitive Closures of Finite Relations

Christian Sternagel 📧 and René Thiemann 🌐

March 14, 2011

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

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.

License

GNU Lesser General Public License (LGPL)

Topics

Session Transitive-Closure