home *** CD-ROM | disk | FTP | other *** search
/ CD Actual Thematic 7: Programming / CDAT7.iso / Share / Editores / Perl5 / perl / lib / site / Math / Kleene.pod next >
Encoding:
Text File  |  1997-08-10  |  5.3 KB  |  279 lines
  1.  
  2. =head1 NAME
  3.  
  4. Kleene's Algorithm - the theory behind it
  5.  
  6. brief introduction
  7.  
  8. =head1 DESCRIPTION
  9.  
  10. =head2 B<Semi-Rings>
  11.  
  12. A Semi-Ring (S, +, ., 0, 1) is characterized by the following properties:
  13.  
  14. =over 4
  15.  
  16. =item 1)
  17.  
  18. a)  C<(S, +, 0) is a Semi-Group with neutral element 0>
  19.  
  20. b)  C<(S, ., 1) is a Semi-Group with neutral element 1>
  21.  
  22. c)  C<0 . a = a . 0 = 0  for all a in S>
  23.  
  24. =item 2)
  25.  
  26. C<"+"> is commutative and B<idempotent>, i.e., C<a + a = a>
  27.  
  28. =item 3)
  29.  
  30. Distributivity holds, i.e.,
  31.  
  32. a)  C<a . ( b + c ) = a . b + a . c  for all a,b,c in S>
  33.  
  34. b)  C<( a + b ) . c = a . c + b . c  for all a,b,c in S>
  35.  
  36. =item 4)
  37.  
  38. C<SUM_{i=0}^{+infinity} ( a[i] )>
  39.  
  40. exists, is well-defined and unique
  41.  
  42. C<for all a[i] in S>
  43.  
  44. and associativity, commutativity and idempotency hold
  45.  
  46. =item 5)
  47.  
  48. Distributivity for infinite series also holds, i.e.,
  49.  
  50.   ( SUM_{i=0}^{+infty} a[i] ) . ( SUM_{j=0}^{+infty} b[j] )
  51.   = SUM_{i=0}^{+infty} ( SUM_{j=0}^{+infty} ( a[i] . b[j] ) )
  52.  
  53. =back
  54.  
  55. EXAMPLES:
  56.  
  57. =over 4
  58.  
  59. =item *
  60.  
  61. C<S1 = ({0,1}, |, &, 0, 1)>
  62.  
  63. Boolean Algebra
  64.  
  65. See also L<Math::MatrixBool(3)>
  66.  
  67. =item *
  68.  
  69. C<S2 = (pos. reals with 0 and +infty, min, +, +infty, 0)>
  70.  
  71. Positive real numbers including zero and plus infinity
  72.  
  73. See also L<Math::MatrixReal(3)>
  74.  
  75. =item *
  76.  
  77. C<S3 = (Pot(Sigma*), union, concat, {}, {''})>
  78.  
  79. Formal languages over Sigma (= alphabet)
  80.  
  81. See also L<DFA::Kleene(3)>
  82.  
  83. =back
  84.  
  85. =head2 B<Operator '*'>
  86.  
  87. (reflexive and transitive closure)
  88.  
  89. Define an operator called "*" as follows:
  90.  
  91.     a in S   ==>   a*  :=  SUM_{i=0}^{+infty} a^i
  92.  
  93. where
  94.  
  95.     a^0  =  1,   a^(i+1)  =  a . a^i
  96.  
  97. Then, also
  98.  
  99.     a*  =  1 + a . a*,   0*  =  1*  =  1
  100.  
  101. hold.
  102.  
  103. =head2 B<Kleene's Algorithm>
  104.  
  105. In its general form, Kleene's algorithm goes as follows:
  106.  
  107.     for i := 1 to n do
  108.         for j := 1 to n do
  109.         begin
  110.             C^0[i,j] := m(v[i],v[j]);
  111.             if (i = j) then C^0[i,j] := C^0[i,j] + 1
  112.         end
  113.     for k := 1 to n do
  114.         for i := 1 to n do
  115.             for j := 1 to n do
  116.                 C^k[i,j] := C^k-1[i,j] +
  117.                             C^k-1[i,k] . ( C^k-1[k,k] )* . C^k-1[k,j]
  118.     for i := 1 to n do
  119.         for j := 1 to n do
  120.             c(v[i],v[j]) := C^n[i,j]
  121.  
  122. =head2 B<Kleene's Algorithm and Semi-Rings>
  123.  
  124. Kleene's algorithm can be applied to any Semi-Ring having the properties
  125. listed previously (above). (!)
  126.  
  127. EXAMPLES:
  128.  
  129. =over 4
  130.  
  131. =item *
  132.  
  133. C<S1 = ({0,1}, |, &, 0, 1)>
  134.  
  135. C<G(V,E)> be a graph with set of vortices V and set of edges E:
  136.  
  137. C<m(v[i],v[j])  :=  ( (v[i],v[j]) in E ) ? 1 : 0>
  138.  
  139. Kleene's algorithm then calculates
  140.  
  141. C<c^{n}_{i,j} = ( path from v[i] to v[j] exists ) ? 1 : 0>
  142.  
  143. using
  144.  
  145. C<C^k[i,j]  =  C^k-1[i,j]  |  C^k-1[i,k]  &  C^k-1[k,j]>
  146.  
  147. (remember C< 0*  =  1*  =  1 >)
  148.  
  149. =item *
  150.  
  151. C<S2 = (pos. reals with 0 and +infty, min, +, +infty, 0)>
  152.  
  153. C<G(V,E)> be a graph with set of vortices V and set of edges E, with
  154. costs C<m(v[i],v[j])> associated with each edge C<(v[i],v[j])> in E:
  155.  
  156. C<m(v[i],v[j])  :=  costs of (v[i],v[j])>
  157.  
  158. C<for all (v[i],v[j]) in E>
  159.  
  160. Set C<m(v[i],v[j]) := +infinity> if an edge (v[i],v[j]) is not in E.
  161.  
  162. C<  ==E<gt>  a* = 0  for all a in S2>
  163.  
  164. C<  ==E<gt>  C^k[i,j]  =  min( C^k-1[i,j] ,>
  165.  
  166. C<           C^k-1[i,k]  +  C^k-1[k,j] )>
  167.  
  168. Kleene's algorithm then calculates the costs of the "shortest" path
  169. from any C<v[i]> to any other C<v[j]>:
  170.  
  171. C<C^n[i,j] = costs of "shortest" path from v[i] to v[j]>
  172.  
  173. =item *
  174.  
  175. C<S3 = (Pot(Sigma*), union, concat, {}, {''})>
  176.  
  177. C<M in DFA(Sigma)> be a Deterministic Finite Automaton with a set of
  178. states C<Q>, a subset C<F> of C<Q> of accepting states and a transition
  179. function C<delta : Q x Sigma --E<gt> Q>.
  180.  
  181. Define
  182.  
  183. C<m(v[i],v[j])  :=>
  184.  
  185. C<    { a in Sigma | delta( q[i] , a ) = q[j] }>
  186.  
  187. and
  188.  
  189. C<C^0[i,j] := m(v[i],v[j]);>
  190.  
  191. C<if (i = j) then C^0[i,j] := C^0[i,j] union {''}>
  192.  
  193. (C<{''}> is the set containing the empty string, whereas C<{}> is the
  194. empty set!)
  195.  
  196. Then Kleene's algorithm calculates the language accepted by Deterministic
  197. Finite Automaton M using
  198.  
  199. C<C^k[i,j] = C^k-1[i,j] union>
  200.  
  201. C<    C^k-1[i,k] concat ( C^k-1[k,k] )* concat C^k-1[k,j]>
  202.  
  203. and
  204.  
  205. C<L(M)  =  UNION_{ q[j] in F }  C^n[1,j]>
  206.  
  207. (state C<q[1]> is assumed to be the "start" state)
  208.  
  209. finally being the language recognized by Deterministic Finite Automaton M.
  210.  
  211. =back
  212.  
  213. Note that instead of using Kleene's algorithm, you can also use the "*"
  214. operator on the associated matrix:
  215.  
  216. Define  C<A[i,j]  :=  m(v[i],v[j])>
  217.  
  218. C<  ==E<gt>   A*[i,j]  =  c(v[i],v[j])>
  219.  
  220. Proof:
  221.  
  222. C<A*  =  SUM_{i=0}^{+infty} A^i>
  223.  
  224. where  C<A^0  =  E_{n}>
  225.  
  226. (matrix with one's in its main diagonal and zero's elsewhere)
  227.  
  228. and  C<A^(i+1)  =   A . A^i>
  229.  
  230. Induction over k yields:
  231.  
  232. C<A^k[i,j]  =  c_{k}(v[i],v[j])>
  233.  
  234. =over 10
  235.  
  236. =item C<k = 0:>
  237.  
  238. C<c_{0}(v[i],v[j])  =  d_{i,j}>
  239.  
  240. with  C<d_{i,j}  :=  (i = j) ? 1 : 0>
  241.  
  242. and  C<A^0  =  E_{n}  =  [d_{i,j}]>
  243.  
  244. =item C<k-1 -E<gt> k:>
  245.  
  246. C<c_{k}(v[i],v[j])>
  247.  
  248. C<= SUM_{l=1}^{n} m(v[i],v[l]) . c_{k-1}(v[l],v[j])>
  249.  
  250. C<= SUM_{l=1}^{n} ( a[i,l] . a[l,j] )>
  251.  
  252. C<= [a^{k}_{i,j}]  =  A^1 . A^(k-1)  =  A^k>
  253.  
  254. =back
  255.  
  256. qed
  257.  
  258. In other words, the complexity of calculating the closure and doing
  259. matrix multiplications is of the same order C<S<O( n^3 )>> in Semi-Rings!
  260.  
  261. =head1 SEE ALSO
  262.  
  263. Math::MatrixBool(3), Math::MatrixReal(3), DFA::Kleene(3).
  264.  
  265. (All contained in the distribution of the "Bit::Vector" module,
  266. formerly named "Set::IntegerFast")
  267.  
  268. Dijkstra's algorithm for shortest paths.
  269.  
  270. =head1 AUTHOR
  271.  
  272. This document is based on lecture notes and has been put into
  273. POD format by Steffen Beyer <sb@sdm.de>.
  274.  
  275. =head1 COPYRIGHT
  276.  
  277. Copyright (c) 1997 by Steffen Beyer. All rights reserved.
  278.  
  279.