Cover Image

On the Complexity of the Matching Problem of Regular Expressions with Backreferences

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kumabe, Soh, Uezato, Yuya
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Computation and Language
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Efficient Matching of Some Fundamental Regular Expressions with Backreferences
by: Nogami, Taisei, et al.
Published: (2025)

Average sensitivity of the Knapsack Problem
by: Kumabe, Soh, et al.
Published: (2024)

Lipschitz Continuous Algorithms for Covering Problems
by: Kumabe, Soh, et al.
Published: (2023)

Quadratic Kernel for Cliques or Trees Vertex Deletion
by: Kumabe, Soh
Published: (2025)

Max-Distance Sparsification for Diversification and Clustering
by: Kumabe, Soh
Published: (2024)

Regular Expressions with Backreferences and Lookaheads Capture NLOG
by: Uezato, Yuya
Published: (2024)

Lipschitz Continuous Allocations for Optimization Games
by: Kumabe, Soh, et al.
Published: (2024)

Courcelle's Theorem for Lipschitz Continuity
by: Gima, Tatsuya, et al.
Published: (2025)

Hardness of Regular Expression Matching with Extensions
by: Nogami, Taisei, et al.
Published: (2026)

Dichotomies for Tree Minor Containment with Structural Parameters
by: Gima, Tatsuya, et al.
Published: (2023)

Improved Extended Regular Expression Matching
by: Bille, Philip, et al.
Published: (2025)

Permutation Matching Under Parikh Budgets: Linear-Time Detection, Packing, and Disjoint Selection
by: Shanto, MD Nazmul Alam, et al.
Published: (2026)

On the Randomized Locality of Matching Problems in Regular Graphs
by: Khoury, Seri, et al.
Published: (2025)

Complexity and Algorithm for the Matching vertex-cutset Problem
by: Li, Hengzhe, et al.
Published: (2025)

Subsequences in Bounded Ranges: Matching and Analysis Problems
by: Kosche, Maria, et al.
Published: (2022)

Fine-Grained Complexity of Regular Path Queries
by: Casel, Katrin, et al.
Published: (2021)

The Fine-Grained Complexity of Episode Matching
by: Bille, Philip, et al.
Published: (2021)

Dynamic Boundary Time Warping for Sub-sequence Matching with Few Examples
by: Borchmann, Łukasz, et al.
Published: (2020)

Flashback: A Reversible Bilateral Run-Peeling Decomposition of Strings
by: Konstantinovsky, Thomas, et al.
Published: (2026)

Towards Optimal Multi-draft Speculative Decoding
by: Hu, Zhengmian, et al.
Published: (2025)

Theoretical Analysis of Byte-Pair Encoding
by: Kozma, László, et al.
Published: (2024)

Structured Tree Alignment for Evaluation of (Speech) Constituency Parsing
by: Shi, Freda, et al.
Published: (2024)

Fast Exact Retrieval for Nearest-neighbor Lookup (FERN)
by: Zhu, Richard
Published: (2024)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
by: Assadi, Sepehr, et al.
Published: (2024)

On the Advice Complexity of Online Matching on the Line
by: Csaba, Béla, et al.
Published: (2024)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
by: Chudigiewitsch, Florian, et al.
Published: (2026)

Complexity of Local Search for Euclidean Clustering Problems
by: Manthey, Bodo, et al.
Published: (2023)

On the Complexity of the Ordered Covering Problem in Distance Geometry
by: Souza, Michael, et al.
Published: (2025)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
by: Nederlof, Jesper
Published: (2026)

The Communication Complexity of Pattern Matching with Edits Revisited
by: Kociumaka, Tomasz, et al.
Published: (2026)

Matching (Multi)Cut: Algorithms, Complexity, and Enumeration
by: Gomes, Guilherme C. M., et al.
Published: (2024)

Semi-Robust Communication Complexity of Maximum Matching
by: Huete, Gabriel Cipriani, et al.
Published: (2025)

On the Complexity of Secluded Path Problems
by: Hanaka, Tesshu, et al.
Published: (2026)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
by: Shih, Yu-Sheng, et al.
Published: (2026)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
by: Focke, Jacob, et al.
Published: (2023)

A Complexity Analysis of the c-Closed Vertex Deletion Problem
by: Lehner, Lisa, et al.
Published: (2025)

On the Complexity of the Odd-Red Bipartite Perfect Matching Polytope
by: Nägele, Martin, et al.
Published: (2026)

A New Impossibility Result for Online Bipartite Matching Problems
by: Chierichetti, Flavio, et al.
Published: (2025)

Optimizing Inventory Placement for a Downstream Online Matching Problem
by: Epstein, Boris, et al.
Published: (2024)

Towards Settling the Complexity of the Lettericity Problem
by: Grobler, Mario, et al.
Published: (2026)