Regular Expression Matching with Ordered Linear Backreferences
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Regular Expression Matching with Ordered Linear Backreferences".
Jane: Here's the gist of the paper. A new algorithm is presented that solves the regular expression matching with backreferences problem in O(n 2m) time and O(nm) space for a class of regular expressions containing a single capturing group and k references, improving previous results The paper presents Theorem 1, stating that given a regular expression of length m with a single capturing group and k references and a string of length n, the problem can be solved in O(n 2m) time and O(nm) space This result improves upon previous bounds by achieving a factor km improvement in time compared to Uezato's algorithm and an nm factor improvement in space compared to that result Theorem 2 extends this to ordered, single-nested regular expressions, also achieving O(n 2m) time and O(nm) space Data Structures The core of the algorithm relies on an interval tree data structure used to efficiently propagate feasible match endpoints across multiple references and capturing groups Specifically, each node in the interval tree stores sets of left and right match states for dyadic substrings of the input string Q, represented as bit vectors The construction of this interval tree is shown to take O(n 2m) time and O(nm) space, which is established in Lemma 3 Furthermore, the paper utilizes suffix trees to enumerate candidate strings for capturing groups and Thompson’s finite automaton (TNFA) construction for regular expressions Matching Substrings The process of finding matching substrings involves traversing the suffix tree of Q depth-first to identify all substrings q that match the base regular expression e, and then processing each such q by traversing the interval tree as described in Section 4.1 This traversal uses definitions like prefixmatchq(v) and suffixmatchq(v) to check for overlaps between leftmatchstatesq(v) and rightmatchstatesq(v) to determine if Q matches the full expression R The time complexity for this part is analyzed using Lemma 4, leading to a total time of O(n 2m) Sequential Traversal and Generalization For the more general case of ordered and single-nested rewbs, the algorithm employs a sequential interval tree traversal across multiple interval trees T1...
Tom: Tk This involves keeping track of prefix match indices across different levels to maintain feasibility for subsequent expressions The analysis shows that the total time complexity remains O(n 2m) and the space complexity is O(nm) This sequential approach allows for a decomposition of the complex pattern into manageable blocks, processing them successively while carrying forward feasible endpoints Correctness Proof The correctness of the algorithm is established through several lemmas, including Lemma 5 and Lemma 6, which prove that the procedure correctly computes the intersection of leftmatchstatesq(v) and rightmatchstatesq(v) for every node v in T Lemma 6 further shows that the overlap of these sets is equivalent to Q matching R, by decomposing Q into W0qw1qw2 where w0 matches e0, q matches e, and w1 matches e1 The final step involves postprocessing by checking if an index i in the set endpoints satisfies i + 1 is in suffixset to confirm a full match Analysis Summary The overall time complexity is derived from the sum of preprocessing, finding matching substrings, and processing substrings, resulting in O(n 2m) time The space complexity is bounded by O(nm), which is achieved through careful management of the interval trees and automaton states This efficiency is maintained even when generalizing to multiple references, where the total time remains O(n 2m) The analysis demonstrates that the algorithm successfully handles the complexity introduced by backreferences in a polynomial manner relative to m References
1: Alfred V.
Jane: Aho, Algorithms for finding patterns in strings, In Algorithms and Complexity, Handbook of Theoretical Computer Science, pages 255–300, Elsevier, Amsterdam, 1990
2: Arturs Backurs and Piotr Indyk.
Tom: Which regular expression patterns are hard to match?, In Proc.
Paper summary: Tom: So, wrapping up this paper "Regular Expression Matching with Ordered Linear Backreferences," the authors have successfully shown a way to solve this problem for regular expressions with a single capturing group and several references efficiently.
Jane: The authors of this work are Philip Bille, Inge Li Gørtz, Rikke Schjeldrup, and Jessen rscje >
Lu: It’s important to note that they extend the result to ordered and single-nested regular expressions as well by using a sequential interval tree traversal across multiple trees >
Meng: The implications are that for things like symbolic execution or complex string constraint solving, we might finally have an efficient way to handle these patterns without relying on exponential time solutions >
Tom: The main takeaway is the O(n squared times m) time and O(nm) space complexity they achieved for this specific class of regular expressions >
Jane: In simpler terms, if you have a string of length n and a pattern of length m with one group and k references, this algorithm can check for a match in time proportional to n squared times m >
Lalam: This is solid work because they've done it by proving correctness through lemmas like Lemma five and Lemma six which show the overlap calculation is sound > <ref:2609.16914#pg3>
Tom: It’s a significant step forward because it improves upon previous bounds by showing a factor k improvement in time compared to Uezato’s algorithm >
Jane: So, for listeners who might not be deeply into regex theory, this means that matching these types of patterns is no longer inherently intractable if the structure fits this specific form >
Meng: I just worry about the constant factors and whether it holds up when we move to more chaotic real-world data streams where n is massive >
Lu: The paper does acknowledge its limitations, though, they state that their results are conditional on certain hypotheses regarding orthogonal vectors >
Tom: So, while it's a strong polynomial result with clear bounds, the authors are careful about the conditions under which these specific performance guarantees hold >
Conclusion: Tom: So, we’re wrapping up our look at "Regular Expression Matching with Ordered Linear Backreferences." This paper tackles how to match those complex patterns—the ones with multiple backreferences—in a regular expression without letting the time explode.
Jane: Right, so we've seen them talk about this new algorithm and how it uses interval trees to keep track of matching pieces across all those different references. But what does that actually mean for the person who just wants to check if a specific piece of text matches a complicated instruction?
Lu: Basically, they’ve managed to bound the time complexity at n squared times m, where n is the length of your string and m is the length of your pattern. That's a big improvement over what we saw before for this kind of problem.
Meng: A quadratic time complexity means if you double the size of your input string, it gets four times slower. I need to know how that scales when we move from small test cases to real traffic where n is huge and m is complicated.
Tom: That's the million-dollar question for me, Meng. The paper shows they’ve improved Uezato's time bound by a factor of k, which is the number of those backreferences. That’s a tangible improvement on their previous results.
Jane: So it means for someone building systems that check these kinds of patterns—maybe in code or in data pipelines—they can finally handle these multi-reference requirements with a polynomial time guarantee instead of something that just runs forever.
Lu: Exactly. And they extend this to regular expressions that have nested levels, meaning you can have backreferences inside other backreferences too, and the time complexity stays at n squared times m for those cases too.
Tom: It’s solid work because they proved it using these interval tree structures and suffix trees to find those candidate substrings efficiently before running the main check. That methodology is pretty clean.
Jane: And their conclusion is that this approach gives us a concrete, scalable way to solve this problem for a whole class of regular expressions, which is really useful for things like complex string constraints in AI or security checks.
Lu: So, the authors are saying they’ve found a robust way to manage the complexity introduced by those backreferences without losing that polynomial efficiency. But they're also careful about the conditions under which these specific performance guarantees hold, which is always important.
Meng: And for deployment, we still need to figure out how much space this takes, because O of n times m space might be manageable on a small machine but becomes a real problem at scale if n and m are both massive.
Tom: That’s the next big thing for me—the space complexity. We need to know the memory footprint when we try to run these algorithms in production environments where resources are tight.
Jane: We'll be diving into those details next, and we’ll see if this new technique actually translates well from theory to something you can actually ship.
DTU
cs.DS
Submitted: 2026-09-15
Updated: 2026-11-16
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 82/100
The gist: A new algorithm is presented that solves the regular expression matching with backreferences problem in O(n 2m) time and O(nm) space for a class of regular expressions containing a single capturing…
Key concepts
- Interval Tree
- This data structure is central to the algorithm. It is used to efficiently track feasible match endpoints across multiple references and capturing groups. Each node stores sets of left and right match states for dyadic substrings of the input string, represented as bit vectors, allowing for fast overlap checks.
- Suffix Tree
- A suffix tree is used to enumerate all substrings of the input string Q that match the base regular expression e. By traversing this tree depth-first, the algorithm identifies all candidate substrings that could potentially satisfy the pattern before checking them against backreferences.
- Backreferences Matching
- This refers to handling instances where a part of a regular expression refers back to a previously matched substring. The algorithm manages this complexity by using the interval tree to check for overlaps between left and right match states, ensuring that the chosen substrings satisfy all required dependencies defined by the backreferences.
- Sequential Traversal
- For more complex patterns like ordered and single-nested regular expressions, the algorithm uses a sequential traversal across multiple interval trees. This method maintains feasibility by tracking prefix match indices across different levels of nesting, allowing the decomposition of complex patterns into manageable blocks.
Terminology
Summary
A new algorithm is presented that solves the regular expression matching with backreferences problem in O(n 2m) time and O(nm) space for a class of regular expressions containing a single capturing group and k references, improving previous results
Main Results
The paper presents Theorem 1, stating that given a regular expression of length m with a single capturing group and k references and a string of length n, the problem can be solved in O(n 2m) time and O(nm) space This result improves upon previous bounds by achieving a factor km improvement in time compared to Uezato's algorithm and an nm factor improvement in space compared to that result Theorem 2 extends this to ordered, single-nested regular expressions, also achieving O(n 2m) time and O(nm) space
Data Structures
The core of the algorithm relies on an interval tree data structure used to efficiently propagate feasible match endpoints across multiple references and capturing groups Specifically, each node in the interval tree stores sets of left and right match states for dyadic substrings of the input string Q, represented as bit vectors The construction of this interval tree is shown to take O(n 2m) time and O(nm) space, which is established in Lemma 3 Furthermore, the paper utilizes suffix trees to enumerate candidate strings for capturing groups and Thompson’s finite automaton (TNFA) construction for regular expressions
Matching Substrings
The process of finding matching substrings involves traversing the suffix tree of Q depth-first to identify all substrings q that match the base regular expression e, and then processing each such q by traversing the interval tree as described in Section 4.1 This traversal uses definitions like prefixmatchq(v) and suffixmatchq(v) to check for overlaps between leftmatchstatesq(v) and rightmatchstatesq(v) to determine if Q matches the full expression R The time complexity for this part is analyzed using Lemma 4, leading to a total time of O(n 2m)
Sequential Traversal and Generalization
For the more general case of ordered and single-nested rewbs, the algorithm employs a sequential interval tree traversal across multiple interval trees T1... Tk This involves keeping track of prefix match indices across different levels to maintain feasibility for subsequent expressions The analysis shows that the total time complexity remains O(n 2m) and the space complexity is O(nm) This sequential approach allows for a decomposition of the complex pattern into manageable blocks, processing them successively while carrying forward feasible endpoints
Correctness Proof
The correctness of the algorithm is established through several lemmas, including Lemma 5 and Lemma 6, which prove that the procedure correctly computes the intersection of leftmatchstatesq(v) and rightmatchstatesq(v) for every node v in T Lemma 6 further shows that the overlap of these sets is equivalent to Q matching R, by decomposing Q into W0qw1qw2 where w0 matches e0, q matches e, and w1 matches e1 The final step involves postprocessing by checking if an index i in the set endpoints satisfies i + 1 is in suffixset to confirm a full match
Analysis Summary
The overall time complexity is derived from the sum of preprocessing, finding matching substrings, and processing substrings, resulting in O(n 2m) time The space complexity is bounded by O(nm), which is achieved through careful management of the interval trees and automaton states This efficiency is maintained even when generalizing to multiple references, where the total time remains O(n 2m) The analysis demonstrates that the algorithm successfully handles the complexity introduced by backreferences in a polynomial manner relative to m
References
[1] Alfred V. Aho, Algorithms for finding patterns in strings, In Algorithms and Complexity, Handbook of Theoretical Computer Science, pages 255–300, Elsevier, Amsterdam, 1990
[2] Arturs Backurs and Piotr Indyk. Which regular expression patterns are hard to match? p. 3, In Proc. 57th FOCS, pages 457–466, 2016
[3] Philip Bille, New algorithms for regular expression matching, In Proc. 33rd ICALP, pages 643–654, 2006
[4] Philip Bille and Martin Farach-Colton. Fast and compact regular expression matching, Theoret. p. 0 Comput. Sci., 409:486 – 496, 2008
[5] Philip Bille and Mikkel Thorup. Faster regular expression matching, In Proc. p. 0 36th ICALP, pages 171–182, 2009
[6] Philip Bille and Mikkel Thorup. Regular expression matching with multi-strings and intervals, In Proc. p. 1 21st SODA, 2010
[7] Karl Bringmann, Allan Grønlund, and Kasper Green Larsen. A dichotomy for regular expression membership testing, In Proc. p. 1 58th FOCS, pages 307–318, 2017
[8] Taolue Chen et al., Solving string constraints with regexdependent functions through transducers with priorities and variables, In Proc. p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 49th POPL, 2022
[9] Martin Farach-Colton et al., On the sorting-complexity of suffix tree construction, J. p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 ACM, 47(6):987–1011, 2000
[10] Dominik D Freydenberger and Markus L Schmid. Deterministic regular expressions with backreferences, J. p. 0 Comput. Syst. Sci., 105:1–39, 2019
[13] Soh Kumabe and Yuya Uezato, On the Complexity of the Matching Problem of Regular Expressions with Backreferences, In Proc. 53rd ICALP, pages 135:1–135:25, 2026
[14] Kim S. Larsen, Regular expressions with nested levels of back referencing form a hierarchy, Inform. p. 5 p. 5 Process Lett. p. 1 p. 1, 65(4):169–172, 1998
[15] Blake Loring et al., Sound regular expression semantics for dynamic symbolic execution of javascript, In Proc. p. 1 40th PLDI, pages 425–438, 2019
[16] R. McNaughton and H. Yamada, Regular expressions and state graphs for automata, IRE Trans. p. 2 on Electronic Computers, 9(1):39–47, 1960
[23] K. Thompson, Regular expression search algorithm, Commun. p. 3 ACM, 11:419–422, 1968
[24] Yuya Uezato, Matching Regular-Typed Pattern Languages: Quadratic-Time Algorithms, In Proc. 37th CPM 2026, pages 11:1–11:20, 2026
[58] Taisei Nogami and Tachio Terauchi, Efficient Matching of Some Fundamental Regular Expressions with Backreferences, In Proc. 50th MFCS 2025, pages 81:1–81:19, 2025
[7] Karl Bringmann et al., A dichotomy for regular expression membership testing, In Proc. p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 58th FOCS, pages 307–318, 2017
[8] Taolue Chen et al., Solving string constraints with regexdependent functions through transducers with priorities and variables, In Proc. 49th POPL, 2022
[9] Martin Farach-Colton et al., On the sorting-complexity of suffix tree construction, J. ACM, 47(6):987–1011, 2000
[13] Soh Kumabe and Yuya Uezato, On the Complexity of the Matching Problem of Regular Expressions with Backreferences, In Proc. 53rd ICALP, pages 135:1–135:25, 2026
[14] Kim S. Larsen, Regular expressions with nested levels of back referencing form a hierarchy, Inform. Process Lett., 65(4):169–172, 1998
[20] Taisei Nogami and Tachio Terauchi, Efficient Matching of Some Fundamental Regular Expressions with Backreferences, In Proc. 50th MFCS 2025, pages 81:1–81:19, 2025
[3] Philip Bille, New algorithms for regular expression matching, In Proc. 33rd ICALP, pages 643–654, 2006
[7] Karl Bringmann et al., A dichotomy for regular expression membership testing, In Proc. 58th FOCS, pages 307–318, 2017
[8] Taolue Chen et al., Solving string constraints with regexdependent functions through transducers with priorities and variables, In Proc. 49th POPL, 2022
[9] Martin Farach-Colton et al., On the sorting-complexity of suffix tree construction, J. ACM, 47(6):987–1011, 2000
[3] Philip Bille, New algorithms for regular expression matching, In Proc. 33rd ICALP, pages 643–654, 2006
[7] Karl Bringmann et al., A dichotomy for regular expression membership testing, In Proc. 58th FOCS, pages 307–318, 2017
[8] Taolue Chen et al., Solving string constraints with regexdependent functions through transducers with priorities and variables, In Proc. 49th POPL, 2022
[9] Martin Farach-Colton et al., On the sorting-complexity of suffix tree construction, J. ACM, 47(6):987–1011, 2000
[3] Philip Bille, New algorithms for regular expression matching, In Proc. 33rd ICALP, pages 643–654, 2006
[7] Karl Bringmann et al., A dichotomy for regular expression membership testing, In Proc. 58th FOCS, pages 307–318, 2017
[8] Taolue Chen et al., Solving string constraints with regexdependent functions through transducers with priorities and variables, In Proc. 49th POPL, 2022
[9] Martin Farach-Colton et al., On the sorting-complexity of suffix tree construction, J. ACM, 47(6):987–1011, 2000
[3] Philip Bille, New algorithms for regular expression matching, In Proc. 33rd ICALP, pages 643–654, 2006
[7] Karl Bringmann et al., A dichotomy for regular expression membership testing, In Proc. 58th FOCS, pages 307–318, 2017
[8] Taolue Chen et al., Solving string constraints with regexdependent functions through transducers with priorities and variables, In Proc. 49th POPL, 2022
[9] Martin Farach-Colton et al., On the sorting-complexity of suffix tree construction, J. ACM, 47(6):987–1011, 2000
[3] Philip Bille, New algorithms for regular expression matching, In Proc. 33rd ICALP, pages 643–654, 2006
[7] Karl Bringmann et al., A dichotomy for regular expression membership testing, In Proc. 58th FOCS, pages 307–318, 2017
[8] Taolue Chen et al., Solving string constraints with regexdependent functions through transducers with priorities and variables, In Proc. 49th POPL, 2022
[9] Martin Farach-Colton et al., On the sorting-complexity of suffix tree construction, J. ACM, 47(6):987–1011, 2000
[3] Philip Bille, New algorithms for regular expression matching, In Proc. 33rd ICALP, pages 643–654, 2006
[7] Karl Bringmann et al., A dichotomy for regular expression membership testing, In Proc. 58th FOCS, pages 307–318, 2017
[8] Taolue Chen et al., Solving string constraints with regexdependent functions through transducers with priorities and variables, In Proc. 49th POPL, 2022
[9] Martin Farach-Colton et al., On the sorting-complexity of suffix tree construction, J. ACM, 47(6):987–1011, 2000
[3] Philip Bille, New algorithms for regular expression matching, In Proc. 33rd ICALP, pages 643–654, 2006
[7] Karl Bringmann et al., A dichotomy for regular expression membership testing, In Proc. 58th FOCS, pages 307–318, 2017
[8] Taolue Chen et al., Solving string constraints with regexdependent functions through transducers with priorities and variables, In Proc. 49th POPL, 2022
[9] Martin Farach-Colton et al., On the sorting-complexity of suffix tree construction, J. ACM, 47(6):987–1011, 2000
[3] Philip Bille, New algorithms for regular expression matching, In Proc. 33rd ICALP, pages 643–654, 2006
[7] Karl Bringmann et al., A dichotomy for regular expression membership testing, In Proc. 58th FOCS, pages 307–318, 2017
[8] Taolue Chen et al., Solving string constraints with regexdependent functions through transducers with priorities and variables, In Proc. 49th POPL, 2022
[9] Martin Farach-Colton et al., On the sorting-complexity of suffix tree construction, J. ACM, 47(6):987–1011, 2000
[3] Philip Bille, New algorithms for regular expression matching, In Proc. 33rd ICALP, pages 643–654, 2006
[7] Karl Bringmann et al., A dichotomy for regular expression membership testing, In Proc. 58th FOCS, pages 307–318, 2017
[8] Taolue Chen et al., Solving string constraints with regexdependent functions through transducers with priorities and variables, In Proc. 49th POPL, 2022 <ref:2609. p. 0
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Efficient regular expression matching for patterns with a single capturing group and multiple references can be solved in O(n 2m) time and O(nm) space, improving upon previous bounds like Uezato's O((kn 2m 2)) time for general k references.
-
The algorithm can determine if a string Q matches a regular expression with backreferences by traversing interval trees and checking for overlaps between leftmatchstatesq and rightmatchstatesq, which is proven to be correct by Lemma 6:
Given a non-empty substring q of Q that matches e, the sets leftmatchstatesq(v) and rightmatchstatesq(v) intersect for some v in T if and only if Q matches e0 ⊙ q ⊙ e1 ⊙ q ⊙ e2.
-
The system can handle a more general class of ordered and single-nested regular expressions by extending the technique to sequential interval tree traversal, allowing it to solve matching problems for patterns like R = E0E1... Etet+1,0 in O(n 2m) time and O(nm) space.
-
The improved system can perform robust string constraint solving and symbolic execution by utilizing the fast regular expression matching algorithms described, which are supported across a wide range of applications including network intrusion detection and graph-database querying.
Sources
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time