.\" Automatically generated by Pod::Man v1.34, Pod::Parser v1.13
.\" ========================================================================
.de Sh \" Subsection heading
.de Sp \" Vertical space (when we can't use .PP)
.de Vb \" Begin verbatim text
.de Ve \" End verbatim text
.\" Set up some character translations and predefined strings. \*(-- will
.\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
.\" double quote, and \*(R" will give a right double quote. | will give a
.\" real vertical bar. \*(C+ will give a nicer C++. Capital omega is used to
.\" do unbreakable dashes and therefore won't be available. \*(C` and \*(C'
.\" expand to `' in nroff, nothing in troff, for use with C<>.
.ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
. if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
. if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch
.\" If the F register is turned on, we'll generate index entries on stderr for
.\" titles (.TH), headers (.SH), subsections (.Sh), items (.Ip), and index
.\" entries marked with X<> in POD. Of course, you'll have to process the
.\" output yourself in some meaningful fashion.
. tm Index:\\$1\t\\n%\t"\\$2"
.\" For nroff, turn off justification. Always turn off hyphenation; it makes
.\" way too many mistakes in technical documents.
.\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2).
.\" Fear. Run. Save yourself. No user-serviceable parts.
. \" fudge factors for nroff and troff
. ds #H ((1u-(\\\\n(.fu%2u))*.13m)
. \" simple accents for nroff and troff
. ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
. ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
. ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
. ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
. ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
. ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
. \" troff and (daisy-wheel) nroff accents
.ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
.ds 8 \h'\*(#H'\(*b\h'-\*(#H'
.ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
.ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
.ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
.ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
.ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
.ds ae a\h'-(\w'a'u*4/10)'e
.ds Ae A\h'-(\w'A'u*4/10)'E
. \" corrections for vroff
.if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
.if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
. \" for low resolution devices (crt and lpr)
.if \n(.H>23 .if \n(.V>19 \
.\" ========================================================================
.TH KLEENE 1 "2001-12-12" "perl v5.8.0" "User Contributed Perl Documentation"
Kleene's Algorithm \- the theory behind it
.IX Subsection "Semi-Rings"
A Semi-Ring (S, +, ., 0, 1) is characterized by the following properties:
a) \f(CW\*(C`(S, +, 0) is a Semi\-Group with neutral element 0\*(C'\fR
b) \f(CW\*(C`(S, ., 1) is a Semi\-Group with neutral element 1\*(C'\fR
c) \f(CW\*(C`0 . a = a . 0 = 0 for all a in S\*(C'\fR
\&\f(CW"+"\fR is commutative and \fBidempotent\fR, i.e., \f(CW\*(C`a + a = a\*(C'\fR
Distributivity holds, i.e.,
a) \f(CW\*(C`a . ( b + c ) = a . b + a . c for all a,b,c in S\*(C'\fR
b) \f(CW\*(C`( a + b ) . c = a . c + b . c for all a,b,c in S\*(C'\fR
\&\f(CW\*(C`SUM_{i=0}^{+infinity} ( a[i] )\*(C'\fR
exists, is well-defined and unique
\&\f(CW\*(C`for all a[i] in S\*(C'\fR
and associativity, commutativity and idempotency hold
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] ) )
\&\f(CW\*(C`S1 = ({0,1}, |, &, 0, 1)\*(C'\fR
See also \fIMath::MatrixBool\fR\|(3)
\&\f(CW\*(C`S2 = (pos. reals with 0 and +infty, min, +, +infty, 0)\*(C'\fR
Positive real numbers including zero and plus infinity
See also \fIMath::MatrixReal\fR\|(3)
\&\f(CW\*(C`S3 = (Pot(Sigma*), union, concat, {}, {''})\*(C'\fR
Formal languages over Sigma (= alphabet)
See also \fIDFA::Kleene\fR\|(3)
.IX Subsection "Operator '*'"
(reflexive and transitive closure)
Define an operator called \*(L"*\*(R" as follows:
\& a in S ==> a* := SUM_{i=0}^{+infty} a^i
\& a^0 = 1, a^(i+1) = a . a^i
\& a* = 1 + a . a*, 0* = 1* = 1
.Sh "\fBKleene's Algorithm\fP"
.IX Subsection "Kleene's Algorithm"
In its general form, Kleene's algorithm goes as follows:
\& C^0[i,j] := m(v[i],v[j]);
\& if (i = j) then C^0[i,j] := C^0[i,j] + 1
\& C^k[i,j] := C^k-1[i,j] +
\& C^k-1[i,k] . ( C^k-1[k,k] )* . C^k-1[k,j]
\& c(v[i],v[j]) := C^n[i,j]
.Sh "\fBKleene's Algorithm and Semi-Rings\fP"
.IX Subsection "Kleene's Algorithm and Semi-Rings"
Kleene's algorithm can be applied to any Semi-Ring having the properties
listed previously (above). (!)
\&\f(CW\*(C`S1 = ({0,1}, |, &, 0, 1)\*(C'\fR
\&\f(CW\*(C`G(V,E)\*(C'\fR be a graph with set of vortices V and set of edges E:
\&\f(CW\*(C`m(v[i],v[j]) := ( (v[i],v[j]) in E ) ? 1 : 0\*(C'\fR
Kleene's algorithm then calculates
\&\f(CW\*(C`c^{n}_{i,j} = ( path from v[i] to v[j] exists ) ? 1 : 0\*(C'\fR
\&\f(CW\*(C`C^k[i,j] = C^k\-1[i,j] | C^k\-1[i,k] & C^k\-1[k,j]\*(C'\fR
(remember \f(CW\*(C` 0* = 1* = 1 \*(C'\fR)
\&\f(CW\*(C`S2 = (pos. reals with 0 and +infty, min, +, +infty, 0)\*(C'\fR
\&\f(CW\*(C`G(V,E)\*(C'\fR be a graph with set of vortices V and set of edges E, with
costs \f(CW\*(C`m(v[i],v[j])\*(C'\fR associated with each edge \f(CW\*(C`(v[i],v[j])\*(C'\fR in E:
\&\f(CW\*(C`m(v[i],v[j]) := costs of (v[i],v[j])\*(C'\fR
\&\f(CW\*(C`for all (v[i],v[j]) in E\*(C'\fR
Set \f(CW\*(C`m(v[i],v[j]) := +infinity\*(C'\fR if an edge (v[i],v[j]) is not in E.
\&\f(CW\*(C` ==> a* = 0 for all a in S2\*(C'\fR
\&\f(CW\*(C` ==> C^k[i,j] = min( C^k\-1[i,j] ,\*(C'\fR
\&\f(CW\*(C` C^k\-1[i,k] + C^k\-1[k,j] )\*(C'\fR
Kleene's algorithm then calculates the costs of the \*(L"shortest\*(R" path
from any \f(CW\*(C`v[i]\*(C'\fR to any other \f(CW\*(C`v[j]\*(C'\fR:
\&\f(CW\*(C`C^n[i,j] = costs of "shortest" path from v[i] to v[j]\*(C'\fR
\&\f(CW\*(C`S3 = (Pot(Sigma*), union, concat, {}, {''})\*(C'\fR
\&\f(CW\*(C`M in DFA(Sigma)\*(C'\fR be a Deterministic Finite Automaton with a set of
states \f(CW\*(C`Q\*(C'\fR, a subset \f(CW\*(C`F\*(C'\fR of \f(CW\*(C`Q\*(C'\fR of accepting states and a transition
function \f(CW\*(C`delta : Q x Sigma \-\-> Q\*(C'\fR.
\&\f(CW\*(C`m(v[i],v[j]) :=\*(C'\fR
\&\f(CW\*(C` { a in Sigma | delta( q[i] , a ) = q[j] }\*(C'\fR
\&\f(CW\*(C`C^0[i,j] := m(v[i],v[j]);\*(C'\fR
\&\f(CW\*(C`if (i = j) then C^0[i,j] := C^0[i,j] union {''}\*(C'\fR
(\f(CW\*(C`{''}\*(C'\fR is the set containing the empty string, whereas \f(CW\*(C`{}\*(C'\fR is the
Then Kleene's algorithm calculates the language accepted by Deterministic
\&\f(CW\*(C`C^k[i,j] = C^k\-1[i,j] union\*(C'\fR
\&\f(CW\*(C` C^k\-1[i,k] concat ( C^k\-1[k,k] )* concat C^k\-1[k,j]\*(C'\fR
\&\f(CW\*(C`L(M) = UNION_{ q[j] in F } C^n[1,j]\*(C'\fR
(state \f(CW\*(C`q[1]\*(C'\fR is assumed to be the \*(L"start\*(R" state)
finally being the language recognized by Deterministic Finite Automaton M.
Note that instead of using Kleene's algorithm, you can also use the \*(L"*\*(R"
operator on the associated matrix:
Define \f(CW\*(C`A[i,j] := m(v[i],v[j])\*(C'\fR
\&\f(CW\*(C` ==> A*[i,j] = c(v[i],v[j])\*(C'\fR
\&\f(CW\*(C`A* = SUM_{i=0}^{+infty} A^i\*(C'\fR
where \f(CW\*(C`A^0 = E_{n}\*(C'\fR
(matrix with one's in its main diagonal and zero's elsewhere)
and \f(CW\*(C`A^(i+1) = A . A^i\*(C'\fR
\&\f(CW\*(C`A^k[i,j] = c_{k}(v[i],v[j])\*(C'\fR
.ie n .IP """k = 0:""" 10
.el .IP "\f(CWk = 0:\fR" 10
\&\f(CW\*(C`c_{0}(v[i],v[j]) = d_{i,j}\*(C'\fR
with \f(CW\*(C`d_{i,j} := (i = j) ? 1 : 0\*(C'\fR
and \f(CW\*(C`A^0 = E_{n} = [d_{i,j}]\*(C'\fR
.ie n .IP """k\-1 \-> k:""" 10
.el .IP "\f(CWk\-1 \-> k:\fR" 10
\&\f(CW\*(C`c_{k}(v[i],v[j])\*(C'\fR
\&\f(CW\*(C`= SUM_{l=1}^{n} m(v[i],v[l]) . c_{k\-1}(v[l],v[j])\*(C'\fR
\&\f(CW\*(C`= SUM_{l=1}^{n} ( a[i,l] . a[l,j] )\*(C'\fR
\&\f(CW\*(C`= [a^{k}_{i,j}] = A^1 . A^(k\-1) = A^k\*(C'\fR
In other words, the complexity of calculating the closure and doing
matrix multiplications is of the same order \f(CW\*(C`O(\ n^3\ )\*(C'\fR in Semi\-Rings!
\&\fIMath::MatrixBool\fR\|(3), \fIMath::MatrixReal\fR\|(3), \fIDFA::Kleene\fR\|(3).
(All contained in the distribution of the \*(L"Set::IntegerFast\*(R" module)
Dijkstra's algorithm for shortest paths.
This document is based on lecture notes and has been put into
\&\s-1POD\s0 format by Steffen Beyer <sb@engelschall.com>.
Copyright (c) 1997 by Steffen Beyer. All rights reserved.
projects / OpenSPARC-T2-DV / blob