NAME
Kleene's Algorithm  the theory behind it
brief introduction
DESCRIPTION
SemiRings
A SemiRing (S, +, ., 0, 1) is characterized by the following properties:
 1)

a)
(S, +, 0) is a SemiGroup with neutral element 0
b)
(S, ., 1) is a SemiGroup 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 welldefined 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:
S1 = ({0,1}, , &, 0, 1)
Boolean Algebra
See also Math::MatrixBool(3)
S2 = (pos. reals with 0 and +infty, min, +, +infty, 0)
Positive real numbers including zero and plus infinity
See also Math::MatrixReal(3)
S3 = (Pot(Sigma*), union, concat, {}, {''})
Formal languages over Sigma (= alphabet)
See also DFA::Kleene(3)
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^k1[i,j] +
C^k1[i,k] . ( C^k1[k,k] )* . C^k1[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 SemiRings
Kleene's algorithm can be applied to any SemiRing having the properties listed previously (above). (!)
EXAMPLES:
S1 = ({0,1}, , &, 0, 1)
G(V,E)
be a graph with set of vortices V and set of edges E:m(v[i],v[j]) := ( (v[i],v[j]) in E ) ? 1 : 0
Kleene's algorithm then calculates
c^{n}_{i,j} = ( path from v[i] to v[j] exists ) ? 1 : 0
using
C^k[i,j] = C^k1[i,j]  C^k1[i,k] & C^k1[k,j]
(remember
0* = 1* = 1
)S2 = (pos. reals with 0 and +infty, min, +, +infty, 0)
G(V,E)
be a graph with set of vortices V and set of edges E, with costsm(v[i],v[j])
associated with each edge(v[i],v[j])
in E:m(v[i],v[j]) := costs of (v[i],v[j])
for all (v[i],v[j]) in E
Set
m(v[i],v[j]) := +infinity
if an edge (v[i],v[j]) is not in E.==> a* = 0 for all a in S2
==> C^k[i,j] = min( C^k1[i,j] ,
C^k1[i,k] + C^k1[k,j] )
Kleene's algorithm then calculates the costs of the "shortest" path from any
v[i]
to any otherv[j]
:C^n[i,j] = costs of "shortest" path from v[i] to v[j]
S3 = (Pot(Sigma*), union, concat, {}, {''})
M in DFA(Sigma)
be a Deterministic Finite Automaton with a set of statesQ
, a subsetF
ofQ
of accepting states and a transition functiondelta : Q x Sigma > Q
.Define
m(v[i],v[j]) :=
{ a in Sigma  delta( q[i] , a ) = q[j] }
and
C^0[i,j] := m(v[i],v[j]);
if (i = j) then C^0[i,j] := C^0[i,j] union {''}
(
{''}
is the set containing the empty string, whereas{}
is the empty set!)Then Kleene's algorithm calculates the language accepted by Deterministic Finite Automaton M using
C^k[i,j] = C^k1[i,j] union
C^k1[i,k] concat ( C^k1[k,k] )* concat C^k1[k,j]
and
L(M) = UNION_{ q[j] in F } C^n[1,j]
(state
q[1]
is assumed to be the "start" state)finally being the language recognized by Deterministic Finite Automaton M.
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}]
k1 > k:

c_{k}(v[i],v[j])
= SUM_{l=1}^{n} m(v[i],v[l]) . c_{k1}(v[l],v[j])
= SUM_{l=1}^{n} ( a[i,l] . a[l,j] )
= [a^{k}_{i,j}] = A^1 . A^(k1) = 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 SemiRings!
SEE ALSO
Math::MatrixBool(3), Math::MatrixReal(3), DFA::Kleene(3).
(All contained in the distribution of the "Bit::Vector" module, formerly named "Set::IntegerFast")
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.