Kleene


NAME

Kleene's Algorithm - the theory behind it

brief introduction


DESCRIPTION

Semi-Rings

A Semi-Ring (S, +, ., 0, 1) is characterized by the following properties:

  1. a) (S, +, 0) is a Semi-Group with neutral element 0

    b) (S, ., 1) is a Semi-Group with neutral element 1

    c) 0 . a = a . 0 = 0 for all a in S

  2. ``+'' is commutative and idempotent, i.e., a + a = a

  3. Distributivity holds, i.e.,

    a) a . ( b + c ) = a . b + a . c for all a,b,c in S

    b) ( a + b ) . c = a . c + b . c for all a,b,c in S

  4. SUM_{i=0}^{+infinity} ( a[i] )

    exists, is well-defined and unique

    for all a[i] in S

    and associativity, commutativity and idempotency hold

  5. Distributivity for infinite series also holds, i.e.,

    ( SUM_{i=0}^{+infty} a[i] ) . ( SUM_{j=0}^{+infty} b[j] ) = SUM_{i=0}^{+infty} ( SUM_{j=0}^{+infty} ( a[i] . b[j] ) )

EXAMPLES:.

.

Operator '*'

(reflexive and transitive closure)

Define an operator called ``*'' as follows:

a in S ==> a* := SUM_{i=0}^{+infty} a^i

where

a^0 = 1, a^(i+1) = a . a^i

Then, also

a* = 1 + a . a*, 0* = 1* = 1

hold.

Kleene's Algorithm

In its general form, Kleene's algorithm goes as follows:

for i := 1 to n do for j := 1 to n do begin C^0[i,j] := m(v[i],v[j]); if (i = j) then C^0[i,j] := C^0[i,j] + 1 end for k := 1 to n do for i := 1 to n do for j := 1 to n do C^k[i,j] := C^k-1[i,j] + C^k-1[i,k] . ( C^k-1[k,k] )* . C^k-1[k,j] for i := 1 to n do for j := 1 to n do c(v[i],v[j]) := C^n[i,j]

Kleene's Algorithm and Semi-Rings

Kleene's algorithm can be applied to any Semi-Ring having the properties listed previously (above). (!)

EXAMPLES:

Note that instead of using Kleene's algorithm, you can also use the ``*''.operator on the associated matrix:

Define A[i,j] := m(v[i],v[j])

==> A*[i,j] = c(v[i],v[j])

Proof:

A* = SUM_{i=0}^{+infty} A^i

where A^0 = E_{n}

(matrix with one's in its main diagonal and zero's elsewhere)

and A^(i+1) = A . A^i

Induction over k yields:

A^k[i,j] = c_{k}(v[i],v[j])

k = 0:
c_{0}(v[i],v[j]) = d_{i,j}

with d_{i,j} := (i = j) ? 1 : 0

and A^0 = E_{n} = [d_{i,j}]

k-1 -> k:
c_{k}(v[i],v[j])

= SUM_{l=1}^{n} m(v[i],v[l]) . c_{k-1}(v[l],v[j])

= SUM_{l=1}^{n} ( a[i,l] . a[l,j] )

= [a^{k}_{i,j}] = A^1 . A^(k-1) = A^k

qed. In other words, the complexity of calculating the closure and doing matrix multiplications is of the same order O( n^3 )> in Semi-Rings!


SEE ALSO

Math::MatrixBool(3), Math::MatrixReal(3), DFA::Kleene(3).

(All contained in the distribution of the ``Set::IntegerFast'' module)

Dijkstra's algorithm for shortest paths.


AUTHOR

This document is based on lecture notes and has been put into POD format by Steffen Beyer <sb@sdm.de>.


COPYRIGHT

Copyright (c) 1997 by Steffen Beyer. All rights reserved.