语义正则表达式的成员测试

本文研究了语义正则表达式的成员测试问题，提出了一种基于NFA的两遍算法，用于确定字符串是否匹配语义正则表达式。该算法时间复杂度为O(|r|^2 |w|^2 + |r| |w|^3)，在没有嵌套查询的常见情况下，时间复杂度为O(|r|^2 |w|^2)。实验验证了该算法的有效性，其性能远超基于动态规划的基线方法。此外，文章还探讨了语义正则表达式成员测试与图论中三角形查找问题之间的联系，并证明了进行成员测试所需oracle查询次数的下界为Ω(|w|^2)。