一句话：将字符串相等选择内嵌进正则语言，提出 Refl-Spanners，以略弱表达力换取更好的静态分析与查询求值上界。
正则 Spanner（可由 vset-自动机刻画）对并、连接和投影封闭，具有良好的算法性质。核心 Spanner 在此基础上加入字符串相等选择，用于刻画 IBM SystemT 中 AQL 查询语言的核心功能，但已有工作表明这会导致静态分析与查询求值问题复杂度很高甚至不可判定。本文提出 Refl-Spanners：不再把字符串相等选择视为对正则 Spanner 抽出表施加的代数操作，而是将其直接并入表示底层正则 Spanner 的正则语言。由此得到核心 Spanner 的一个片段，其表达力比完整核心 Spanner 略弱，但仍能覆盖信息抽取中字符串相等选择的直观应用，并且静态分析和查询求值的典型问题具有更好的复杂度上界。
The regular spanners (characterised by vset-automata) are closed under the algebraic operations of union, join and projection, and have desirable algorithmic properties. The core spanners (introduced by Fagin, Kimelfeld, Reiss, and Vansummeren (PODS 2013, JACM 2015) as a formalisation of the core functionality of the query language AQL used in IBM's SystemT) additionally need string-equality selections and it has been shown by Freydenberger and Holldack (ICDT 2016, Theory of Computing Systems 2018) that this leads to high complexity and even undecidability of the typical problems in static analysis and query evaluation. We propose an alternative approach to core spanners: by incorporating the string-equality selections directly into the regular language that represents the underlying regular spanner (instead of treating it as an algebraic operation on the table extracted by the regular spanner), we obtain a fragment of core spanners that, while having slightly weaker expressive power than the full class of core spanners, arguably still covers the intuitive applications of string-equality selections for information extraction and has much better upper complexity bounds of the typical problems in static analysis and query evaluation.
@article{paperbot2706,
title = {Refl-Spanners: A Purely Regular Approach to Non-Regular Core Spanners},
author = {Markus L. Schmid and Nicole Schweikardt},
journal = {Logical Methods in Computer Science},
volume = {Volume 20, Issue 4},
year = {2024},
doi = {10.46298/lmcs-20(4:16)2024}
}