Mercurial > hg > Papers > 2010 > jsst-shinya

changeset 2:3bf6db862bc7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ver:1
author Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
date Fri, 13 Aug 2010 22:11:43 +0900
parents e79cdc772194
children b00e4e5b5368
files fig1.eps fig2.eps fig3.eps fig4.eps paper.pdf paper.tex
diffstat 6 files changed, 533 insertions(+), 171 deletions(-) [+]
line wrap: on
line diff
--- a/fig1.eps	Thu Aug 12 04:55:49 2010 +0900
+++ b/fig1.eps	Fri Aug 13 22:11:43 2010 +0900
@@ -2,7 +2,7 @@
 %%Creator: graphviz version 2.26.3 (20100126.1600)
 %%Title: G
 %%Pages: 1
-%%BoundingBox: 36 36 284 125
+%%BoundingBox: 36 36 380 125
 %%EndComments
 save
 %%BeginProlog
@@ -178,17 +178,17 @@
 %%EndSetup
 setupLatin1
 %%Page: 1 1
-%%PageBoundingBox: 36 36 284 125
+%%PageBoundingBox: 36 36 380 125
 %%PageOrientation: Portrait
 0 0 1 beginpage
 gsave
-36 36 248 89 boxprim clip newpath
+36 36 344 89 boxprim clip newpath
 1 1 set_scale 0 rotate 40 41 translate
 % regex
 gsave
 0 0 0 nodecolor
 14 /Times-Roman set_font
-21.5 12.9 moveto 11 (A) alignedtext
+16.5 12.9 moveto 21 (AB) alignedtext
 grestore
 % q0
 gsave
@@ -205,42 +205,77 @@
 % q1
 gsave
 0 0 1 nodecolor
-215 56 20.8 20.8 ellipse_path fill
+211 56 20.8 20.8 ellipse_path fill
 1 setlinewidth
 filled
 0 0 0 nodecolor
-215 56 20.8 20.8 ellipse_path stroke
-1 setlinewidth
-filled
-0 0 0 nodecolor
-215 56 24.8 24.8 ellipse_path stroke
+211 56 20.8 20.8 ellipse_path stroke
 0 0 0 nodecolor
 14 /Times-Roman set_font
-207 50.9 moveto 16 (q1) alignedtext
+203 50.9 moveto 16 (q1) alignedtext
 grestore
 % q0->q1
 gsave
 1 setlinewidth
 0 0 0 edgecolor
-newpath 134.13 56 moveto
-147.31 56 164.6 56 179.81 56 curveto
+newpath 134.26 56 moveto
+147.49 56 164.74 56 179.53 56 curveto
 stroke
 0 0 0 edgecolor
-newpath 179.93 59.5 moveto
-189.93 56 lineto
-179.93 52.5 lineto
+newpath 179.78 59.5 moveto
+189.78 56 lineto
+179.78 52.5 lineto
 closepath fill
 1 setlinewidth
 solid
 0 0 0 edgecolor
-newpath 179.93 59.5 moveto
-189.93 56 lineto
-179.93 52.5 lineto
+newpath 179.78 59.5 moveto
+189.78 56 lineto
+179.78 52.5 lineto
 closepath stroke
 0 0 0 edgecolor
 14 /Times-Roman set_font
 152.5 58.4 moveto 19 ('A') alignedtext
 grestore
+% q2
+gsave
+0 0 1 nodecolor
+311 56 20.8 20.8 ellipse_path fill
+1 setlinewidth
+filled
+0 0 0 nodecolor
+311 56 20.8 20.8 ellipse_path stroke
+1 setlinewidth
+filled
+0 0 0 nodecolor
+311 56 24.8 24.8 ellipse_path stroke
+0 0 0 nodecolor
+14 /Times-Roman set_font
+303 50.9 moveto 16 (q2) alignedtext
+grestore
+% q1->q2
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 232.21 56 moveto
+244.85 56 261.21 56 275.75 56 curveto
+stroke
+0 0 0 edgecolor
+newpath 275.94 59.5 moveto
+285.94 56 lineto
+275.94 52.5 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 275.94 59.5 moveto
+285.94 56 lineto
+275.94 52.5 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+250 58.4 moveto 18 ('B') alignedtext
+grestore
 % start
 gsave
 0 0 0 nodecolor
--- a/fig2.eps	Thu Aug 12 04:55:49 2010 +0900
+++ b/fig2.eps	Fri Aug 13 22:11:43 2010 +0900
@@ -2,7 +2,7 @@
 %%Creator: graphviz version 2.26.3 (20100126.1600)
 %%Title: G
 %%Pages: 1
-%%BoundingBox: 36 36 284 125
+%%BoundingBox: 36 36 364 160
 %%EndComments
 save
 %%BeginProlog
@@ -178,11 +178,11 @@
 %%EndSetup
 setupLatin1
 %%Page: 1 1
-%%PageBoundingBox: 36 36 284 125
+%%PageBoundingBox: 36 36 364 160
 %%PageOrientation: Portrait
 0 0 1 beginpage
 gsave
-36 36 248 89 boxprim clip newpath
+36 36 328 124 boxprim clip newpath
 1 1 set_scale 0 rotate 40 41 translate
 % regex
 gsave
@@ -193,6 +193,92 @@
 % q0
 gsave
 0 0 1 nodecolor
+193 95 20.8 20.8 ellipse_path fill
+1 setlinewidth
+filled
+0 0 0 nodecolor
+193 95 20.8 20.8 ellipse_path stroke
+0 0 0 nodecolor
+14 /Times-Roman set_font
+185 89.9 moveto 16 (q0) alignedtext
+grestore
+% q3
+gsave
+0 0 1 nodecolor
+295 67 20.8 20.8 ellipse_path fill
+1 setlinewidth
+filled
+0 0 0 nodecolor
+295 67 20.8 20.8 ellipse_path stroke
+1 setlinewidth
+filled
+0 0 0 nodecolor
+295 67 24.8 24.8 ellipse_path stroke
+0 0 0 nodecolor
+14 /Times-Roman set_font
+287 61.9 moveto 16 (q3) alignedtext
+grestore
+% q0->q3
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 213.64 89.33 moveto
+227.2 85.61 245.27 80.65 260.93 76.35 curveto
+stroke
+0 0 0 edgecolor
+newpath 262.09 79.66 moveto
+270.8 73.64 lineto
+260.23 72.91 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 262.09 79.66 moveto
+270.8 73.64 lineto
+260.23 72.91 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+232.5 85.4 moveto 19 ('A') alignedtext
+grestore
+% q1
+gsave
+0 0 1 nodecolor
+193 35 20.8 20.8 ellipse_path fill
+1 setlinewidth
+filled
+0 0 0 nodecolor
+193 35 20.8 20.8 ellipse_path stroke
+0 0 0 nodecolor
+14 /Times-Roman set_font
+185 29.9 moveto 16 (q1) alignedtext
+grestore
+% q1->q3
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 213.15 41.32 moveto
+226.77 45.6 245.1 51.34 260.95 56.32 curveto
+stroke
+0 0 0 edgecolor
+newpath 260.35 59.8 moveto
+270.94 59.45 lineto
+262.45 53.12 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 260.35 59.8 moveto
+270.94 59.45 lineto
+262.45 53.12 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+233 54.4 moveto 18 ('B') alignedtext
+grestore
+% q2
+gsave
+0 0 1 nodecolor
 113 56 20.8 20.8 ellipse_path fill
 1 setlinewidth
 filled
@@ -200,70 +286,47 @@
 113 56 20.8 20.8 ellipse_path stroke
 0 0 0 nodecolor
 14 /Times-Roman set_font
-105 50.9 moveto 16 (q0) alignedtext
+105 50.9 moveto 16 (q2) alignedtext
 grestore
-% q1
-gsave
-0 0 1 nodecolor
-215 56 20.8 20.8 ellipse_path fill
-1 setlinewidth
-filled
-0 0 0 nodecolor
-215 56 20.8 20.8 ellipse_path stroke
-1 setlinewidth
-filled
-0 0 0 nodecolor
-215 56 24.8 24.8 ellipse_path stroke
-0 0 0 nodecolor
-14 /Times-Roman set_font
-207 50.9 moveto 16 (q1) alignedtext
-grestore
-% q0->q1
+% q2->q0
 gsave
 1 setlinewidth
 0 0 0 edgecolor
-newpath 134.13 56 moveto
-147.31 56 164.6 56 179.81 56 curveto
+newpath 131.96 65.24 moveto
+141.75 70.02 153.89 75.94 164.77 81.24 curveto
 stroke
 0 0 0 edgecolor
-newpath 179.93 59.5 moveto
-189.93 56 lineto
-179.93 52.5 lineto
+newpath 163.38 84.45 moveto
+173.9 85.69 lineto
+166.44 78.16 lineto
 closepath fill
 1 setlinewidth
 solid
 0 0 0 edgecolor
-newpath 179.93 59.5 moveto
-189.93 56 lineto
-179.93 52.5 lineto
+newpath 163.38 84.45 moveto
+173.9 85.69 lineto
+166.44 78.16 lineto
 closepath stroke
-0 0 0 edgecolor
-14 /Times-Roman set_font
-152.5 58.4 moveto 19 ('A') alignedtext
 grestore
-% q0->q1
+% q2->q1
 gsave
 1 setlinewidth
 0 0 0 edgecolor
-newpath 131.01 45.12 moveto
-137.41 41.83 144.81 38.66 152 37 curveto
-162.35 34.61 173.5 36.47 183.49 39.8 curveto
+newpath 133.6 50.59 moveto
+142.47 48.26 153.01 45.5 162.73 42.94 curveto
 stroke
 0 0 0 edgecolor
-newpath 182.45 43.14 moveto
-193.03 43.52 lineto
-184.99 36.62 lineto
+newpath 163.68 46.31 moveto
+172.47 40.39 lineto
+161.91 39.54 lineto
 closepath fill
 1 setlinewidth
 solid
 0 0 0 edgecolor
-newpath 182.45 43.14 moveto
-193.03 43.52 lineto
-184.99 36.62 lineto
+newpath 163.68 46.31 moveto
+172.47 40.39 lineto
+161.91 39.54 lineto
 closepath stroke
-0 0 0 edgecolor
-14 /Times-Roman set_font
-153 39.4 moveto 18 ('B') alignedtext
 grestore
 % start
 gsave
@@ -274,7 +337,7 @@
 0 0 0 nodecolor
 27 56 1.8 1.8 ellipse_path stroke
 grestore
-% start->q0
+% start->q2
 gsave
 1 setlinewidth
 0 0 0 edgecolor
--- a/fig3.eps	Thu Aug 12 04:55:49 2010 +0900
+++ b/fig3.eps	Fri Aug 13 22:11:43 2010 +0900
@@ -2,7 +2,7 @@
 %%Creator: graphviz version 2.26.3 (20100126.1600)
 %%Title: G
 %%Pages: 1
-%%BoundingBox: 36 36 186 158
+%%BoundingBox: 36 36 243 194
 %%EndComments
 save
 %%BeginProlog
@@ -178,85 +178,148 @@
 %%EndSetup
 setupLatin1
 %%Page: 1 1
-%%PageBoundingBox: 36 36 186 158
+%%PageBoundingBox: 36 36 243 194
 %%PageOrientation: Portrait
 0 0 1 beginpage
 gsave
-36 36 150 122 boxprim clip newpath
+36 36 207 158 boxprim clip newpath
 1 1 set_scale 0 rotate 40 41 translate
 % regex
 gsave
 0 0 0 nodecolor
 14 /Times-Roman set_font
-17.5 12.9 moveto 19 (A*) alignedtext
+161.5 52.9 moveto 19 (A*) alignedtext
 grestore
 % q0
 gsave
 0 0 1 nodecolor
-117 56 20.8 20.8 ellipse_path fill
+134 127.71 20.8 20.8 ellipse_path fill
 1 setlinewidth
 filled
 0 0 0 nodecolor
-117 56 20.8 20.8 ellipse_path stroke
+134 127.71 20.8 20.8 ellipse_path stroke
+0 0 0 nodecolor
+14 /Times-Roman set_font
+126 122.61 moveto 16 (q0) alignedtext
+grestore
+% q1
+gsave
+0 0 1 nodecolor
+98 65.35 20.8 20.8 ellipse_path fill
 1 setlinewidth
 filled
 0 0 0 nodecolor
-117 56 24.8 24.8 ellipse_path stroke
+98 65.35 20.8 20.8 ellipse_path stroke
 0 0 0 nodecolor
 14 /Times-Roman set_font
-109 50.9 moveto 16 (q0) alignedtext
+90 60.25 moveto 16 (q1) alignedtext
 grestore
-% q0->q0
+% q0->q1
 gsave
 1 setlinewidth
 0 0 0 edgecolor
-newpath 108.85 79.88 moveto
-108.18 90.18 110.9 99 117 99 curveto
-120.91 99 123.43 95.38 124.56 90.07 curveto
+newpath 129.11 106.93 moveto
+126.28 100.95 122.7 94.41 118.96 88.31 curveto
 stroke
 0 0 0 edgecolor
-newpath 128.07 90.06 moveto
-125.15 79.88 lineto
-121.08 89.66 lineto
+newpath 121.82 86.29 moveto
+113.44 79.81 lineto
+115.95 90.11 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 121.82 86.29 moveto
+113.44 79.81 lineto
+115.95 90.11 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+125.54 86.52 moveto 19 ('A') alignedtext
+grestore
+% q1->q0
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 102.89 86.13 moveto
+105.72 92.11 109.3 98.65 113.04 104.75 curveto
+stroke
+0 0 0 edgecolor
+newpath 110.18 106.77 moveto
+118.56 113.25 lineto
+116.05 102.96 lineto
 closepath fill
 1 setlinewidth
 solid
 0 0 0 edgecolor
-newpath 128.07 90.06 moveto
-125.15 79.88 lineto
-121.08 89.66 lineto
+newpath 110.18 106.77 moveto
+118.56 113.25 lineto
+116.05 102.96 lineto
 closepath stroke
-0 0 0 edgecolor
+grestore
+% q2
+gsave
+0 0 1 nodecolor
+26 65.35 20.8 20.8 ellipse_path fill
+1 setlinewidth
+filled
+0 0 0 nodecolor
+26 65.35 20.8 20.8 ellipse_path stroke
+1 setlinewidth
+filled
+0 0 0 nodecolor
+26 65.35 24.8 24.8 ellipse_path stroke
+0 0 0 nodecolor
 14 /Times-Roman set_font
-107.5 101.4 moveto 19 ('A') alignedtext
+18 60.25 moveto 16 (q2) alignedtext
+grestore
+% q1->q2
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 76.79 65.35 moveto
+71.88 65.35 66.54 65.35 61.21 65.35 curveto
+stroke
+0 0 0 edgecolor
+newpath 61.13 61.85 moveto
+51.13 65.35 lineto
+61.13 68.85 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 61.13 61.85 moveto
+51.13 65.35 lineto
+61.13 68.85 lineto
+closepath stroke
 grestore
 % start
 gsave
 0 0 0 nodecolor
-27 56 1.8 1.8 ellipse_path fill
+134 3 1.8 1.8 ellipse_path fill
 1 setlinewidth
 filled
 0 0 0 nodecolor
-27 56 1.8 1.8 ellipse_path stroke
+134 3 1.8 1.8 ellipse_path stroke
 grestore
-% start->q0
+% start->q1
 gsave
 1 setlinewidth
 0 0 0 edgecolor
-newpath 28.88 56 moveto
-35.73 56 60.11 56 81.49 56 curveto
+newpath 132.96 4.8 moveto
+130.05 9.84 121.5 24.66 113.58 38.37 curveto
 stroke
 0 0 0 edgecolor
-newpath 81.65 59.5 moveto
-91.65 56 lineto
-81.65 52.5 lineto
+newpath 110.51 36.69 moveto
+108.54 47.1 lineto
+116.57 40.19 lineto
 closepath fill
 1 setlinewidth
 solid
 0 0 0 edgecolor
-newpath 81.65 59.5 moveto
-91.65 56 lineto
-81.65 52.5 lineto
+newpath 110.51 36.69 moveto
+108.54 47.1 lineto
+116.57 40.19 lineto
 closepath stroke
 grestore
 endpage
--- a/fig4.eps	Thu Aug 12 04:55:49 2010 +0900
+++ b/fig4.eps	Fri Aug 13 22:11:43 2010 +0900
@@ -2,7 +2,7 @@
 %%Creator: graphviz version 2.26.3 (20100126.1600)
 %%Title: G
 %%Pages: 1
-%%BoundingBox: 36 36 294 187
+%%BoundingBox: 36 36 392 201
 %%EndComments
 save
 %%BeginProlog
@@ -178,144 +178,271 @@
 %%EndSetup
 setupLatin1
 %%Page: 1 1
-%%PageBoundingBox: 36 36 294 187
+%%PageBoundingBox: 36 36 392 201
 %%PageOrientation: Portrait
 0 0 1 beginpage
 gsave
-36 36 258 151 boxprim clip newpath
+36 36 356 165 boxprim clip newpath
 1 1 set_scale 0 rotate 40 41 translate
 % regex
 gsave
 0 0 0 nodecolor
 14 /Times-Roman set_font
-8 12.9 moveto 50 (\(A|B\)*C) alignedtext
+8 29.9 moveto 50 (\(A|B\)*C) alignedtext
 grestore
 % q0
 gsave
 0 0 1 nodecolor
-125 56 20.8 20.8 ellipse_path fill
+33 125 20.8 20.8 ellipse_path fill
+1 setlinewidth
+filled
+0 0 0 nodecolor
+33 125 20.8 20.8 ellipse_path stroke
+0 0 0 nodecolor
+14 /Times-Roman set_font
+25 119.9 moveto 16 (q0) alignedtext
+grestore
+% q3
+gsave
+0 0 1 nodecolor
+143 82 20.8 20.8 ellipse_path fill
 1 setlinewidth
 filled
 0 0 0 nodecolor
-125 56 20.8 20.8 ellipse_path stroke
+143 82 20.8 20.8 ellipse_path stroke
 0 0 0 nodecolor
 14 /Times-Roman set_font
-117 50.9 moveto 16 (q0) alignedtext
+135 76.9 moveto 16 (q3) alignedtext
 grestore
-% q0->q0
+% q0->q3
 gsave
 1 setlinewidth
 0 0 0 edgecolor
-newpath 121.32 76.86 moveto
-120.92 86.54 122.15 95 125 95 curveto
-126.74 95 127.87 91.86 128.4 87.22 curveto
+newpath 52.67 117.31 moveto
+69.61 110.69 94.32 101.03 113.61 93.49 curveto
 stroke
 0 0 0 edgecolor
-newpath 131.91 86.95 moveto
-128.68 76.86 lineto
-124.91 86.77 lineto
+newpath 115.09 96.67 moveto
+123.13 89.77 lineto
+112.55 90.15 lineto
 closepath fill
 1 setlinewidth
 solid
 0 0 0 edgecolor
-newpath 131.91 86.95 moveto
-128.68 76.86 lineto
-124.91 86.77 lineto
+newpath 115.09 96.67 moveto
+123.13 89.77 lineto
+112.55 90.15 lineto
 closepath stroke
 0 0 0 edgecolor
 14 /Times-Roman set_font
-115.5 97.4 moveto 19 ('A') alignedtext
+84.5 106.4 moveto 19 ('A') alignedtext
 grestore
-% q0->q0
+% q1
+gsave
+0 0 1 nodecolor
+323 105 20.8 20.8 ellipse_path fill
+1 setlinewidth
+filled
+0 0 0 nodecolor
+323 105 20.8 20.8 ellipse_path stroke
+0 0 0 nodecolor
+14 /Times-Roman set_font
+315 99.9 moveto 16 (q1) alignedtext
+grestore
+% q1->q3
 gsave
 1 setlinewidth
 0 0 0 edgecolor
-newpath 111.79 72.34 moveto
-102.41 91.18 106.81 113 125 113 curveto
-140.2 113 145.78 97.75 141.72 81.74 curveto
+newpath 302.28 100.82 moveto
+286.39 97.74 263.88 93.64 244 91 curveto
+220.78 87.91 194.4 85.6 174.43 84.1 curveto
 stroke
 0 0 0 edgecolor
-newpath 144.98 80.49 moveto
-138.21 72.34 lineto
-138.43 82.93 lineto
+newpath 174.57 80.6 moveto
+164.34 83.36 lineto
+174.06 87.58 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 174.57 80.6 moveto
+164.34 83.36 lineto
+174.06 87.58 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+214 93.4 moveto 18 ('B') alignedtext
+grestore
+% q2
+gsave
+0 0 1 nodecolor
+223 136 20.8 20.8 ellipse_path fill
+1 setlinewidth
+filled
+0 0 0 nodecolor
+223 136 20.8 20.8 ellipse_path stroke
+0 0 0 nodecolor
+14 /Times-Roman set_font
+215 130.9 moveto 16 (q2) alignedtext
+grestore
+% q2->q0
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 201.85 134.78 moveto
+168.4 132.84 103.14 129.06 64.27 126.81 curveto
+stroke
+0 0 0 edgecolor
+newpath 64.24 123.3 moveto
+54.06 126.22 lineto
+63.84 130.29 lineto
 closepath fill
 1 setlinewidth
 solid
 0 0 0 edgecolor
-newpath 144.98 80.49 moveto
-138.21 72.34 lineto
-138.43 82.93 lineto
+newpath 64.24 123.3 moveto
+54.06 126.22 lineto
+63.84 130.29 lineto
 closepath stroke
+grestore
+% q2->q1
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 243.24 129.73 moveto
+257.47 125.31 276.76 119.33 292.8 114.36 curveto
+stroke
+0 0 0 edgecolor
+newpath 294.28 117.57 moveto
+302.79 111.26 lineto
+292.21 110.88 lineto
+closepath fill
+1 setlinewidth
+solid
 0 0 0 edgecolor
-14 /Times-Roman set_font
-116 115.4 moveto 18 ('B') alignedtext
+newpath 294.28 117.57 moveto
+302.79 111.26 lineto
+292.21 110.88 lineto
+closepath stroke
 grestore
-% q1
+% q3->q2
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 160.75 93.98 moveto
+171.39 101.16 185.11 110.42 196.96 118.42 curveto
+stroke
+0 0 0 edgecolor
+newpath 195.32 121.54 moveto
+205.57 124.23 lineto
+199.24 115.74 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 195.32 121.54 moveto
+205.57 124.23 lineto
+199.24 115.74 lineto
+closepath stroke
+grestore
+% q4
 gsave
 0 0 1 nodecolor
-225 56 20.8 20.8 ellipse_path fill
+223 25 20.8 20.8 ellipse_path fill
 1 setlinewidth
 filled
 0 0 0 nodecolor
-225 56 20.8 20.8 ellipse_path stroke
-1 setlinewidth
-filled
-0 0 0 nodecolor
-225 56 24.8 24.8 ellipse_path stroke
+223 25 20.8 20.8 ellipse_path stroke
 0 0 0 nodecolor
 14 /Times-Roman set_font
-217 50.9 moveto 16 (q1) alignedtext
+215 19.9 moveto 16 (q4) alignedtext
 grestore
-% q0->q1
+% q3->q4
 gsave
 1 setlinewidth
 0 0 0 edgecolor
-newpath 146.21 56 moveto
-158.85 56 175.21 56 189.75 56 curveto
+newpath 160.36 69.63 moveto
+171.16 61.94 185.24 51.91 197.31 43.3 curveto
 stroke
 0 0 0 edgecolor
-newpath 189.94 59.5 moveto
-199.94 56 lineto
-189.94 52.5 lineto
+newpath 199.56 46 moveto
+205.68 37.34 lineto
+195.5 40.3 lineto
 closepath fill
 1 setlinewidth
 solid
 0 0 0 edgecolor
-newpath 189.94 59.5 moveto
-199.94 56 lineto
-189.94 52.5 lineto
+newpath 199.56 46 moveto
+205.68 37.34 lineto
+195.5 40.3 lineto
+closepath stroke
+grestore
+% q5
+gsave
+0 0 1 nodecolor
+323 25 20.8 20.8 ellipse_path fill
+1 setlinewidth
+filled
+0 0 0 nodecolor
+323 25 20.8 20.8 ellipse_path stroke
+1 setlinewidth
+filled
+0 0 0 nodecolor
+323 25 24.8 24.8 ellipse_path stroke
+0 0 0 nodecolor
+14 /Times-Roman set_font
+315 19.9 moveto 16 (q5) alignedtext
+grestore
+% q4->q5
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 244.21 25 moveto
+256.85 25 273.21 25 287.75 25 curveto
+stroke
+0 0 0 edgecolor
+newpath 287.94 28.5 moveto
+297.94 25 lineto
+287.94 21.5 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 287.94 28.5 moveto
+297.94 25 lineto
+287.94 21.5 lineto
 closepath stroke
 0 0 0 edgecolor
 14 /Times-Roman set_font
-164 58.4 moveto 18 ('C') alignedtext
+262 27.4 moveto 18 ('C') alignedtext
 grestore
 % start
 gsave
 0 0 0 nodecolor
-33 56 1.8 1.8 ellipse_path fill
+33 73 1.8 1.8 ellipse_path fill
 1 setlinewidth
 filled
 0 0 0 nodecolor
-33 56 1.8 1.8 ellipse_path stroke
+33 73 1.8 1.8 ellipse_path stroke
 grestore
-% start->q0
+% start->q3
 gsave
 1 setlinewidth
 0 0 0 edgecolor
-newpath 34.92 56 moveto
-42.48 56 70.91 56 93.83 56 curveto
+newpath 34.91 73.16 moveto
+43.95 73.9 83.25 77.11 111.86 79.45 curveto
 stroke
 0 0 0 edgecolor
-newpath 93.88 59.5 moveto
-103.88 56 lineto
-93.88 52.5 lineto
+newpath 111.59 82.94 moveto
+121.84 80.27 lineto
+112.16 75.96 lineto
 closepath fill
 1 setlinewidth
 solid
 0 0 0 edgecolor
-newpath 93.88 59.5 moveto
-103.88 56 lineto
-93.88 52.5 lineto
+newpath 111.59 82.94 moveto
+121.84 80.27 lineto
+112.16 75.96 lineto
 closepath stroke
 grestore
 endpage
Binary file paper.pdf has changed
--- a/paper.tex	Thu Aug 12 04:55:49 2010 +0900
+++ b/paper.tex	Fri Aug 13 22:11:43 2010 +0900
@@ -84,12 +84,18 @@
 ば Java の HotSpot や Python の PyPy など, 仮想マシンを持つ言語処理系の
 最適化技術として利用されている.
 
-実行時コンパイルが可能な対象として, 正規表現評価器に着目し,コンパイラ基
-盤であるLLVM, GCC をバックエンドに用いた実行時コンパイルを行う評価器を
-Pythonによって実装した.
+実行時コンパイルが可能な対象として, 正規表現評価器に着目した.
+現在,正規表現の評価器は, プログラミング言語の組み込み機能やライブラリ等,
+さまざまな実装が存在するが, それらの殆どは仮想マシン方式を採用している\cite{R2}.
+仮想マシンを採用いた実装でも, 正規表現を内部表現に変換する処理を行ってお
+り, それらを ``コンパイル'' と呼ぶことが多い.本研究で実装した評価器の
+``実行時コンパイル''とは, 正規表現を内部形式に変換することではなく, 正規
+表現 から実行バイナリを生成することを指す(\ref{subsection:compile}節). 本研究では, 実行バイナリの生
+成にはコンパイラ基盤であるLLVM, GCC を用いており,評価器全体の実装として
+はPythonで実装した.
 
 本論文では, まず正規表現のコンパイル方法について説明し, 実装した評価器の
-性能調査のために, 正規表現を用いてテキストマッチ検査を行う grep と同等の
+性能調査のために, 正規表現を用いてテキストマッチ処理を行う grep と同等の
 機能を実装し, GNU grep との比較を行う.
 
 \section{正規表現}
@@ -97,51 +103,119 @@
 正規表現は与えられた文字列を受理するかどうかを判定できるパターンマッチン
 グの機構であり, sed, grep, awk を始めとするテキスト処理ツールに広く利用
 されている. 正規表現には定められた文法によって記述され, 例えば,正規表現
-``a*b''は''a''の0回以上の繰り返し ``b'' で終わる文字列(``b'', ``ab'',
-``'aaaab')を受理し, ``a(b|c)'' は ``a''で始まり,直後が ``b'' または
+``a*b''は''a''の0回以上の繰り返し直後, ``b'' で終わる文字列(``b'', ``ab'',
+``'aaaab')を受理し, ``a(b\textbar c)'' は ``a''で始まり,直後が ``b'' または
 ``c''で終わる文字列(``ab'', ``ac'') を受理する.
 
+\subsection{正規表現の演算}\label{subsection:regex}
+
+本論文では, 以下に定義された演算をサポートする表現を正規表現として扱う.
+\begin{enumerate}
+\item {連接} 二つの言語LとMの連接(LM)は, Lに族する列を一つとり, そのあとにMに族する列を連
+接することによってできる列全体から成る集合である.
+\item {集合和} 二つの言語LとM集合和(L\textbar M)は, LまたはM(もしくはその両方)に属する列全体からなる
+集合である.
+\item {閉包} 言語Lの閉包(L*)とは, Lの中から有限個の列を重複を許して取り出し,
+      それらを連接してできる列全体の集合である.
+\end{enumerate}
+
+正規表現は,この3つの演算について閉じておリ,この3つの演算によって定義され
+る表現は, 数学的には正則表現と定義されている.
+本論文では,特に区別のない限り,正則表現と正規表現を同じものとして扱う.
+
 \subsection{grep}
+正規表現は, テキストのパターンをシンプルに記述できるという利点から, テキ
+ストファイルから, 任意のパターンにマッチするテキストを検索するなどの用途
+に使用される.
 
-\section{正規表現の実行時コンパイル}
+GNU grep は, それを実現するソフトウェアの一つであり, 引数として与えられ
+たファイルから, 与えられた正規表現にマッチするテキストを含む行を出力する
+機能を持っている.
+
+``与えられた正規表現にマッチするテキストを含む''というのは, 行の先頭から
+末尾まで正規表現によるマッチングを行い, 正規表現が受理状態になった時点で
+``含む'' という解釈を行う.つまり, 正規表現 ''(a\textbar s)t'' は, ''at''または''
+st``を受理する正規表現であり, テキスト行''math.``の2~3文字目の''at''に一致す
+るので grep は ``math.'' を出力する. また正規表現''a*''は, ``a''の0回以上の繰
+り返しを受理する正規表現であり, 空文字も受理するので, grep は全ての行を
+出力することになる.
+
+\section{正規表現評価器の実装}
+正規表現は等価なNFAに, またNFAは等価なDFAに変換することが可能である\cite{U}. 以
+下にその変換手方を説明する.
+
 \subsection{正規表現からNFAへの変換}
-\subsection{NFAからDFAへの変換}
-は
+NFA は, 入力に対して複数の遷移先持つ状態の集合である.
+
+正規表現が, 等価なNFAに変換できるということを,\ref{subsection:regex}で定義
+した3つの演算について対応するNFAに変換できることから示す.
 
-\begin{figure}[!tb]
+\begin{enumerate}
+\item {連接} 図\ref{figure:concat}は正規表現 ``AB'' に対応するNFAとなる.
+\item {集合和} 図\ref{figure:union}は正規表現 ``A|B''に対応するNFAとなる.
+\item {閉包} 図\ref{figure:star}は正規表現 ``A*''に対応するNFAとなる.
+\end{enumerate}
+
+\begin{figure}[tH]
 \begin{center}
 \scalebox{0.80}{\includegraphics{fig1.eps}}
 \end{center}
+\caption{``A''と``B''の連接}
+\label{figure:concat}
 \end{figure}
 
 \begin{figure}[tb]
 \begin{center}
 \scalebox{0.80}{\includegraphics{fig2.eps}}
 \end{center}
+\caption{``A''と``B''の集合和}
+\label{figure:union}
 \end{figure}
 
 \begin{figure}[tb]
 \begin{center}
 \scalebox{0.80}{\includegraphics{fig3.eps}}
 \end{center}
+\caption{``A''の閉包}
+\label{figure:star}
 \end{figure}
 
-\subsection{DFAからContinuous base Cへの変換}
+図\ref{figure:union}, \ref{figure:star}において, ラベルのない矢印は無条件
+の遷移を現しており,$\varepsilon$-動作と呼ばれる. また, 二重丸で囲まれた
+状態は受理状態を現しておリ, NFAにおいて入力が終了した時点で,受理状態を保
+持している場合に限り, その文字列を受理したことになる.
+
+現在実装されている正規表現評価器の多くは, 正規表現を内部的にNFAに変換し
+て評価を行っている\cite{R1}. NFAによる実装は, 後述する後方参照や最長一致
+に対応しやすいが, 複数の状態を保持する必要があるため
+
+\subsection{NFAからDFAへの変換}
+\subsection{DFAから実行バイナリの生成}\label{subsection:compile}
+DFAからの実行バイナリ生成には, 3種類の実装を行った.
+\begin{enumerate}
+\item ({\bf DFA -> Continuous based C -> gccによるコンパイル})
+\item ({\bf DFA -> C -> gccによるコンパイル })
+\item ({\bf DFA -> LLVM 中間表現 -> LLVMによるコンパイル})
+\end{enumerate}
 %
 
 \section{評価}
-
 ...
 
 \begin{adjustvboxheight} % needed only when Appendix follows
 \begin{thebibliography}{99}
-\bibitem{K} Ken Thompson : Regular Expression Search Algorithm, 1968
+\bibitem{U} Hopcroft, J, E. Motowani, R. D, Ullman. : オートマトン言
+        語理論計算論I (第二版), pp.~39--90.
 
-\bibitem{R1} Russ Cox : Regular Expression Matching Can Be Simple And
+\bibitem{K} Thompson, K : Regular Expression Search Algorithm, 1968
+
+\bibitem{R1} Cox, R : Regular Expression Matching Can Be Simple And
         Fast, 2007
-\bibitem{R2} Russ Cox : Regular Expression Matching: the Virtual Machine
+
+\bibitem{R2} Cox, R : Regular Expression Matching: the Virtual Machine
         Approach, 2009
-\bibitem{R3} Russ Cox : Regular Expression Matching in the Wild, 2010
+
+\bibitem{R3} Cox, R : Regular Expression Matching in the Wild, 2010
 
 \bibitem{H} 長谷川 勇 : 国際正規表現ライブラリの開発