Document spanners: from expressive power to decision problems

DOI10.1007/s00224-017-9770-0zbMath1392.68167OpenAlexW2616567161WikidataQ59528982 ScholiaQ59528982MaRDI QIDQ1650917

Mario Holldack, Dominik D. Freydenberger

Publication date: 16 July 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-017-9770-0

zbMATH Keywords

decision problemsregular expressionspatternsword equationsdescriptional complexityinformation extractiondocument spannersxregex

Mathematics Subject Classification ID

Database theory (68P15) Formal languages and automata (68Q45) Information storage and retrieval of data (68P20)

Related Items

Enumerating grammar-based extractions, Languages generated by conjunctive query fragments of FC[REG], Matching patterns with variables under edit distance, Deterministic regular expressions with back-references, A logic for document spanners

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extended regular expressions: succinctness and decidability
• Expressiveness and static analysis of extended conjunctive regular path queries
• Patterns with bounded treewidth
• On Goedel speed-up and succinctness of language representations
• Bad news on decision problems for patterns
• Finding patterns common to a set of strings
• On the equivalence problem for E-pattern languages
• Decision problems for patterns
• Inclusion problems for patterns with a bounded number of variables
• Pattern matching with variables: a multivariate complexity analysis
• Parametrized complexity theory.
• Theory of computation.
• Semigroups, Presburger formulas, and languages
• Document Spanners
• The expressibility of languages and relations by word equations
• Pattern languages with and without erasing
• Declarative Cleaning of Inconsistencies in Information Extraction
• Document Spanners: From Expressive Power to Decision Problems.
• On Context-Free Languages
• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
• THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS