Which Regular Expression Patterns Are Hard to Match?
Regular expressions constitute a fundamental notion in formal language theory and are frequently used in computer science to define search patterns. In particular, regular expression matching and membership testing are widely used computational primitives, employed in many programming languages and...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2017
|
| Online Access: | http://hdl.handle.net/1721.1/110931 https://orcid.org/0000-0001-7546-6313 https://orcid.org/0000-0002-7983-9524 |
| _version_ | 1826198379760189440 |
|---|---|
| author | Backurs, Arturs Indyk, Piotr |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Backurs, Arturs Indyk, Piotr |
| author_sort | Backurs, Arturs |
| collection | MIT |
| description | Regular expressions constitute a fundamental notion in formal language theory and are frequently used in computer science to define search patterns. In particular, regular expression matching and membership testing are widely used computational primitives, employed in many programming languages and text processing utilities. A classic algorithm for these problems constructs and simulates a non-deterministic finite automaton corresponding to the expression, resulting in an O(m n) running time (where m is the length of the pattern and n is the length of the text). This running time can be improved slightly (by a polylogarithmic factor), but no significantly faster solutions are known. At the same time, much faster algorithms exist for various special cases of regular expressions, including dictionary matching, wildcard matching, subset matching, word break problem etc. In this paper, we show that the complexity of regular expression matching can be characterized based on its depth (when interpreted as a formula). Our results hold for expressions involving concatenation, OR, Kleene star and Kleene plus. For regular expressions of depth two (involving any combination of the above operators), we show the following dichotomy: matching and membership testing can be solved in near-linear time, except for "concatenations of stars", which cannot be solved in strongly sub-quadratic time assuming the Strong Exponential Time Hypothesis (SETH). For regular expressions of depth three the picture is more complex. Nevertheless, we show that all problems can either be solved in strongly sub-quadratic time, or cannot be solved in strongly sub-quadratic time assuming SETH. An intriguing special case of membership testing involves regular expressions of the form "a star of an OR of concatenations", e.g., [a|ab|bc]*. This corresponds to the so-called word break problem, for which a dynamic programming algorithm with a runtime of (roughly) O(n √m) is known. We show that the latter bound is not tight and improve the runtime to O(n m[superscript 0.44...]). |
| first_indexed | 2024-09-23T11:03:57Z |
| format | Article |
| id | mit-1721.1/110931 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:03:57Z |
| publishDate | 2017 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1109312022-10-01T00:56:16Z Which Regular Expression Patterns Are Hard to Match? Backurs, Arturs Indyk, Piotr Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Backurs, Arturs Indyk, Piotr Regular expressions constitute a fundamental notion in formal language theory and are frequently used in computer science to define search patterns. In particular, regular expression matching and membership testing are widely used computational primitives, employed in many programming languages and text processing utilities. A classic algorithm for these problems constructs and simulates a non-deterministic finite automaton corresponding to the expression, resulting in an O(m n) running time (where m is the length of the pattern and n is the length of the text). This running time can be improved slightly (by a polylogarithmic factor), but no significantly faster solutions are known. At the same time, much faster algorithms exist for various special cases of regular expressions, including dictionary matching, wildcard matching, subset matching, word break problem etc. In this paper, we show that the complexity of regular expression matching can be characterized based on its depth (when interpreted as a formula). Our results hold for expressions involving concatenation, OR, Kleene star and Kleene plus. For regular expressions of depth two (involving any combination of the above operators), we show the following dichotomy: matching and membership testing can be solved in near-linear time, except for "concatenations of stars", which cannot be solved in strongly sub-quadratic time assuming the Strong Exponential Time Hypothesis (SETH). For regular expressions of depth three the picture is more complex. Nevertheless, we show that all problems can either be solved in strongly sub-quadratic time, or cannot be solved in strongly sub-quadratic time assuming SETH. An intriguing special case of membership testing involves regular expressions of the form "a star of an OR of concatenations", e.g., [a|ab|bc]*. This corresponds to the so-called word break problem, for which a dynamic programming algorithm with a runtime of (roughly) O(n √m) is known. We show that the latter bound is not tight and improve the runtime to O(n m[superscript 0.44...]). 2017-08-09T17:35:59Z 2017-08-09T17:35:59Z 2016-12 Article http://purl.org/eprint/type/ConferencePaper 978-1-5090-3933-3 0272-5428 http://hdl.handle.net/1721.1/110931 Backurs, Arturs and Indyk, Piotr. “Which Regular Expression Patterns Are Hard to Match?” 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), New Brunswick, New Jersey, USA, October 9-11 2016, Institute of Electrical and Electronics Engineers (IEEE), December 2016 https://orcid.org/0000-0001-7546-6313 https://orcid.org/0000-0002-7983-9524 en_US http://dx.doi.org/10.1109/FOCS.2016.56 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Backurs, Arturs Indyk, Piotr Which Regular Expression Patterns Are Hard to Match? |
| title | Which Regular Expression Patterns Are Hard to Match? |
| title_full | Which Regular Expression Patterns Are Hard to Match? |
| title_fullStr | Which Regular Expression Patterns Are Hard to Match? |
| title_full_unstemmed | Which Regular Expression Patterns Are Hard to Match? |
| title_short | Which Regular Expression Patterns Are Hard to Match? |
| title_sort | which regular expression patterns are hard to match |
| url | http://hdl.handle.net/1721.1/110931 https://orcid.org/0000-0001-7546-6313 https://orcid.org/0000-0002-7983-9524 |
| work_keys_str_mv | AT backursarturs whichregularexpressionpatternsarehardtomatch AT indykpiotr whichregularexpressionpatternsarehardtomatch |