Towards Efficient Matching of Regexes with Backreferences using Register Set Automata (Technical Report)

[2205.12114] Towards Efficient Matching of Regexes with Backreferences using Register Set Automata (Technical Report) Skip to main content Search Submit Donate Log in Search arXiv Press Enter to search · Advanced search Computer Science > Logic in Computer Science arXiv:2205.12114 (cs) [Submitted on 24 May 2022 ( v1 ), last revised 15 Apr 2026 (this version, v5)] Title: Towards Efficient Matching of Regexes with Backreferences using Register Set Automata (Technical Report) Authors: Vojtěch Havlena , Lukáš Holík , Ondřej Lengál , Jan Vašák , Sabína Gulčíková View a PDF of the paper titled Towards Efficient Matching of Regexes with Backreferences using Register Set Automata (Technical Report), by Vojt\v{e}ch Havlena and Luk\'a\v{s} Hol\'ik and Ond\v{r}ej Leng\'al and Jan Va\v{s}\'ak and Sab\'ina Gul\v{c}\'ikov\'a View PDF HTML (experimental) Abstract: Matching regexes (regular expressions) is a common problem in many areas of computer science, with requirements on high speed and robust performance. Regexes with backreferences allow one to express certain patterns (even beyond regular) concisely, however, since the matching is usually done by backtracking, the matching speed can degrade to a degree that constitutes a service failure or a security threat. To facilitate high-speed matching of such regexes, we propose register set automata (RSAs), an extension of register automata where registers can contain sets of symbols (from a potentially infinite alphabet) and the following operations are supported: adding input values to registers, merging or clearing registers, and testing whether a register contains a value. We show that a large class of register automata can be transformed into deterministic RSAs, which can serve as a basis for fast matching of a family of regexes with single-letter capture groups and backreferences. We also give a derivative-based algorithm for transforming a large class of regexes with backreferences to register automata and show that the time complexity of matching is linear and quadratic to the length of the input for finite and infinite alphabets respectively. Our prototype implementation of a regex matcher shows that our approach can significantly improve the robustness of state-of-the-art regex matchers on regexes with backreferences. We also study the theoretical properties of the model and show that the emptiness problem for RSAs is decidable and complete for the $\mathbf{F}_\omega$ class and that RSAs are incomparable in expressive power to other popular automata models over data words. Comments: Accepted for PLDI'26 Subjects: Logic in Computer Science (cs.LO) ; Formal Languages and Automata Theory (cs.FL) Cite as: arXiv:2205.12114 [cs.LO] (or arXiv:2205.12114v5 [cs.LO] for this version) https://doi.org/10.48550/arXiv.2205.12114 Focus to learn more arXiv-issued DOI via DataCite Submission history From: Ondřej Lengál [ view email ] [v1] Tue, 24 May 2022 14:45:38 UTC (364 KB) [v2] Tue, 2 Aug 2022 12:45:42 UTC (365 KB) [v3] Thu, 8 Dec 2022 07:57:07 UTC (365 KB) [v4] Mon, 13 Apr 2026 20:14:52 UTC (635 KB) [v5] Wed, 15 Apr 2026 11:05:09 UTC (660 KB) Full-text links: Access Paper: View a PDF of the paper titled Towards Efficient Matching of Regexes with Backreferences using Register Set Automata (Technical Report), by Vojt\v{e}ch Havlena and Luk\'a\v{s} Hol\'ik and Ond\v{r}ej Leng\'al and Jan Va\v{s}\'ak and Sab\'ina Gul\v{c}\'ikov\'a View PDF HTML (experimental) TeX Source view license Current browse context: cs.LO < prev | next > new | recent | 2022-05 Change to browse by: cs cs.FL References & Citations NASA ADS Google Scholar Semantic Scholar export BibTeX citation Loading... BibTeX formatted citation × loading... Data provided by: Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer ( What is the Explorer? ) Connected Papers Toggle Connected Papers ( What is Connected Papers? ) Litmaps Toggle Litmaps ( What is Litmaps? ) scite.ai Toggle scite Smart Citations ( What are Smart Citations? ) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv ( What is alphaXiv? ) Links to Code Toggle CatalyzeX Code Finder for Papers ( What is CatalyzeX? ) DagsHub Toggle DagsHub ( What is DagsHub? ) GotitPub Toggle Gotit.pub ( What is GotitPub? ) Huggingface Toggle Hugging Face ( What is Huggingface? ) ScienceCast Toggle ScienceCast ( What is ScienceCast? ) Demos Demos Replicate Toggle Replicate ( What is Replicate? ) Spaces Toggle Hugging Face Spaces ( What is Spaces? ) Spaces Toggle TXYZ.AI ( What is TXYZ.AI? ) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower ( What are Influence Flowers? ) Core recommender toggle CORE Recommender ( What is CORE? ) Author Venue Institution Topic About arXivLabs arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs . Which authors of this paper are endorsers? | Disable MathJax ( What is MathJax? ) We gratefully acknowledge support from our major funders , member institutions , , and all contributors. About · Help · Contact · Subscribe · Copyright · Privacy · Accessibility · Operational Status (opens in new tab) Major funding support from

Related documents

• MDL-Calibrated Significance-Gain Pair Encoding: Replication-Aware Automatic Stopping for Subword Tokenization#1115661
• The Language Space Framework_ A Conceptual Theory for Reasoning About Symbolic Expressions_#706428
• Robust XML Encoding Rules (RXER) for Abstract Syntax Notation One (ASN.1)#500889
• Putting Registers to Work: Task Registers for Token Pruning in Vision Transformers#444674
• Protein sequence domain annotation using a language model#10114