equal
deleted
inserted
replaced
84 |
84 |
85 |
85 |
86 \begin{document} |
86 \begin{document} |
87 |
87 |
88 |
88 |
89 \section*{Proposal:\\ |
89 \section*{Proposal: \\ |
90 Fast Regular Expression Matching\\ |
90 Fast Regular Expression Matching\\ |
91 with Brzozowski Derivatives} |
91 with Brzozowski Derivatives} |
92 |
92 |
93 \subsubsection*{Summary} |
93 \subsubsection*{Summary} |
94 |
94 |
256 \noindent |
256 \noindent |
257 These graphs show how long strings can be when using the rather simple |
257 These graphs show how long strings can be when using the rather simple |
258 regular expression $(a^*)^* \,b$ and the built-in regular expression |
258 regular expression $(a^*)^* \,b$ and the built-in regular expression |
259 matchers in the popular programming languages Python and Java (Version |
259 matchers in the popular programming languages Python and Java (Version |
260 8 and Version 9). There are many more regular expressions that show |
260 8 and Version 9). There are many more regular expressions that show |
261 the same bahaviour. On the left-hand side the graphs show that for a |
261 the same behaviour. On the left-hand side the graphs show that for a |
262 string consisting of just 28 $a\,$'s, Python and the older Java (which |
262 string consisting of just 28 $a\,$'s, Python and the older Java (which |
263 was the latest version of Java until September 2017) already need 30 |
263 was the latest version of Java until September 2017) already need 30 |
264 seconds to decide whether this string is matched or not. This is an |
264 seconds to decide whether this string is matched or not. This is an |
265 abysmal result given that Python and Java are very popular programming |
265 abysmal result given that Python and Java are very popular programming |
266 languages. We already know that this problem can be decided much, much |
266 languages. We already know that this problem can be decided much, much |