Semi-Rings

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 '*'

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

    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

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!