home *** CD-ROM | disk | FTP | other *** search
/ Chip 2000 May / Chip_2000-05_cd1.bin / zkuste / Perl / ActivePerl-5.6.0.613.msi / 䆊䌷䈹䈙䏵-䞅䞆䞀㡆䞃䄦䠥 / _ef5badafe9192e74daf62dd8bc3927e1 < prev    next >
Text File  |  2000-03-23  |  10KB  |  239 lines
  1.  
  2. <HTML>
  3. <HEAD>
  4. <TITLE>Algorithm - the theory behind it</TITLE>
  5. <LINK REL="stylesheet" HREF="../../../Active.css" TYPE="text/css">
  6. <LINK REV="made" HREF="mailto:">
  7. </HEAD>
  8.  
  9. <BODY>
  10. <TABLE BORDER=0 CELLPADDING=0 CELLSPACING=0 WIDTH=100%>
  11. <TR><TD CLASS=block VALIGN=MIDDLE WIDTH=100% BGCOLOR="#cccccc">
  12. <STRONG><P CLASS=block> Algorithm - the theory behind it</P></STRONG>
  13. </TD></TR>
  14. </TABLE>
  15.  
  16. <A NAME="__index__"></A>
  17. <!-- INDEX BEGIN -->
  18.  
  19. <UL>
  20.  
  21.     <LI><A HREF="#name">NAME</A></LI><LI><A HREF="#supportedplatforms">SUPPORTED PLATFORMS</A></LI>
  22.  
  23.     <LI><A HREF="#description">DESCRIPTION</A></LI>
  24.     <UL>
  25.  
  26.         <LI><A HREF="#semirings"><STRONG>Semi-Rings</STRONG></A></LI>
  27.         <LI><A HREF="#operator '*'"><STRONG>Operator '*'</STRONG></A></LI>
  28.         <LI><A HREF="#kleene's algorithm"><STRONG>Kleene's Algorithm</STRONG></A></LI>
  29.         <LI><A HREF="#kleene's algorithm and semirings"><STRONG>Kleene's Algorithm and Semi-Rings</STRONG></A></LI>
  30.     </UL>
  31.  
  32.     <LI><A HREF="#see also">SEE ALSO</A></LI>
  33.     <LI><A HREF="#author">AUTHOR</A></LI>
  34.     <LI><A HREF="#copyright">COPYRIGHT</A></LI>
  35. </UL>
  36. <!-- INDEX END -->
  37.  
  38. <HR>
  39. <P>
  40. <H1><A NAME="name">NAME</A></H1>
  41. <P>Kleene's Algorithm - the theory behind it</P>
  42. <P>brief introduction</P>
  43. <P>
  44. <HR>
  45. <H1><A NAME="supportedplatforms">SUPPORTED PLATFORMS</A></H1>
  46. <UL>
  47. <LI>Linux</LI>
  48. <LI>Solaris</LI>
  49. <LI>Windows</LI>
  50. </UL>
  51. <HR>
  52. <H1><A NAME="description">DESCRIPTION</A></H1>
  53. <P>
  54. <H2><A NAME="semirings"><STRONG>Semi-Rings</STRONG></A></H2>
  55. <P>A Semi-Ring (S, +, ., 0, 1) is characterized by the following properties:</P>
  56. <OL>
  57. <LI><STRONG><A NAME="item_%29">)</A></STRONG><BR>
  58.  
  59. a)  <CODE>(S, +, 0) is a Semi-Group with neutral element 0</CODE>
  60. <P>b)  <CODE>(S, ., 1) is a Semi-Group with neutral element 1</CODE></P>
  61. <P>c)  <CODE>0 . a = a . 0 = 0  for all a in S</CODE></P>
  62. <P></P>
  63. <LI><STRONG>)</STRONG><BR>
  64.  
  65. <CODE>"+"</CODE> is commutative and <STRONG>idempotent</STRONG>, i.e., <CODE>a + a = a</CODE>
  66. <P></P>
  67. <LI><STRONG>)</STRONG><BR>
  68.  
  69. Distributivity holds, i.e.,
  70. <P>a)  <CODE>a . ( b + c ) = a . b + a . c  for all a,b,c in S</CODE></P>
  71. <P>b)  <CODE>( a + b ) . c = a . c + b . c  for all a,b,c in S</CODE></P>
  72. <P></P>
  73. <LI><STRONG>)</STRONG><BR>
  74.  
  75. <CODE>SUM_{i=0}^{+infinity} ( a[i] )</CODE>
  76. <P>exists, is well-defined and unique</P>
  77. <P><CODE>for all a[i] in S</CODE></P>
  78. <P>and associativity, commutativity and idempotency hold</P>
  79. <P></P>
  80. <LI><STRONG>)</STRONG><BR>
  81.  
  82. Distributivity for infinite series also holds, i.e.,
  83. <PRE>
  84.   ( SUM_{i=0}^{+infty} a[i] ) . ( SUM_{j=0}^{+infty} b[j] )
  85.   = SUM_{i=0}^{+infty} ( SUM_{j=0}^{+infty} ( a[i] . b[j] ) )</PRE>
  86. <P></P></OL>
  87. <P>EXAMPLES:</P>
  88. <UL>
  89. <LI>
  90. <CODE>S1 = ({0,1}, |, &, 0, 1)</CODE>
  91. <P>Boolean Algebra</P>
  92. <P>See also <A HREF="../../../Math/MatrixBool(3).html">the Math::MatrixBool(3) manpage</A></P>
  93. <P></P>
  94. <LI>
  95. <CODE>S2 = (pos. reals with 0 and +infty, min, +, +infty, 0)</CODE>
  96. <P>Positive real numbers including zero and plus infinity</P>
  97. <P>See also <A HREF="../../../Math/MatrixReal(3).html">the Math::MatrixReal(3) manpage</A></P>
  98. <P></P>
  99. <LI>
  100. <CODE>S3 = (Pot(Sigma*), union, concat, {}, {''})</CODE>
  101. <P>Formal languages over Sigma (= alphabet)</P>
  102. <P>See also <A HREF="../../../DFA/Kleene(3).html">the DFA::Kleene(3) manpage</A></P>
  103. <P></P></UL>
  104. <P>
  105. <H2><A NAME="operator '*'"><STRONG>Operator '*'</STRONG></A></H2>
  106. <P>(reflexive and transitive closure)</P>
  107. <P>Define an operator called ``*'' as follows:</P>
  108. <PRE>
  109.     a in S   ==>   a*  :=  SUM_{i=0}^{+infty} a^i</PRE>
  110. <P>where</P>
  111. <PRE>
  112.     a^0  =  1,   a^(i+1)  =  a . a^i</PRE>
  113. <P>Then, also</P>
  114. <PRE>
  115.     a*  =  1 + a . a*,   0*  =  1*  =  1</PRE>
  116. <P>hold.</P>
  117. <P>
  118. <H2><A NAME="kleene's algorithm"><STRONG>Kleene's Algorithm</STRONG></A></H2>
  119. <P>In its general form, Kleene's algorithm goes as follows:</P>
  120. <PRE>
  121.     for i := 1 to n do
  122.         for j := 1 to n do
  123.         begin
  124.             C^0[i,j] := m(v[i],v[j]);
  125.             if (i = j) then C^0[i,j] := C^0[i,j] + 1
  126.         end
  127.     for k := 1 to n do
  128.         for i := 1 to n do
  129.             for j := 1 to n do
  130.                 C^k[i,j] := C^k-1[i,j] + 
  131.                             C^k-1[i,k] . ( C^k-1[k,k] )* . C^k-1[k,j]
  132.     for i := 1 to n do
  133.         for j := 1 to n do
  134.             c(v[i],v[j]) := C^n[i,j]</PRE>
  135. <P>
  136. <H2><A NAME="kleene's algorithm and semirings"><STRONG>Kleene's Algorithm and Semi-Rings</STRONG></A></H2>
  137. <P>Kleene's algorithm can be applied to any Semi-Ring having the properties
  138. listed previously (above). (!)</P>
  139. <P>EXAMPLES:</P>
  140. <UL>
  141. <LI>
  142. <CODE>S1 = ({0,1}, |, &, 0, 1)</CODE>
  143. <P><CODE>G(V,E)</CODE> be a graph with set of vortices V and set of edges E:</P>
  144. <P><A HREF="../../../lib/Pod/perlfunc.html#item_m"><CODE>m(v[i],v[j])  :=  ( (v[i],v[j]) in E ) ? 1 : 0</CODE></A></P>
  145. <P>Kleene's algorithm then calculates</P>
  146. <P><CODE>c^{n}_{i,j} = ( path from v[i] to v[j] exists ) ? 1 : 0</CODE></P>
  147. <P>using</P>
  148. <P><CODE>C^k[i,j]  =  C^k-1[i,j]  |  C^k-1[i,k]  &  C^k-1[k,j]</CODE></P>
  149. <P>(remember <CODE> 0*  =  1*  =  1 </CODE>)</P>
  150. <P></P>
  151. <LI>
  152. <CODE>S2 = (pos. reals with 0 and +infty, min, +, +infty, 0)</CODE>
  153. <P><CODE>G(V,E)</CODE> be a graph with set of vortices V and set of edges E, with
  154. costs <A HREF="../../../lib/Pod/perlfunc.html#item_m"><CODE>m(v[i],v[j])</CODE></A> associated with each edge <CODE>(v[i],v[j])</CODE> in E:</P>
  155. <P><A HREF="../../../lib/Pod/perlfunc.html#item_m"><CODE>m(v[i],v[j])  :=  costs of (v[i],v[j])</CODE></A></P>
  156. <P><CODE>for all (v[i],v[j]) in E</CODE></P>
  157. <P>Set <A HREF="../../../lib/Pod/perlfunc.html#item_m"><CODE>m(v[i],v[j]) := +infinity</CODE></A> if an edge (v[i],v[j]) is not in E.</P>
  158. <P><CODE>  ==>  a* = 0  for all a in S2</CODE></P>
  159. <P><CODE>  ==>  C^k[i,j]  =  min( C^k-1[i,j] ,</CODE></P>
  160. <P><CODE>           C^k-1[i,k]  +  C^k-1[k,j] )</CODE></P>
  161. <P>Kleene's algorithm then calculates the costs of the ``shortest'' path
  162. from any <CODE>v[i]</CODE> to any other <CODE>v[j]</CODE>:</P>
  163. <P><CODE>C^n[i,j] = costs of "shortest" path from v[i] to v[j]</CODE></P>
  164. <P></P>
  165. <LI>
  166. <CODE>S3 = (Pot(Sigma*), union, concat, {}, {''})</CODE>
  167. <P><CODE>M in DFA(Sigma)</CODE> be a Deterministic Finite Automaton with a set of
  168. states <CODE>Q</CODE>, a subset <CODE>F</CODE> of <CODE>Q</CODE> of accepting states and a transition
  169. function <CODE>delta : Q x Sigma --> Q</CODE>.</P>
  170. <P>Define</P>
  171. <P><A HREF="../../../lib/Pod/perlfunc.html#item_m"><CODE>m(v[i],v[j])  :=</CODE></A></P>
  172. <P><CODE>    { a in Sigma | delta( q[i] , a ) = q[j] }</CODE></P>
  173. <P>and</P>
  174. <P><A HREF="../../../lib/Pod/perlfunc.html#item_m"><CODE>C^0[i,j] := m(v[i],v[j]);</CODE></A></P>
  175. <P><CODE>if (i = j) then C^0[i,j] := C^0[i,j] union {''}</CODE></P>
  176. <P>(<CODE>{''}</CODE> is the set containing the empty string, whereas <CODE>{}</CODE> is the
  177. empty set!)</P>
  178. <P>Then Kleene's algorithm calculates the language accepted by Deterministic
  179. Finite Automaton M using</P>
  180. <P><CODE>C^k[i,j] = C^k-1[i,j] union</CODE></P>
  181. <P><CODE>    C^k-1[i,k] concat ( C^k-1[k,k] )* concat C^k-1[k,j]</CODE></P>
  182. <P>and</P>
  183. <P><CODE>L(M)  =  UNION_{ q[j] in F }  C^n[1,j]</CODE></P>
  184. <P>(state <CODE>q[1]</CODE> is assumed to be the ``start'' state)</P>
  185. <P>finally being the language recognized by Deterministic Finite Automaton M.</P>
  186. <P></P></UL>
  187. <P>Note that instead of using Kleene's algorithm, you can also use the ``*''
  188. operator on the associated matrix:</P>
  189. <P>Define  <A HREF="../../../lib/Pod/perlfunc.html#item_m"><CODE>A[i,j]  :=  m(v[i],v[j])</CODE></A></P>
  190. <P><CODE>  ==>   A*[i,j]  =  c(v[i],v[j])</CODE></P>
  191. <P>Proof:</P>
  192. <P><CODE>A*  =  SUM_{i=0}^{+infty} A^i</CODE></P>
  193. <P>where  <CODE>A^0  =  E_{n}</CODE></P>
  194. <P>(matrix with one's in its main diagonal and zero's elsewhere)</P>
  195. <P>and  <CODE>A^(i+1)  =   A . A^i</CODE></P>
  196. <P>Induction over k yields:</P>
  197. <P><CODE>A^k[i,j]  =  c_{k}(v[i],v[j])</CODE></P>
  198. <DL>
  199. <DT><STRONG><A NAME="item_k_%3D_0%3A"><CODE>k = 0:</CODE></A></STRONG><BR>
  200. <DD>
  201. <CODE>c_{0}(v[i],v[j])  =  d_{i,j}</CODE>
  202. <P>with  <CODE>d_{i,j}  :=  (i = j) ? 1 : 0</CODE></P>
  203. <P>and  <CODE>A^0  =  E_{n}  =  [d_{i,j}]</CODE></P>
  204. <P></P>
  205. <DT><STRONG><A NAME="item_k"><CODE>k-1 -> k:</CODE></A></STRONG><BR>
  206. <DD>
  207. <CODE>c_{k}(v[i],v[j])</CODE>
  208. <P><A HREF="../../../lib/Pod/perlfunc.html#item_m"><CODE>= SUM_{l=1}^{n} m(v[i],v[l]) . c_{k-1}(v[l],v[j])</CODE></A></P>
  209. <P><CODE>= SUM_{l=1}^{n} ( a[i,l] . a[l,j] )</CODE></P>
  210. <P><CODE>= [a^{k}_{i,j}]  =  A^1 . A^(k-1)  =  A^k</CODE></P>
  211. <P></P></DL>
  212. <P>qed</P>
  213. <P>In other words, the complexity of calculating the closure and doing
  214. matrix multiplications is of the same order <CODE>O( n^3 )</CODE> in Semi-Rings!</P>
  215. <P>
  216. <HR>
  217. <H1><A NAME="see also">SEE ALSO</A></H1>
  218. <P>Math::MatrixBool(3), Math::MatrixReal(3), DFA::Kleene(3).</P>
  219. <P>(All contained in the distribution of the ``Set::IntegerFast'' module)</P>
  220. <P>Dijkstra's algorithm for shortest paths.</P>
  221. <P>
  222. <HR>
  223. <H1><A NAME="author">AUTHOR</A></H1>
  224. <P>This document is based on lecture notes and has been put into
  225. POD format by Steffen Beyer <<A HREF="mailto:sb@sdm.de">sb@sdm.de</A>>.</P>
  226. <P>
  227. <HR>
  228. <H1><A NAME="copyright">COPYRIGHT</A></H1>
  229. <P>Copyright (c) 1997 by Steffen Beyer. All rights reserved.</P>
  230. <TABLE BORDER=0 CELLPADDING=0 CELLSPACING=0 WIDTH=100%>
  231. <TR><TD CLASS=block VALIGN=MIDDLE WIDTH=100% BGCOLOR="#cccccc">
  232. <STRONG><P CLASS=block> Algorithm - the theory behind it</P></STRONG>
  233. </TD></TR>
  234. </TABLE>
  235.  
  236. </BODY>
  237.  
  238. </HTML>
  239.