Rechercher une page de manuel
Math::Kleene.3pm
Langue: en
Version: 1999-05-19 (mandriva - 01/05/08)
Section: 3 (Bibliothèques de fonctions)
NAME
Kleene's Algorithm - the theory behind itbrief 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:
- •
- "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^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:
- •
- "S1 = ({0,1}, |, &, 0, 1)"
"G(V,E)" be a graph with set of vertices 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^k-1[i,j] | C^k-1[i,k] & C^k-1[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 vertices V and set of edges E, with costs "m(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^k-1[i,j] ,"
" C^k-1[i,k] + C^k-1[k,j] )"
Kleene's algorithm then calculates the costs of the ``shortest'' path from any "v[i]" to any other "v[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 states "Q", a subset "F" of "Q" of accepting states and a transition function "delta : 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^k-1[i,j] union"
" C^k-1[i,k] concat ( C^k-1[k,k] )* concat C^k-1[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}]"
- "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).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, 1998, 1999 by Steffen Beyer. All rights reserved.Contenus ©2006-2024 Benjamin Poulain
Design ©2006-2024 Maxime Vantorre