GSP
Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Support
Contact Us
Online Help
Handbooks
Domain Status
Man Pages

FAQ
Virtual Servers
Pricing
Billing
Technical

Network
Facilities
Connectivity
Topology Map

Miscellaneous
Server Agreement
Year 2038
Credits
 

USA Flag

 

 

Man Pages


Manual Reference Pages  -  MATH::KLEENE (3)

.ds Aq ’

NAME

Kleene’s Algorithm - the theory behind it

brief introduction

CONTENTS

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 <B>idempotentB>, 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:
o S1 = ({0,1}, |, &, 0, 1)

Boolean Algebra

See also Math::MatrixBool(3)

o S2 = (pos. reals with 0 and +infty, min, +, +infty, 0)

Positive real numbers including zero and plus infinity

See also Math::MatrixReal(3)

o 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:
o 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 )

o 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]

o 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).

(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@engelschall.com>.

COPYRIGHT

Copyright (c) 1997 by Steffen Beyer. All rights reserved.
Search for    or go to Top of page |  Section 3 |  Main Index


perl v5.20.3 KLEENE (3) 2014-12-28

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with manServer 1.07.