Diese Seite auf deutsch
SearchGreedy-Like Algorithms in Kleene Algebra
B. Möller, G. Struth
2003-11
in: Universität Augsburg
Technical Report, Institute of Computer Science, University of Augsburg, August 2003
This paper provides an algebraic background for the formal derivation of greedy-like algorithms. Such derivations have previously been done in various frameworks including relation algebra. We propose Kleene algebra as a particularly simple alternative. Instead of converse and residuation we use modal operators that are definable in a wide class of algebras, based on domain/codomain or image/pre-image operations. By abstracting from earlier approaches we arrive at a very general theorem about the correctness of loops that covers particular forms of greedy algorithms as special cases.
Downloads:
- Greedy-Like Algorithms in Kleene Algebra - (tr-2003-11_moe_str.pdf, 765 KB)