一句话：系统分析正则文档跨度器上聚合查询的精确与近似计算复杂度，并给出多项式时间与 FPRAS 边界。
带捕获变量的正则表达式（regex-formulas）可从文本中抽取由起止索引标识的跨度关系；正则文档跨度器（regular document spanners）是这类表达式在关系代数下的闭包。本文研究在正则文档跨度器上执行聚合查询（如 sum、average、quantile）的计算复杂度。作者形式化定义了作用于正则文档跨度器的聚合函数，并分析其精确计算与近似计算的复杂度：在受限情形下，所研究的聚合均可在多项式时间内计算；而在一般情况下，精确计算是难解的，但部分聚合函数仍可用全多项式时间随机近似方案（FPRAS）进行近似。该工作为文本信息抽取查询中的聚合操作提供了复杂度理论边界。
Regular expressions with capture variables, also known as regex-formulas, extract relations of spans (intervals identified by their start and end indices) from text. In turn, the class of regular document spanners is the closure of the regex formulas under the Relational Algebra. We investigate the computational complexity of querying text by aggregate functions, such as sum, average, and quantile, on top of regular document spanners. To this end, we formally define aggregate functions over regular document spanners and analyze the computational complexity of exact and approximate computation. More precisely, we show that in a restricted case, all studied aggregate functions can be computed in polynomial time. In general, however, even though exact computation is intractable, some aggregates can still be approximated with fully polynomial-time randomized approximation schemes (FPRAS).
@article{paperbot2198,
title = {The Complexity of Aggregates over Extractions by Regular Expressions},
author = {Johannes Doleschal and Benny Kimelfeld and Wim Martens},
journal = {Logical Methods in Computer Science},
volume = {Volume 19, Issue 3},
year = {2023},
doi = {10.46298/lmcs-19(3:12)2023}
}