181 to a bound better than Antimirov's cubic bound). |
181 to a bound better than Antimirov's cubic bound). |
182 Rather, we do not try to eliminate in every instance of regular expressions |
182 Rather, we do not try to eliminate in every instance of regular expressions |
183 that have "language duplicates", but only eliminate the "exact duplicates". |
183 that have "language duplicates", but only eliminate the "exact duplicates". |
184 For this we need to break up terms $(a+b)\cdot c$ into two |
184 For this we need to break up terms $(a+b)\cdot c$ into two |
185 terms $a\cdot c$ and $b\cdot c$ before we add them to the accumulator: |
185 terms $a\cdot c$ and $b\cdot c$ before we add them to the accumulator: |
|
186 \begin{figure} |
186 \begin{verbatim} |
187 \begin{verbatim} |
187 def distinctWith(rs: List[ARexp], |
188 def distinctWith(rs: List[ARexp], |
188 pruneFunction: (ARexp, Set[Rexp]) => ARexp, |
189 pruneFunction: (ARexp, Set[Rexp]) => ARexp, |
189 acc: Set[Rexp] = Set()) : List[ARexp] = |
190 acc: Set[Rexp] = Set()) : List[ARexp] = |
190 rs match{ |
191 rs match{ |
213 case ALTS(r1, r2) => turnIntoTerms(r1) ::: turnIntoTerms(r2) |
217 case ALTS(r1, r2) => turnIntoTerms(r1) ::: turnIntoTerms(r2) |
214 case ZERO => Nil |
218 case ZERO => Nil |
215 case _ => r :: Nil |
219 case _ => r :: Nil |
216 } |
220 } |
217 \end{verbatim} |
221 \end{verbatim} |
|
222 \caption{function that breaks up regular expression into "atomic" terms} |
|
223 \end{figure} |
|
224 |
218 \noindent |
225 \noindent |
219 The pruning function can be defined recursively: |
226 The pruning function can be defined recursively: |
|
227 \begin{figure} |
220 \begin{verbatim} |
228 \begin{verbatim} |
221 def prune7(r: ARexp, acc: Set[Rexp]) : ARexp = r match{ |
229 def prune7(r: ARexp, acc: Set[Rexp]) : ARexp = r match{ |
222 case AALTS(bs, rs) => rs.map(r => prune7(r, acc)).filter(_ != ZERO) match |
230 case AALTS(bs, rs) => rs.map(r => prune7(r, acc)).filter(_ != ZERO) match |
223 { |
231 { |
224 case Nil => AZERO |
232 case Nil => AZERO |
231 case r1p => ASEQ(bs, r1p, r2) |
239 case r1p => ASEQ(bs, r1p, r2) |
232 } |
240 } |
233 case r => if(acc(erase(r))) AZERO else r |
241 case r => if(acc(erase(r))) AZERO else r |
234 } |
242 } |
235 \end{verbatim} |
243 \end{verbatim} |
|
244 \caption{pruning function} |
|
245 \end{figure} |
|
246 |
|
247 |
|
248 \pgfplotsset{ |
|
249 myplotstyle/.style={ |
|
250 legend style={draw=none, font=\small}, |
|
251 legend cell align=left, |
|
252 legend pos=north east, |
|
253 ylabel style={align=center, font=\bfseries\boldmath}, |
|
254 xlabel style={align=center, font=\bfseries\boldmath}, |
|
255 x tick label style={font=\bfseries\boldmath}, |
|
256 y tick label style={font=\bfseries\boldmath}, |
|
257 scaled ticks=true, |
|
258 every axis plot/.append style={thick}, |
|
259 }, |
|
260 } |
236 |
261 |
237 \begin{figure} |
262 \begin{figure} |
238 \centering |
263 \centering |
239 \begin{tabular}{@{}c@{\hspace{0mm}}c@{\hspace{0mm}}c@{}} |
264 \begin{tabular}{@{}c@{\hspace{0mm}}c@{\hspace{0mm}}c@{}} |
240 \begin{tikzpicture} |
265 \begin{tikzpicture} |
241 \begin{axis}[ |
266 \begin{axis}[ |
242 xlabel={$n$}, |
267 %xlabel={$n$}, |
243 x label style={at={(1.05,-0.05)}}, |
268 myplotstyle, |
|
269 xlabel={input length}, |
244 ylabel={size}, |
270 ylabel={size}, |
245 enlargelimits=false, |
271 ] |
246 xtick={0,5,...,30}, |
|
247 xmax=30, |
|
248 ymax=800, |
|
249 ytick={0,200,...,800}, |
|
250 scaled ticks=false, |
|
251 axis lines=left, |
|
252 width=5cm, |
|
253 height=4cm, |
|
254 legend entries={$bsimpStrong$ size growth}, |
|
255 legend pos=north west, |
|
256 legend cell align=left] |
|
257 \addplot[red,mark=*, mark options={fill=white}] table {strongSimpCurve.data}; |
272 \addplot[red,mark=*, mark options={fill=white}] table {strongSimpCurve.data}; |
258 \end{axis} |
273 \end{axis} |
259 \end{tikzpicture} |
274 \end{tikzpicture} |
260 & |
275 & |
261 \begin{tikzpicture} |
276 \begin{tikzpicture} |
262 \begin{axis}[ |
277 \begin{axis}[ |
263 xlabel={$n$}, |
278 %xlabel={$n$}, |
264 x label style={at={(1.05,-0.05)}}, |
279 myplotstyle, |
|
280 xlabel={input length}, |
265 ylabel={size}, |
281 ylabel={size}, |
266 enlargelimits=false, |
282 ] |
267 xtick={0,5,...,30}, |
|
268 xmax=30, |
|
269 ymax=42000, |
|
270 ytick={0,10000,...,40000}, |
|
271 scaled ticks=true, |
|
272 axis lines=left, |
|
273 width=5cm, |
|
274 height=4cm, |
|
275 legend entries={$bsimp$ size growth}, |
|
276 legend pos=north west, |
|
277 legend cell align=left] |
|
278 \addplot[blue,mark=*, mark options={fill=white}] table {bsimpExponential.data}; |
283 \addplot[blue,mark=*, mark options={fill=white}] table {bsimpExponential.data}; |
279 \end{axis} |
284 \end{axis} |
280 \end{tikzpicture}\\ |
285 \end{tikzpicture}\\ |
281 \multicolumn{2}{c}{Graphs: Runtime for matching $((a^* + (aa)^* + \ldots + (aaaaa)^* )^*)^*$ with strings |
286 \multicolumn{2}{l}{Graphs: Runtime for matching $((a^* + (aa)^* + \ldots + (aaaaa)^* )^*)^*$ with strings |
282 of the form $\underbrace{aa..a}_{n}$.} |
287 of the form $\underbrace{aa..a}_{n}$.} |
283 \end{tabular} |
288 \end{tabular} |
284 \caption{aaaaaStarStar} \label{fig:aaaaaStarStar} |
289 \caption{aaaaaStarStar} \label{fig:aaaaaStarStar} |
285 \end{figure} |
290 \end{figure} |
286 |
291 |