一句话：提出寄存器集合自动机（RSA），将一类带反向引用的正则表达式确定化，实现线性/二次时间匹配并提升鲁棒性。
带反向引用的正则匹配常依赖回溯，复杂模式可能严重退化并引发服务失败或安全威胁。论文提出寄存器集合自动机（RSA）：寄存器可保存可能无限字母表上的符号集合，支持加入输入值、合并/清空及成员测试。作者证明一大类寄存器自动机可确定化为 RSA，用于单字母捕获组和反向引用正则的高速匹配；并给出基于导数的算法，将一大类此类正则转为寄存器自动机。匹配复杂度在有限与无限字母表下分别为输入长度的线性与二次；原型显著提升了现有匹配器的鲁棒性。此外，RSA 空性可判定且对 Fω 完全，表达力与数据字上常见自动机不可比。
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 F ω class and that RSAs are incomparable in expressive power to other popular automata models over data words.
@article{paperbot3759,
title = {Towards Efficient Matching of Regexes with Backreferences using Register Set Automata},
author = {Vojtěch Havlena and Lukáš Holík and Ondřej Lengál and Jan Vašák and Sabína Gulčíková},
journal = {Proceedings of the ACM on Programming Languages},
volume = {10},
number = {PLDI},
year = {2026},
doi = {10.1145/3808281}
}