一句话：研究语义正则表达式（SemREs）的成员测试问题，即判定字符串是否匹配带外部 oracle 查询的正则模式。
该论文关注语义正则表达式（SemREs）。SemREs 由 Chen 等人提出，在经典正则表达式基础上增加查询外部 oracle（如数据库和大语言模型）的原语，用于识别包含城市、名人、政治实体等语义概念引用的文本行。已有工作侧重从正负例自动合成语义正则表达式；本文则转向成员测试问题，即给定语义正则表达式和输入字符串，判断其是否属于该表达式所定义的语言。由于摘要在此处截断，论文提出的具体算法、复杂度结果和实验评估未在摘要中展开；其核心贡献在于将成员测试确立为 SemREs 的独立研究问题。
This paper is about semantic regular expressions (SemREs). This is a concept that was recently proposed by Chen et al. [ 9 ] in which classical regular expressions are extended with a primitive to query external oracles such as databases and large language models (LLMs). SemREs can be used to identify lines of text containing references to semantic concepts such as cities, celebrities, political entities, etc. The focus in their paper was on automatically synthesizing semantic regular expressions from positive and negative examples. In this paper, we study the membership testing problem :
@article{paperbot3107,
title = {Membership Testing for Semantic Regular Expressions},
author = {Yifei Huang and Matin Amini and Alexis Le Glaunec and Konstantinos Mamouras and Mukund Raghothaman},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {PLDI},
year = {2025},
doi = {10.1145/3729300}
}