Regular Expressions with Backreferences: Polynomial-Time Matching Techniques
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2019
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917584577757184 |
|---|---|
| author | Schmid, Markus L. |
| author_facet | Schmid, Markus L. |
| contents | Regular expressions with backreferences (regex, for short), as supported by most modern libraries for regular expression matching, have an NP-complete matching problem. We define a complexity parameter of regex, called active variable degree, such that regex with this parameter bounded by a constant can be matched in polynomial-time. Moreover, we formulate a novel type of determinism for regex (on an automaton-theoretic level), which yields the class of memory-deterministic regex that can be matched in time O(|w|p(|r|)) for a polynomial p (where r is the regex and w the word). Natural extensions of these concepts lead to properties of regex that are intractable to check. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1903_05896 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Regular Expressions with Backreferences: Polynomial-Time Matching Techniques Schmid, Markus L. Formal Languages and Automata Theory Information Retrieval F.1.1; F.2.2; F.4.3; H.3.3 Regular expressions with backreferences (regex, for short), as supported by most modern libraries for regular expression matching, have an NP-complete matching problem. We define a complexity parameter of regex, called active variable degree, such that regex with this parameter bounded by a constant can be matched in polynomial-time. Moreover, we formulate a novel type of determinism for regex (on an automaton-theoretic level), which yields the class of memory-deterministic regex that can be matched in time O(|w|p(|r|)) for a polynomial p (where r is the regex and w the word). Natural extensions of these concepts lead to properties of regex that are intractable to check. |
| title | Regular Expressions with Backreferences: Polynomial-Time Matching Techniques |
| topic | Formal Languages and Automata Theory Information Retrieval F.1.1; F.2.2; F.4.3; H.3.3 |
| url | https://arxiv.org/abs/1903.05896 |