42 & & $\quad \phantom{\mid}\; \None \implies \None$\\ |
42 & & $\quad \phantom{\mid}\; \None \implies \None$\\ |
43 & & $\quad \mid \Some(v) \implies \Some(\inj \; r\; c\; v)$ |
43 & & $\quad \mid \Some(v) \implies \Some(\inj \; r\; c\; v)$ |
44 \end{tabular} |
44 \end{tabular} |
45 \end{center} |
45 \end{center} |
46 \noindent |
46 \noindent |
47 The first problem with this algorithm is that |
47 This algorithm works nicely as a functional program that utilizes Brzozowski derivatives: |
48 for the function $\inj$ to work properly |
48 each derivative character is remembered and stacked up, and |
49 we cannot destroy the structure of a regular expression, |
49 injected back in reverse order as they have been taken derivative of. |
50 and therefore cannot simplify too aggressively. |
50 The derivative operation $\backslash$ and its reverse operation |
51 For example, |
51 $\inj$ is of similar shape and compexity, and work in lockstep with each other. |
52 \[ |
52 However if we take a closer look into the example run |
53 r + (r + a) \rightarrow r + a |
53 of $\lexer$ we have shown in chapter \ref{Inj}, |
54 \] |
54 many inefficiencies exist: |
55 cannot be applied because that would require |
55 \begin{center} |
56 breaking up the inner alternative. |
56 \begin{tabular}{lcl} |
57 The $\lexer$ plus $\textit{simp}$ therefore only enables |
57 $(a+\textcolor{magenta}{a}\textcolor{blue}{a})^* \cdot \textcolor{red}{c}$ & $\stackrel{\backslash \textcolor{magenta}{a}}{\rightarrow}$ & $((\ONE + \textcolor{magenta}{\ONE} \textcolor{blue}{a})\cdot (a+aa)^*)\cdot \textcolor{red}{c}+\ZERO$\\ |
58 same-level de-duplications like |
58 %& $\stackrel{\rightarrow}{\backslash a}$ & $((\ONE + \ONE a)\cdot (a+aa)^*)\cdot c + \ZERO$\\ |
59 \[ |
59 & $\stackrel{\backslash \textcolor{blue}{a}}{\rightarrow}$ & |
60 r + r \rightarrow r. |
60 $(((\ZERO+(\ZERO a+ \textcolor{blue}{\ONE}))\cdot (a+aa)^* + (\ONE+\ONE a)\cdot (a+aa)^* )\cdot \textcolor{red}{\mathbf{c}} + \ZERO)+\ZERO$\\ |
61 \] |
61 & $\stackrel{\backslash \textcolor{red}{c}}{\rightarrow}$ & |
62 Secondly, the algorithm recursively calls $\lexer$ on |
62 $((r_{=0}\cdot c + \textcolor{red}{\ONE})+\ZERO)+\ZERO$\\ |
63 each new character input, |
63 & $\stackrel{\mkeps}{\rightarrow}$ & $\Left (\Left \; (\Right \; \textcolor{red}{\Empty}))$ \\ |
64 and before starting a child call |
64 & $\stackrel{\inj \;\textcolor{red}{c} }{\rightarrow}$ & |
65 it stores information of previous lexing steps |
65 $\Left \; (\Left \; (\Seq \;(\Left \; (\Seq \; (\Right \; (\Right\; \textcolor{blue}{\Empty})) \; \Stars \, [])) \; \textcolor{red}{c}))$\\ |
66 on a stack, in the form of regular expressions |
66 & $\stackrel{\inj \;\textcolor{blue}{a}}{\rightarrow}$ & |
67 and characters: $r_0$, $c_0$, $r_1$, $c_1$, etc. |
67 $\Left\; (\Seq \; (\Seq\; (\Right \; (\Seq \; \textcolor{magenta}{\Empty }\; \textcolor{blue}{ \mathbf{a}}) ) |
68 Each descent into deeper recursive calls in $\lexer$ |
68 \;\Stars \,[]) \; \textcolor{red}{c})$\\ |
69 causes a new pair of $r_i, c_i$ to be pushed to the call stack. |
69 & $\stackrel{\inj \;\textcolor{magenta}{a}}{\rightarrow}$ & $\Seq \; (\Stars \; [\Right \; (\Seq \; \mathbf{\textcolor{magenta}{a}} \; \textcolor{blue}{a})]) \; \textcolor{red}{ c}$ |
70 \begin{figure}[H] |
70 |
71 \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick] |
71 %$\inj \; r \; c\A$ |
72 %\draw (-6,-6) grid (6,6); |
72 %$\inj \; (a\cdot b)\cdot c \; \Seq \; \ONE \; b$ & $=$ & $(a+e)$\\ |
73 \node [ circle ] (r) at (-6, 5) {$r$}; |
73 \end{tabular} |
74 |
74 \end{center} |
75 %\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$}; |
75 \noindent |
76 \node [circle, minimum size = 0.1, draw] (c1) at (-4, 5.4) {$c_1$}; |
76 For the un |
77 % |
77 |
78 %\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$}; |
78 \begin{center} |
79 \node [minimum size = 0.5, circle, draw] (r1) at (-2, 5) {$r_1$}; |
79 \begin{tabular}{lcl} |
80 |
80 $\inj$ & $\quad ((\ONE + {\ONE} |
81 \node [minimum width = 2cm, rectangle, draw] (stack) at (0, 3) {Stack}; |
81 \textcolor{blue}{a})\cdot (a+aa)^*)\cdot |
82 |
82 + \ZERO \; \quad \textcolor{blue}{a} \; $ & \\ |
83 \path |
83 $\quad \Left \; |
84 (r) |
84 (\Left \; (\Seq \;(\Left \; (\Seq \; (\Right \; (\Right\; |
85 edge [->, >=stealth',shorten >=1pt] node[left] {} (r1); |
85 \textcolor{blue}{\Empty})) \; \Stars \, [])) \; c))$ & \\$=$\\ |
86 |
86 $\Left \; (\inj \; ((\ONE + \ONE |
87 \path (r1) |
87 \textcolor{blue}{a})\cdot (a+aa)^*)\cdot |
88 edge [bend right, dashed] node {saved} (stack); |
88 c \quad \textcolor{blue}{a} \quad (\Left \; (\Seq\; ( \Left \; (\Seq \; (\Right \; (\Right\; |
89 \path (c1) |
89 \textcolor{blue}{\Empty})) \; \Stars \, []) ) \; c ) )\;\;)$ &\\ $=$\\ |
90 edge [bend right, dashed] node {} (stack); |
90 $\Left \; (\Seq \; (\inj \; (\ONE + \ONE \textcolor{blue}{a})\cdot(a+aa)^* \quad \textcolor{blue}{a} \quad |
91 |
91 (\Left \; (\Seq \; (\Right \; (\Right\;\textcolor{blue}{\Empty})))) ) \; c ) $ & \\$=$\\ |
92 |
92 $\Left \; (\Seq \; (\Seq \; (\inj \quad (\ONE + \ONE \textcolor{blue}{a}) \quad \textcolor{blue}{a}\quad \Right \;(\Right \; \textcolor{blue}{\Empty}) ) \; \Stars \,[])\; c)$ &\\ $=$ \\ |
93 \end{tikzpicture} |
93 $\Left \; (\Seq \; (\Seq \; (\Right \; (\inj \; \ONE \textcolor{blue}{a} \quad \textcolor{blue}{a}\quad (\Right \;\textcolor{blue}{\Empty})))) \; \Stars \, [])$ |
94 \caption{First derivative taken} |
94 & \\ $=$\\ |
95 \end{figure} |
95 $\Left \; (\Seq \; (\Seq \; (\Right \; (\Seq \; (\mkeps \; \ONE)\;(\inj \;\textcolor{blue}{a} \; \textcolor{blue}{a} \; \textcolor{blue}{\Empty})) ) ) \; \Stars \, [] )$ |
96 |
96 & \\ $=$\\ |
97 |
97 $\Left \; (\Seq \; (\Seq \; (\Right \; (\Seq \; \Empty \; \textcolor{blue}{a}) ) ) \; \Stars \, [] )$ |
98 |
98 \end{tabular} |
99 \begin{figure}[H] |
99 \end{center} |
100 \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick] |
100 |
101 %\draw (-6,-6) grid (6,6); |
101 |
102 \node [ circle ] (r) at (-6, 5) {$r$}; |
102 |
103 |
103 |
104 %\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$}; |
104 |
105 \node [circle, minimum size = 0.1, ] (c1) at (-4, 5.4) {$c_1$}; |
105 |
106 % |
106 |
107 %\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$}; |
107 |
108 \node [minimum size = 0.5, circle, ] (r1) at (-2, 5) {$r_1$}; |
108 % The first problem with this algorithm is that |
109 |
109 % for the function $\inj$ to work properly |
110 |
110 % we cannot destroy the structure of a regular expression, |
111 \node [circle, minimum size = 0.1, draw] (c2) at (0, 5.4) {$c_2$}; |
111 % and therefore cannot simplify along the way without mechanisms |
112 % |
112 % that restores the values during the simplification process. |
113 %\node (2, 5) (r2) circle [radius = 0.5] {$r_2$}; |
113 % %too aggressively. |
114 \node [circle, draw] (r2) at (2, 5) {$r_2$}; |
114 % For example, |
115 \node [minimum width = 3cm, minimum height = 1cm, rectangle, draw] (stack) at (0, 2) {\large Stack}; |
115 % \[ |
116 |
116 % r + (r + a) \rightarrow r + a |
117 \path |
117 % \] |
118 (r) |
118 % cannot be applied because that would require |
119 edge [->, >=stealth',shorten >=1pt] node[left] {} (r1); |
119 % breaking up the inner alternative. |
120 |
120 % The $\lexer$ plus $\textit{simp}$ therefore only enables |
121 \path (r2) |
121 % same-level de-duplications like |
122 edge [bend right, dashed] node {} (stack); |
122 % \[ |
123 \path (c2) |
123 % r + r \rightarrow r. |
124 edge [bend right, dashed] node {} (stack); |
124 % \] |
125 |
125 % Secondly, the algorithm recursively calls $\lexer$ on |
126 \path (r1) |
126 % each new character input, |
127 edge [] node {} (r2); |
127 % and before starting a child call |
128 |
128 % it stores information of previous lexing steps |
129 \end{tikzpicture} |
129 % on a stack, in the form of regular expressions |
130 \caption{Second derivative taken} |
130 % and characters: $r_0$, $c_0$, $r_1$, $c_1$, etc. |
131 \end{figure} |
131 % Each descent into deeper recursive calls in $\lexer$ |
132 \noindent |
132 % causes a new pair of $r_i, c_i$ to be pushed to the call stack. |
133 As the number of derivative steps increases, |
133 % \begin{figure}[H] |
134 the stack would increase: |
134 % \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick] |
135 |
135 % %\draw (-6,-6) grid (6,6); |
136 \begin{figure}[H] |
136 % \node [ circle ] (r) at (-6, 5) {$r$}; |
137 \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick] |
137 |
138 %\draw (-6,-6) grid (6,6); |
138 % %\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$}; |
139 \node [ circle ] (r) at (-6, 5) {$r$}; |
139 % \node [circle, minimum size = 0.1, draw] (c1) at (-4, 5.4) {$c_1$}; |
140 |
140 % % |
141 %\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$}; |
141 % %\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$}; |
142 \node [circle, minimum size = 0.1, ] (c1) at (-4, 5.4) {$c_1$}; |
142 % \node [minimum size = 0.5, circle, draw] (r1) at (-2, 5) {$r_1$}; |
143 % |
143 |
144 %\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$}; |
144 % \node [minimum width = 2cm, rectangle, draw] (stack) at (0, 3) {Stack}; |
145 \node [minimum size = 0.5, circle, ] (r1) at (-2, 5) {$r_1$}; |
145 |
146 |
146 % \path |
147 |
147 % (r) |
148 \node [circle, minimum size = 0.1, ] (c2) at (0, 5.4) {$c_2$}; |
148 % edge [->, >=stealth',shorten >=1pt] node[left] {} (r1); |
149 % |
149 |
150 %\node (2, 5) (r2) circle [radius = 0.5] {$r_2$}; |
150 % \path (r1) |
151 \node [circle, ] (r2) at (2, 5) {$r_2$}; |
151 % edge [bend right, dashed] node {saved} (stack); |
152 \node [minimum width = 4cm, minimum height = 2.5cm, rectangle, draw] (stack) at (0, 1) { \large Stack}; |
152 % \path (c1) |
153 |
153 % edge [bend right, dashed] node {} (stack); |
154 \node [] (ldots) at (3.5, 5) {}; |
154 |
155 %\node (6, 5) (rn) circle [radius = 0.5] {$r_n$}; |
155 |
156 |
156 % \end{tikzpicture} |
157 \node [minimum size = 0.5, circle, ] (rn) at (6, 5) {}; |
157 % \caption{First derivative taken} |
158 |
158 % \end{figure} |
159 \node (rldots) at ($(ldots)!.4!(rn)$) {\ldots}; |
159 |
160 |
160 |
161 \path |
161 |
162 (r) |
162 % \begin{figure}[H] |
163 edge [->, >=stealth',shorten >=1pt] node[left] {} (r1); |
163 % \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick] |
164 |
164 % %\draw (-6,-6) grid (6,6); |
165 \path (rldots) |
165 % \node [ circle ] (r) at (-6, 5) {$r$}; |
166 edge [bend left, dashed] node {} (stack); |
166 |
167 |
167 % %\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$}; |
168 \path (r1) |
168 % \node [circle, minimum size = 0.1, ] (c1) at (-4, 5.4) {$c_1$}; |
169 edge [] node {} (r2); |
169 % % |
170 |
170 % %\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$}; |
171 \path (r2) |
171 % \node [minimum size = 0.5, circle, ] (r1) at (-2, 5) {$r_1$}; |
172 edge [] node {} (ldots); |
172 |
173 \path (ldots) |
173 |
174 edge [bend left, dashed] node {} (stack); |
174 % \node [circle, minimum size = 0.1, draw] (c2) at (0, 5.4) {$c_2$}; |
175 \path (5.03, 4.9) |
175 % % |
176 edge [bend left, dashed] node {} (stack); |
176 % %\node (2, 5) (r2) circle [radius = 0.5] {$r_2$}; |
177 \end{tikzpicture} |
177 % \node [circle, draw] (r2) at (2, 5) {$r_2$}; |
178 \caption{More derivatives taken} |
178 % \node [minimum width = 3cm, minimum height = 1cm, rectangle, draw] (stack) at (0, 2) {\large Stack}; |
179 \end{figure} |
179 |
180 |
180 % \path |
181 |
181 % (r) |
182 \begin{figure}[H] |
182 % edge [->, >=stealth',shorten >=1pt] node[left] {} (r1); |
183 \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick] |
183 |
184 %\draw (-6,-6) grid (6,6); |
184 % \path (r2) |
185 \node [radius = 0.5, circle, draw] (r) at (-6, 5) {$r$}; |
185 % edge [bend right, dashed] node {} (stack); |
186 |
186 % \path (c2) |
187 %\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$}; |
187 % edge [bend right, dashed] node {} (stack); |
188 \node [circle, minimum size = 0.1, draw] (c1) at (-4, 5.4) {$c_1$}; |
188 |
189 % |
189 % \path (r1) |
190 %\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$}; |
190 % edge [] node {} (r2); |
191 \node [minimum size = 0.5, circle, draw] (r1) at (-2, 5) {$r_1$}; |
191 |
192 % |
192 % \end{tikzpicture} |
193 %\node (0, 6) (c2) circle [radius = 0.3] {$c_2$}; |
193 % \caption{Second derivative taken} |
194 \node [circle, minimum size = 0.1, draw] (c2) at (0, 5.4) {$c_2$}; |
194 % \end{figure} |
195 % |
195 % \noindent |
196 %\node (2, 5) (r2) circle [radius = 0.5] {$r_2$}; |
196 % As the number of derivative steps increases, |
197 \node [circle, draw] (r2) at (2, 5) {$r_2$}; |
197 % the stack would increase: |
198 % |
198 |
199 % |
199 % \begin{figure}[H] |
200 \node [] (ldots) at (4.5, 5) {}; |
200 % \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick] |
201 %\node (6, 5) (rn) circle [radius = 0.5] {$r_n$}; |
201 % %\draw (-6,-6) grid (6,6); |
202 |
202 % \node [ circle ] (r) at (-6, 5) {$r$}; |
203 \node [minimum size = 0.5, circle, draw] (rn) at (6, 5) {$r_n$}; |
203 |
204 |
204 % %\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$}; |
205 \node at ($(ldots)!.4!(rn)$) {\ldots}; |
205 % \node [circle, minimum size = 0.1, ] (c1) at (-4, 5.4) {$c_1$}; |
206 |
206 % % |
207 |
207 % %\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$}; |
208 |
208 % \node [minimum size = 0.5, circle, ] (r1) at (-2, 5) {$r_1$}; |
209 |
209 |
210 \node [minimum size = 6cm, rectangle, draw] (stack) at (0, 0) {\Huge Stack}; |
210 |
211 |
211 % \node [circle, minimum size = 0.1, ] (c2) at (0, 5.4) {$c_2$}; |
212 \path |
212 % % |
213 (r) |
213 % %\node (2, 5) (r2) circle [radius = 0.5] {$r_2$}; |
214 edge [->, >=stealth',shorten >=1pt] node[left] {} (r1); |
214 % \node [circle, ] (r2) at (2, 5) {$r_2$}; |
215 \path |
215 % \node [minimum width = 4cm, minimum height = 2.5cm, rectangle, draw] (stack) at (0, 1) { \large Stack}; |
216 (r1) |
216 |
217 edge [] node {} (r2); |
217 % \node [] (ldots) at (3.5, 5) {}; |
218 \path (r2) |
218 % %\node (6, 5) (rn) circle [radius = 0.5] {$r_n$}; |
219 edge [] node {} (ldots); |
219 |
220 \path (r) |
220 % \node [minimum size = 0.5, circle, ] (rn) at (6, 5) {}; |
221 edge [dashed, bend right] node {} (stack); |
221 |
222 |
222 % \node (rldots) at ($(ldots)!.4!(rn)$) {\ldots}; |
223 \path (r1) |
223 |
224 edge [dashed, ] node {} (stack); |
224 % \path |
225 |
225 % (r) |
226 \path (c1) |
226 % edge [->, >=stealth',shorten >=1pt] node[left] {} (r1); |
227 edge [dashed, bend right] node {} (stack); |
227 |
228 |
228 % \path (rldots) |
229 \path (c2) |
229 % edge [bend left, dashed] node {} (stack); |
230 edge [dashed] node {} (stack); |
230 |
231 \path (4.5, 5) |
231 % \path (r1) |
232 edge [dashed, bend left] node {} (stack); |
232 % edge [] node {} (r2); |
233 \path (4.9, 5) |
233 |
234 edge [dashed, bend left] node {} (stack); |
234 % \path (r2) |
235 \path (5.3, 5) |
235 % edge [] node {} (ldots); |
236 edge [dashed, bend left] node {} (stack); |
236 % \path (ldots) |
237 \path (r2) |
237 % edge [bend left, dashed] node {} (stack); |
238 edge [dashed, ] node {} (stack); |
238 % \path (5.03, 4.9) |
239 \path (rn) |
239 % edge [bend left, dashed] node {} (stack); |
240 edge [dashed, bend left] node {} (stack); |
240 % \end{tikzpicture} |
241 \end{tikzpicture} |
241 % \caption{More derivatives taken} |
242 \caption{Before injection phase starts} |
242 % \end{figure} |
243 \end{figure} |
243 |
244 |
244 |
245 |
245 % \begin{figure}[H] |
246 \noindent |
246 % \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick] |
|
247 % %\draw (-6,-6) grid (6,6); |
|
248 % \node [radius = 0.5, circle, draw] (r) at (-6, 5) {$r$}; |
|
249 |
|
250 % %\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$}; |
|
251 % \node [circle, minimum size = 0.1, draw] (c1) at (-4, 5.4) {$c_1$}; |
|
252 % % |
|
253 % %\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$}; |
|
254 % \node [minimum size = 0.5, circle, draw] (r1) at (-2, 5) {$r_1$}; |
|
255 % % |
|
256 % %\node (0, 6) (c2) circle [radius = 0.3] {$c_2$}; |
|
257 % \node [circle, minimum size = 0.1, draw] (c2) at (0, 5.4) {$c_2$}; |
|
258 % % |
|
259 % %\node (2, 5) (r2) circle [radius = 0.5] {$r_2$}; |
|
260 % \node [circle, draw] (r2) at (2, 5) {$r_2$}; |
|
261 % % |
|
262 % % |
|
263 % \node [] (ldots) at (4.5, 5) {}; |
|
264 % %\node (6, 5) (rn) circle [radius = 0.5] {$r_n$}; |
|
265 |
|
266 % \node [minimum size = 0.5, circle, draw] (rn) at (6, 5) {$r_n$}; |
|
267 |
|
268 % \node at ($(ldots)!.4!(rn)$) {\ldots}; |
|
269 |
|
270 |
|
271 |
|
272 |
|
273 % \node [minimum size = 6cm, rectangle, draw] (stack) at (0, 0) {\Huge Stack}; |
|
274 |
|
275 % \path |
|
276 % (r) |
|
277 % edge [->, >=stealth',shorten >=1pt] node[left] {} (r1); |
|
278 % \path |
|
279 % (r1) |
|
280 % edge [] node {} (r2); |
|
281 % \path (r2) |
|
282 % edge [] node {} (ldots); |
|
283 % \path (r) |
|
284 % edge [dashed, bend right] node {} (stack); |
|
285 |
|
286 % \path (r1) |
|
287 % edge [dashed, ] node {} (stack); |
|
288 |
|
289 % \path (c1) |
|
290 % edge [dashed, bend right] node {} (stack); |
|
291 |
|
292 % \path (c2) |
|
293 % edge [dashed] node {} (stack); |
|
294 % \path (4.5, 5) |
|
295 % edge [dashed, bend left] node {} (stack); |
|
296 % \path (4.9, 5) |
|
297 % edge [dashed, bend left] node {} (stack); |
|
298 % \path (5.3, 5) |
|
299 % edge [dashed, bend left] node {} (stack); |
|
300 % \path (r2) |
|
301 % edge [dashed, ] node {} (stack); |
|
302 % \path (rn) |
|
303 % edge [dashed, bend left] node {} (stack); |
|
304 % \end{tikzpicture} |
|
305 % \caption{Before injection phase starts} |
|
306 % \end{figure} |
|
307 |
|
308 |
|
309 % \noindent |
247 After all derivatives have been taken, the stack grows to a maximum size |
310 After all derivatives have been taken, the stack grows to a maximum size |
248 and the pair of regular expressions and characters $r_i, c_{i+1}$ |
311 and the pair of regular expressions and characters $r_i, c_{i+1}$ |
249 are then popped out and used in the injection phase. |
312 are then popped out and used in the injection phase. |
250 |
313 |
251 |
314 |
252 |
315 |
253 \begin{figure}[H] |
316 % \begin{figure}[H] |
254 \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick] |
317 % \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick] |
255 %\draw (-6,-6) grid (6,6); |
318 % %\draw (-6,-6) grid (6,6); |
256 \node [radius = 0.5, circle, ] (r) at (-6, 5) {$r$}; |
319 % \node [radius = 0.5, circle, ] (r) at (-6, 5) {$r$}; |
257 |
320 |
258 %\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$}; |
321 % %\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$}; |
259 \node [circle, minimum size = 0.1, ] (c1) at (-4, 5.4) {$c_1$}; |
322 % \node [circle, minimum size = 0.1, ] (c1) at (-4, 5.4) {$c_1$}; |
260 % |
323 % % |
261 %\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$}; |
324 % %\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$}; |
262 \node [minimum size = 0.5, circle, ] (r1) at (-2, 5) {$r_1$}; |
325 % \node [minimum size = 0.5, circle, ] (r1) at (-2, 5) {$r_1$}; |
263 % |
326 % % |
264 %\node (0, 6) (c2) circle [radius = 0.3] {$c_2$}; |
327 % %\node (0, 6) (c2) circle [radius = 0.3] {$c_2$}; |
265 \node [circle, minimum size = 0.1, ] (c2) at (0, 5.4) {$c_2$}; |
328 % \node [circle, minimum size = 0.1, ] (c2) at (0, 5.4) {$c_2$}; |
266 % |
329 % % |
267 %\node (2, 5) (r2) circle [radius = 0.5] {$r_2$}; |
330 % %\node (2, 5) (r2) circle [radius = 0.5] {$r_2$}; |
268 \node [circle, ] (r2) at (2, 5) {$r_2$}; |
331 % \node [circle, ] (r2) at (2, 5) {$r_2$}; |
269 % |
332 % % |
270 % |
333 % % |
271 \node [] (ldots) at (4.5, 5) {}; |
334 % \node [] (ldots) at (4.5, 5) {}; |
272 %\node (6, 5) (rn) circle [radius = 0.5] {$r_n$}; |
335 % %\node (6, 5) (rn) circle [radius = 0.5] {$r_n$}; |
273 |
336 |
274 \node [minimum size = 0.5, circle, ] (rn) at (6, 5) {$r_n$}; |
337 % \node [minimum size = 0.5, circle, ] (rn) at (6, 5) {$r_n$}; |
275 |
338 |
276 \node at ($(ldots)!.4!(rn)$) {\ldots}; |
339 % \node at ($(ldots)!.4!(rn)$) {\ldots}; |
277 |
340 |
278 \node [minimum size = 0.5, circle, ] (vn) at (6, -5) {$v_n$}; |
341 % \node [minimum size = 0.5, circle, ] (vn) at (6, -5) {$v_n$}; |
279 |
342 |
280 \node [] (ldots2) at (3.5, -5) {}; |
343 % \node [] (ldots2) at (3.5, -5) {}; |
281 |
344 |
282 \node [minimum size = 0.5, circle, ] (v2) at (2, -5) {$v_2$}; |
345 % \node [minimum size = 0.5, circle, ] (v2) at (2, -5) {$v_2$}; |
283 |
346 |
284 \node at ($(ldots2)!.4!(v2)$) {\ldots}; |
347 % \node at ($(ldots2)!.4!(v2)$) {\ldots}; |
285 |
348 |
286 |
349 |
287 \node [circle, ] (v1) at (-2, -5) {$v_1$}; |
350 % \node [circle, ] (v1) at (-2, -5) {$v_1$}; |
288 |
351 |
289 \node [radius = 0.5, circle, ] (v) at (-6, -5) {$v$}; |
352 % \node [radius = 0.5, circle, ] (v) at (-6, -5) {$v$}; |
290 |
353 |
291 \node [minimum size = 6cm, rectangle, draw] (stack) at (0, 0) {\Huge Stack}; |
354 % \node [minimum size = 6cm, rectangle, draw] (stack) at (0, 0) {\Huge Stack}; |
292 |
355 |
293 \path |
356 % \path |
294 (r) |
357 % (r) |
295 edge [->, >=stealth',shorten >=1pt] node[left] {} (r1); |
358 % edge [->, >=stealth',shorten >=1pt] node[left] {} (r1); |
296 \path |
359 % \path |
297 (r1) |
360 % (r1) |
298 edge [] node {} (r2); |
361 % edge [] node {} (r2); |
299 \path (r2) |
362 % \path (r2) |
300 edge [] node {} (ldots); |
363 % edge [] node {} (ldots); |
301 \path (rn) |
364 % \path (rn) |
302 edge [] node {$\mkeps$} (vn); |
365 % edge [] node {$\mkeps$} (vn); |
303 \path (vn) |
366 % \path (vn) |
304 edge [] node {} (ldots2); |
367 % edge [] node {} (ldots2); |
305 \path (v2) |
368 % \path (v2) |
306 edge [] node {$\inj \; r_1 \; c_2\;v_2$} (v1); |
369 % edge [] node {$\inj \; r_1 \; c_2\;v_2$} (v1); |
307 |
370 |
308 \path (v1) |
371 % \path (v1) |
309 edge [] node {$\inj \; r \; c_1 \; v_1$} (v); |
372 % edge [] node {$\inj \; r \; c_1 \; v_1$} (v); |
310 |
373 |
311 \path (stack) |
374 % \path (stack) |
312 edge [dashed] node {} (-4.2, -5.2); |
375 % edge [dashed] node {} (-4.2, -5.2); |
313 \path (stack) |
376 % \path (stack) |
314 edge [dashed] node {} (-4, -5.2); |
377 % edge [dashed] node {} (-4, -5.2); |
315 \path (stack) |
378 % \path (stack) |
316 edge [dashed] node {} (-0.1, -5.2); |
379 % edge [dashed] node {} (-0.1, -5.2); |
317 \path (stack) |
380 % \path (stack) |
318 edge [dashed] node {} (0.2, -5.26); |
381 % edge [dashed] node {} (0.2, -5.26); |
319 \path (stack) |
382 % \path (stack) |
320 edge [dashed] node {} (3.2, -5); |
383 % edge [dashed] node {} (3.2, -5); |
321 \path (stack) |
384 % \path (stack) |
322 edge [dashed] node {} (2.7, -5); |
385 % edge [dashed] node {} (2.7, -5); |
323 \path (stack) |
386 % \path (stack) |
324 edge [dashed] node {} (3.7, -5); |
387 % edge [dashed] node {} (3.7, -5); |
325 \end{tikzpicture} |
388 % \end{tikzpicture} |
326 \caption{Stored $r_i, c_{i+1}$ Used by $\inj$} |
389 % \caption{Stored $r_i, c_{i+1}$ Used by $\inj$} |
327 \end{figure} |
390 % \end{figure} |
328 \noindent |
391 % \noindent |
329 Storing all $r_i, c_{i+1}$ pairs recursively |
392 Storing all $r_i, c_{i+1}$ pairs recursively |
330 allows the algorithm to work in an elegant way, at the expense of |
393 allows the algorithm to work in an elegant way, at the expense of |
331 storing quite a bit of verbose information on the stack. |
394 storing quite a bit of verbose information on the stack. |
332 The stack seems to grow at least quadratically with respect |
395 The stack seems to grow at least quadratically with respect |
333 to the input (not taking into account the size bloat of $r_i$), |
396 to the input (not taking into account the size bloat of $r_i$), |