{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T08:32:36Z","timestamp":1785227556026,"version":"3.55.0"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Regular expressions with capture variables, also known as regex-formulas,\nextract relations of spans (intervals identified by their start and end\nindices) from text. In turn, the class of regular document spanners is the\nclosure of the regex formulas under the Relational Algebra. We investigate the\ncomputational complexity of querying text by aggregate functions, such as sum,\naverage, and quantile, on top of regular document spanners. To this end, we\nformally define aggregate functions over regular document spanners and analyze\nthe computational complexity of exact and approximate computation. More\nprecisely, we show that in a restricted case, all studied aggregate functions\ncan be computed in polynomial time. In general, however, even though exact\ncomputation is intractable, some aggregates can still be approximated with\nfully polynomial-time randomized approximation schemes (FPRAS).<\/jats:p>","DOI":"10.46298\/lmcs-19(3:12)2023","type":"journal-article","created":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T07:55:19Z","timestamp":1691567719000},"source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of Aggregates over Extractions by Regular Expressions"],"prefix":"10.46298","volume":"Volume 19, Issue 3","author":[{"given":"Johannes","family":"Doleschal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benny","family":"Kimelfeld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wim","family":"Martens","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25203","published-online":{"date-parts":[[2023,8,9]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/11712\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/11712\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T07:55:21Z","timestamp":1691567721000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/8623"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,9]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-19(3:12)2023","relation":{"has-preprint":[{"id-type":"arxiv","id":"2002.08828v4","asserted-by":"subject"},{"id-type":"arxiv","id":"2002.08828v3","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2002.08828","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2002.08828","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,9]]},"article-number":"8623"}}