projects / OpenSPARC-T2-DV / blame
? search:
summary | tags | clone url | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Initial commit of OpenSPARC T2 design and verification files.
[OpenSPARC-T2-DV] / tools / perl-5.8.0 / man / man3 / Math::Kleene.3
CommitLineData
86530b38
AT		 1.\" Automatically generated by Pod::Man v1.34, Pod::Parser v1.13
2.\"
3.\" Standard preamble:
4.\" ========================================================================
5.de Sh \" Subsection heading
6.br
7.if t .Sp
8.ne 5
9.PP
10\fB\\$1\fR
11.PP
12..
13.de Sp \" Vertical space (when we can't use .PP)
14.if t .sp .5v
15.if n .sp
16..
17.de Vb \" Begin verbatim text
18.ft CW
19.nf
20.ne \\$1
21..
22.de Ve \" End verbatim text
23.ft R
24.fi
25..
26.\" Set up some character translations and predefined strings. \*(-- will
27.\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
28.\" double quote, and \*(R" will give a right double quote. | will give a
29.\" real vertical bar. \*(C+ will give a nicer C++. Capital omega is used to
30.\" do unbreakable dashes and therefore won't be available. \*(C` and \*(C'
31.\" expand to `' in nroff, nothing in troff, for use with C<>.
32.tr \(*W-|\(bv\*(Tr
33.ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
34.ie n \{\
35. ds -- \(*W-
36. ds PI pi
37. if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
38. if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch
39. ds L" ""
40. ds R" ""
41. ds C` ""
42. ds C' ""
43'br\}
44.el\{\
45. ds -- \|\(em\|
46. ds PI \(*p
47. ds L" ``
48. ds R" ''
49'br\}
50.\"
51.\" If the F register is turned on, we'll generate index entries on stderr for
52.\" titles (.TH), headers (.SH), subsections (.Sh), items (.Ip), and index
53.\" entries marked with X<> in POD. Of course, you'll have to process the
54.\" output yourself in some meaningful fashion.
55.if \nF \{\
56. de IX
57. tm Index:\\$1\t\\n%\t"\\$2"
58..
59. nr % 0
60. rr F
61.\}
62.\"
63.\" For nroff, turn off justification. Always turn off hyphenation; it makes
64.\" way too many mistakes in technical documents.
65.hy 0
66.if n .na
67.\"
68.\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2).
69.\" Fear. Run. Save yourself. No user-serviceable parts.
70. \" fudge factors for nroff and troff
71.if n \{\
72. ds #H 0
73. ds #V .8m
74. ds #F .3m
75. ds #[ \f1
76. ds #] \fP
77.\}
78.if t \{\
79. ds #H ((1u-(\\\\n(.fu%2u))*.13m)
80. ds #V .6m
81. ds #F 0
82. ds #[ \&
83. ds #] \&
84.\}
85. \" simple accents for nroff and troff
86.if n \{\
87. ds ' \&
88. ds ` \&
89. ds ^ \&
90. ds , \&
91. ds ~ ~
92. ds /
93.\}
94.if t \{\
95. ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
96. ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
97. ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
98. ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
99. ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
100. ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
101.\}
102. \" troff and (daisy-wheel) nroff accents
103.ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
104.ds 8 \h'\*(#H'\(*b\h'-\*(#H'
105.ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
106.ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
107.ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
108.ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
109.ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
110.ds ae a\h'-(\w'a'u*4/10)'e
111.ds Ae A\h'-(\w'A'u*4/10)'E
112. \" corrections for vroff
113.if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
114.if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
115. \" for low resolution devices (crt and lpr)
116.if \n(.H>23 .if \n(.V>19 \
117\{\
118. ds : e
119. ds 8 ss
120. ds o a
121. ds d- d\h'-1'\(ga
122. ds D- D\h'-1'\(hy
123. ds th \o'bp'
124. ds Th \o'LP'
125. ds ae ae
126. ds Ae AE
127.\}
128.rm #[ #] #H #V #F C
129.\" ========================================================================
130.\"
131.IX Title "KLEENE 1"
132.TH KLEENE 1 "2001-12-12" "perl v5.8.0" "User Contributed Perl Documentation"
133.SH "NAME"
134Kleene's Algorithm \- the theory behind it
135.PP
136brief introduction
137.SH "DESCRIPTION"
138.IX Header "DESCRIPTION"
139.Sh "\fBSemi-Rings\fP"
140.IX Subsection "Semi-Rings"
141A Semi-Ring (S, +, ., 0, 1) is characterized by the following properties:
142.IP "1)" 4
143a) \f(CW\*(C`(S, +, 0) is a Semi\-Group with neutral element 0\*(C'\fR
144.Sp
145b) \f(CW\*(C`(S, ., 1) is a Semi\-Group with neutral element 1\*(C'\fR
146.Sp
147c) \f(CW\*(C`0 . a = a . 0 = 0 for all a in S\*(C'\fR
148.IP "2)" 4
149\&\f(CW"+"\fR is commutative and \fBidempotent\fR, i.e., \f(CW\*(C`a + a = a\*(C'\fR
150.IP "3)" 4
151Distributivity holds, i.e.,
152.Sp
153a) \f(CW\*(C`a . ( b + c ) = a . b + a . c for all a,b,c in S\*(C'\fR
154.Sp
155b) \f(CW\*(C`( a + b ) . c = a . c + b . c for all a,b,c in S\*(C'\fR
156.IP "4)" 4
157\&\f(CW\*(C`SUM_{i=0}^{+infinity} ( a[i] )\*(C'\fR
158.Sp
159exists, is well-defined and unique
160.Sp
161\&\f(CW\*(C`for all a[i] in S\*(C'\fR
162.Sp
163and associativity, commutativity and idempotency hold
164.IP "5)" 4
165Distributivity for infinite series also holds, i.e.,
166.Sp
167.Vb 2
168\& ( SUM_{i=0}^{+infty} a[i] ) . ( SUM_{j=0}^{+infty} b[j] )
169\& = SUM_{i=0}^{+infty} ( SUM_{j=0}^{+infty} ( a[i] . b[j] ) )
170.Ve
171.PP
172\&\s-1EXAMPLES:\s0
173.IP "\(bu" 4
174\&\f(CW\*(C`S1 = ({0,1}, |, &, 0, 1)\*(C'\fR
175.Sp
176Boolean Algebra
177.Sp
178See also \fIMath::MatrixBool\fR\|(3)
179.IP "\(bu" 4
180\&\f(CW\*(C`S2 = (pos. reals with 0 and +infty, min, +, +infty, 0)\*(C'\fR
181.Sp
182Positive real numbers including zero and plus infinity
183.Sp
184See also \fIMath::MatrixReal\fR\|(3)
185.IP "\(bu" 4
186\&\f(CW\*(C`S3 = (Pot(Sigma*), union, concat, {}, {''})\*(C'\fR
187.Sp
188Formal languages over Sigma (= alphabet)
189.Sp
190See also \fIDFA::Kleene\fR\|(3)
191.Sh "\fBOperator '*'\fP"
192.IX Subsection "Operator '*'"
193(reflexive and transitive closure)
194.PP
195Define an operator called \*(L"*\*(R" as follows:
196.PP
197.Vb 1
198\& a in S ==> a* := SUM_{i=0}^{+infty} a^i
199.Ve
200.PP
201where
202.PP
203.Vb 1
204\& a^0 = 1, a^(i+1) = a . a^i
205.Ve
206.PP
207Then, also
208.PP
209.Vb 1
210\& a* = 1 + a . a*, 0* = 1* = 1
211.Ve
212.PP
213hold.
214.Sh "\fBKleene's Algorithm\fP"
215.IX Subsection "Kleene's Algorithm"
216In its general form, Kleene's algorithm goes as follows:
217.PP
218.Vb 14
219\& for i := 1 to n do
220\& for j := 1 to n do
221\& begin
222\& C^0[i,j] := m(v[i],v[j]);
223\& if (i = j) then C^0[i,j] := C^0[i,j] + 1
224\& end
225\& for k := 1 to n do
226\& for i := 1 to n do
227\& for j := 1 to n do
228\& C^k[i,j] := C^k-1[i,j] +
229\& C^k-1[i,k] . ( C^k-1[k,k] )* . C^k-1[k,j]
230\& for i := 1 to n do
231\& for j := 1 to n do
232\& c(v[i],v[j]) := C^n[i,j]
233.Ve
234.Sh "\fBKleene's Algorithm and Semi-Rings\fP"
235.IX Subsection "Kleene's Algorithm and Semi-Rings"
236Kleene's algorithm can be applied to any Semi-Ring having the properties
237listed previously (above). (!)
238.PP
239\&\s-1EXAMPLES:\s0
240.IP "\(bu" 4
241\&\f(CW\*(C`S1 = ({0,1}, |, &, 0, 1)\*(C'\fR
242.Sp
243\&\f(CW\*(C`G(V,E)\*(C'\fR be a graph with set of vortices V and set of edges E:
244.Sp
245\&\f(CW\*(C`m(v[i],v[j]) := ( (v[i],v[j]) in E ) ? 1 : 0\*(C'\fR
246.Sp
247Kleene's algorithm then calculates
248.Sp
249\&\f(CW\*(C`c^{n}_{i,j} = ( path from v[i] to v[j] exists ) ? 1 : 0\*(C'\fR
250.Sp
251using
252.Sp
253\&\f(CW\*(C`C^k[i,j] = C^k\-1[i,j] | C^k\-1[i,k] & C^k\-1[k,j]\*(C'\fR
254.Sp
255(remember \f(CW\*(C` 0* = 1* = 1 \*(C'\fR)
256.IP "\(bu" 4
257\&\f(CW\*(C`S2 = (pos. reals with 0 and +infty, min, +, +infty, 0)\*(C'\fR
258.Sp
259\&\f(CW\*(C`G(V,E)\*(C'\fR be a graph with set of vortices V and set of edges E, with
260costs \f(CW\*(C`m(v[i],v[j])\*(C'\fR associated with each edge \f(CW\*(C`(v[i],v[j])\*(C'\fR in E:
261.Sp
262\&\f(CW\*(C`m(v[i],v[j]) := costs of (v[i],v[j])\*(C'\fR
263.Sp
264\&\f(CW\*(C`for all (v[i],v[j]) in E\*(C'\fR
265.Sp
266Set \f(CW\*(C`m(v[i],v[j]) := +infinity\*(C'\fR if an edge (v[i],v[j]) is not in E.
267.Sp
268\&\f(CW\*(C` ==> a* = 0 for all a in S2\*(C'\fR
269.Sp
270\&\f(CW\*(C` ==> C^k[i,j] = min( C^k\-1[i,j] ,\*(C'\fR
271.Sp
272\&\f(CW\*(C` C^k\-1[i,k] + C^k\-1[k,j] )\*(C'\fR
273.Sp
274Kleene's algorithm then calculates the costs of the \*(L"shortest\*(R" path
275from any \f(CW\*(C`v[i]\*(C'\fR to any other \f(CW\*(C`v[j]\*(C'\fR:
276.Sp
277\&\f(CW\*(C`C^n[i,j] = costs of "shortest" path from v[i] to v[j]\*(C'\fR
278.IP "\(bu" 4
279\&\f(CW\*(C`S3 = (Pot(Sigma*), union, concat, {}, {''})\*(C'\fR
280.Sp
281\&\f(CW\*(C`M in DFA(Sigma)\*(C'\fR be a Deterministic Finite Automaton with a set of
282states \f(CW\*(C`Q\*(C'\fR, a subset \f(CW\*(C`F\*(C'\fR of \f(CW\*(C`Q\*(C'\fR of accepting states and a transition
283function \f(CW\*(C`delta : Q x Sigma \-\-> Q\*(C'\fR.
284.Sp
285Define
286.Sp
287\&\f(CW\*(C`m(v[i],v[j]) :=\*(C'\fR
288.Sp
289\&\f(CW\*(C` { a in Sigma | delta( q[i] , a ) = q[j] }\*(C'\fR
290.Sp
291and
292.Sp
293\&\f(CW\*(C`C^0[i,j] := m(v[i],v[j]);\*(C'\fR
294.Sp
295\&\f(CW\*(C`if (i = j) then C^0[i,j] := C^0[i,j] union {''}\*(C'\fR
296.Sp
297(\f(CW\*(C`{''}\*(C'\fR is the set containing the empty string, whereas \f(CW\*(C`{}\*(C'\fR is the
298empty set!)
299.Sp
300Then Kleene's algorithm calculates the language accepted by Deterministic
301Finite Automaton M using
302.Sp
303\&\f(CW\*(C`C^k[i,j] = C^k\-1[i,j] union\*(C'\fR
304.Sp
305\&\f(CW\*(C` C^k\-1[i,k] concat ( C^k\-1[k,k] )* concat C^k\-1[k,j]\*(C'\fR
306.Sp
307and
308.Sp
309\&\f(CW\*(C`L(M) = UNION_{ q[j] in F } C^n[1,j]\*(C'\fR
310.Sp
311(state \f(CW\*(C`q[1]\*(C'\fR is assumed to be the \*(L"start\*(R" state)
312.Sp
313finally being the language recognized by Deterministic Finite Automaton M.
314.PP
315Note that instead of using Kleene's algorithm, you can also use the \*(L"*\*(R"
316operator on the associated matrix:
317.PP
318Define \f(CW\*(C`A[i,j] := m(v[i],v[j])\*(C'\fR
319.PP
320\&\f(CW\*(C` ==> A*[i,j] = c(v[i],v[j])\*(C'\fR
321.PP
322Proof:
323.PP
324\&\f(CW\*(C`A* = SUM_{i=0}^{+infty} A^i\*(C'\fR
325.PP
326where \f(CW\*(C`A^0 = E_{n}\*(C'\fR
327.PP
328(matrix with one's in its main diagonal and zero's elsewhere)
329.PP
330and \f(CW\*(C`A^(i+1) = A . A^i\*(C'\fR
331.PP
332Induction over k yields:
333.PP
334\&\f(CW\*(C`A^k[i,j] = c_{k}(v[i],v[j])\*(C'\fR
335.ie n .IP """k = 0:""" 10
336.el .IP "\f(CWk = 0:\fR" 10
337.IX Item "k = 0:"
338\&\f(CW\*(C`c_{0}(v[i],v[j]) = d_{i,j}\*(C'\fR
339.Sp
340with \f(CW\*(C`d_{i,j} := (i = j) ? 1 : 0\*(C'\fR
341.Sp
342and \f(CW\*(C`A^0 = E_{n} = [d_{i,j}]\*(C'\fR
343.ie n .IP """k\-1 \-> k:""" 10
344.el .IP "\f(CWk\-1 \-> k:\fR" 10
345.IX Item "k-1 -> k:"
346\&\f(CW\*(C`c_{k}(v[i],v[j])\*(C'\fR
347.Sp
348\&\f(CW\*(C`= SUM_{l=1}^{n} m(v[i],v[l]) . c_{k\-1}(v[l],v[j])\*(C'\fR
349.Sp
350\&\f(CW\*(C`= SUM_{l=1}^{n} ( a[i,l] . a[l,j] )\*(C'\fR
351.Sp
352\&\f(CW\*(C`= [a^{k}_{i,j}] = A^1 . A^(k\-1) = A^k\*(C'\fR
353.PP
354qed
355.PP
356In other words, the complexity of calculating the closure and doing
357matrix multiplications is of the same order \f(CW\*(C`O(\ n^3\ )\*(C'\fR in Semi\-Rings!
358.SH "SEE ALSO"
359.IX Header "SEE ALSO"
360\&\fIMath::MatrixBool\fR\|(3), \fIMath::MatrixReal\fR\|(3), \fIDFA::Kleene\fR\|(3).
361.PP
362(All contained in the distribution of the \*(L"Set::IntegerFast\*(R" module)
363.PP
364Dijkstra's algorithm for shortest paths.
365.SH "AUTHOR"
366.IX Header "AUTHOR"
367This document is based on lecture notes and has been put into
368\&\s-1POD\s0 format by Steffen Beyer <sb@engelschall.com>.
369.SH "COPYRIGHT"
370.IX Header "COPYRIGHT"
371Copyright (c) 1997 by Steffen Beyer. All rights reserved.
Full OpenSPARC design & verification tarball including full HDL.