主要观点：SMORE 近期提出语义正则表达式概念，本文研究其成员测试问题。
关键信息：

• 给出基于 NFA 的两阶段算法，在不同假设下确定字符串与语义正则表达式是否匹配及时间复杂度。
• 建立语义正则表达式成员测试与图论中三角形发现问题的联系。
• 指出经典正则表达式算法主要优化时间和内存消耗，而本文需考虑最小化调用外部或acles 的成本。
• 证明确定所需外部 oracles 查询数量有(\Omega(|w|^2))下限。
  重要细节：
• 论文原作者为 Chen 等（2023 年），本文作者为 Yifei Huang。
• 提交版本为 v1，时间为 2024 年 10 月 17 日 06:33:16 UTC，文件大小 100 KB。
• 可通过View PDF、HTML (experimental)查看，引用为arXiv:2410.13262 [cs.PL]（此版本为arXiv:2410.13262v1 [cs.PL]），也可通过https://doi.org/10.48550/arXiv.2410.13262查看。