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}
}