Document spanners: from expressive power to decision problems

DOI10.1007/S00224-017-9770-0MaRDI QIDQ1650917zbMATH OpenOpenAlexWikidataFDO

Authors Dominik D. Freydenberger, Mario Holldack

Publication date 16 July 2018

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

descriptional complexityword equationspatternsregular expressionsdecision problemsinformation extractiondocument spannersxregex

Mathematics Subject Classification ID

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

Recommendations

• Document Spanners: From Expressive Power to Decision Problems.
• A logic for document spanners
• Document spanners: a formal approach to information extraction
• A logic for document spanners
• Cut and paste

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
• A logic for document spanners
• Bad news on decision problems for patterns
• Decision problems for patterns
• Declarative cleaning of inconsistencies in information extraction
• Descriptional complexity -- an introductory survey
• Document Spanners: From Expressive Power to Decision Problems.
• Document spanners: a formal approach to information extraction
• Expressiveness and static analysis of extended conjunctive regular path queries
• Extended regular expressions: succinctness and decidability
• Finding patterns common to a set of strings
• Inclusion problems for patterns with a bounded number of variables
• On Context-Free Languages
• On Goedel speed-up and succinctness of language representations
• On the equivalence problem for E-pattern languages
• On the parameterised complexity of string morphism problems
• Parametrized complexity theory.
• Pattern languages with and without erasing
• Pattern matching with variables: a multivariate complexity analysis
• Pattern matching with variables: fast algorithms and new hardness results
• Patterns with bounded treewidth
• Semigroups, Presburger formulas, and languages
• THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
• The expressibility of languages and relations by word equations
• Theory of computation.

Cited in

(14)

• Matching patterns with variables under edit distance
• Enumerating grammar-based extractions
• Document spanners: a formal approach to information extraction
• scientific article; zbMATH DE number 7650989 (Why is no real title available?)
• Document Spanners: From Expressive Power to Decision Problems.
• A closer look at the expressive power of logics based on word equations
• On the structure of solution-sets to regular word equations
• Matching patterns with variables under Simon's congruence
• A logic for document spanners
• Recursive Programs for Document Spanners
• A logic for document spanners
• Languages generated by conjunctive query fragments of FC[REG]
• Languages generated by conjunctive query fragments of FC[REG]
• Deterministic regular expressions with back-references

This page was built for publication: Document spanners: from expressive power to decision problems

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