The Complexity of Aggregates over Extractions by Regular Expressions

DOI10.46298/LMCS-19(3:12)2023MaRDI QIDQ6135782zbMATH OpenFDO

Authors Johannes Doleschal, Benny Kimelfeld, Wim Martens

Publication date 26 August 2023

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2002.08828

zbMATH Keywords

aggregationweighted automatainformation extractiondocument spannersprovenance semiringsannotated databases

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Abstract: 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).

Cites work

• scientific article; zbMATH DE number 910913 (Why is no real title available?)
• scientific article; zbMATH DE number 7561482 (Why is no real title available?)
• scientific article; zbMATH DE number 7650989 (Why is no real title available?)
• #NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes
• A logic for document spanners
• An introduction to conditional random fields
• Approximately counting approximately-shortest paths in directed acyclic graphs
• BPP and the polynomial hierarchy
• Document spanners: a formal approach to information extraction
• Handbook of weighted automata
• On Unapproximable Versions of $NP$-Complete Problems
• Probabilistic quantifiers and games
• Recursive Programs for Document Spanners
• SVM Based Learning System for Information Extraction
• The Complexity of Planar Counting Problems
• The complexity of optimization problems
• The relative complexity of approximate counting problems
• Weight Annotation in Information Extraction
• ``Product partition and related problems of scheduling and systems reliability: computational complexity and approximation

This page was built for publication: The Complexity of Aggregates over Extractions by Regular Expressions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6135782)