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
Kleene(3) User Contributed Perl Documentation Kleene(3)

Kleene's Algorithm - the theory behind it

brief introduction

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)

(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.

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 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!

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.

This document is based on lecture notes and has been put into POD format by Steffen Beyer <sb@engelschall.com>.

Copyright (c) 1997 by Steffen Beyer. All rights reserved.
2016-09-25 perl v5.32.1

Search for    or go to Top of page |  Section 3 |  Main Index

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