Executable Transitive Closures of Finite Relations (Q7361316)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
AFP entry Transitive-Closure
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Executable Transitive Closures of Finite Relations |
AFP entry Transitive-Closure |
Statements
14 March 2011
0 references
Christian Sternagel
0 references
René Thiemann
0 references
Executable Transitive Closures of Finite Relations (English)
0 references
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.
0 references
