The Complexity of Aggregates over Extractions by Regular Expressions

DOI10.46298/lmcs-19(3:12)2023arXiv2002.08828MaRDI QIDQ6135782

Johannes Doleschal, Benny Kimelfeld, Wim Martens

Publication date: 26 August 2023

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

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximately counting approximately-shortest paths in directed acyclic graphs
• Handbook of weighted automata
• ``Product partition and related problems of scheduling and systems reliability: computational complexity and approximation
• BPP and the polynomial hierarchy
• The complexity of optimization problems
• Probabilistic quantifiers and games
• The relative complexity of approximate counting problems
• A logic for document spanners
• Document Spanners
• An Introduction to Conditional Random Fields
• The Complexity of Planar Counting Problems
• #NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes
• Recursive Programs for Document Spanners
• SVM Based Learning System for Information Extraction
• On Unapproximable Versions of $NP$-Complete Problems
• Weight Annotation in Information Extraction

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