Quick Navigator

 Search Site Miscellaneous Server Agreement Year 2038 Credits

# Manual Reference Pages  -  MATH::KLEENE (3)

.ds Aq ’

### NAME

Kleene’s Algorithm - the theory behind it

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

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

Positive real numbers including zero and plus infinity

o S3 = (Pot(Sigma*), union, concat, {}, {})

Formal languages over Sigma (= alphabet)

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

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