=head1 NAME
Kleene's Algorithm - the theory behind it
brief introduction
=head1 DESCRIPTION
=head2 B
A Semi-Ring (S, +, ., 0, 1) is characterized by the following properties:
=over 4
=item 1)
a) C<(S, +, 0) is a Semi-Group with neutral element 0>
b) C<(S, ., 1) is a Semi-Group with neutral element 1>
c) C<0 . a = a . 0 = 0 for all a in S>
=item 2)
C<"+"> is commutative and B, i.e., C
=item 3)
Distributivity holds, i.e.,
a) C
b) C<( a + b ) . c = a . c + b . c for all a,b,c in S>
=item 4)
C
exists, is well-defined and unique
C
and associativity, commutativity and idempotency hold
=item 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] ) )
=back
EXAMPLES:
=over 4
=item *
C
Boolean Algebra
See also L
=item *
C
Positive real numbers including zero and plus infinity
See also L
=item *
C
Formal languages over Sigma (= alphabet)
See also L
=back
=head2 B
(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.
=head2 B
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]
=head2 B
Kleene's algorithm can be applied to any Semi-Ring having the properties
listed previously (above). (!)
EXAMPLES:
=over 4
=item *
C
C be a graph with set of vertices V and set of edges E:
C
Kleene's algorithm then calculates
C
using
C
(remember C< 0* = 1* = 1 >)
=item *
C
C be a graph with set of vertices V and set of edges E, with
costs C associated with each edge C<(v[i],v[j])> in E:
C
C
Set C if an edge (v[i],v[j]) is not in E.
C< ==E a* = 0 for all a in S2>
C< ==E C^k[i,j] = min( C^k-1[i,j] ,>
C< C^k-1[i,k] + C^k-1[k,j] )>
Kleene's algorithm then calculates the costs of the "shortest" path
from any C to any other C:
C
=item *
C
C be a Deterministic Finite Automaton with a set of
states C, a subset C of C of accepting states and a transition
function C Q>.
Define
C
C< { a in Sigma | delta( q[i] , a ) = q[j] }>
and
C
C
(C<{''}> is the set containing the empty string, whereas C<{}> is the
empty set!)
Then Kleene's algorithm calculates the language accepted by Deterministic
Finite Automaton M using
C
C< C^k-1[i,k] concat ( C^k-1[k,k] )* concat C^k-1[k,j]>
and
C
(state C is assumed to be the "start" state)
finally being the language recognized by Deterministic Finite Automaton M.
=back
Note that instead of using Kleene's algorithm, you can also use the "*"
operator on the associated matrix:
Define C
C< ==E A*[i,j] = c(v[i],v[j])>
Proof:
C
where C
(matrix with one's in its main diagonal and zero's elsewhere)
and C
Induction over k yields:
C
=over 10
=item C
C
with C
and C
=item C k:>
C
C<= SUM_{l=1}^{n} m(v[i],v[l]) . c_{k-1}(v[l],v[j])>
C<= SUM_{l=1}^{n} ( a[i,l] . a[l,j] )>
C<= [a^{k}_{i,j}] = A^1 . A^(k-1) = A^k>
=back
qed
In other words, the complexity of calculating the closure and doing
matrix multiplications is of the same order C~~> in Semi-Rings!
=head1 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.
=head1 AUTHOR
This document is based on lecture notes and has been put into
POD format by Steffen Beyer .
=head1 COPYRIGHT
Copyright (c) 1997 by Steffen Beyer. All rights reserved.
~~