A logic for document spanners

DOI10.1007/S00224-018-9874-1MaRDI QIDQ2322723zbMATH OpenOpenAlexWikidataFDO

Authors Dominik D. Freydenberger

Publication date 5 September 2019

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-018-9874-1

zbMATH Keywords

CRPQs with string equalitydescriptional complexitydocument spannersinformation extractionword equationsxregex

Mathematics Subject Classification ID

Logic in computer science (03B70) Database theory (68P15) Information storage and retrieval of data (68P20) Formal languages and automata (68Q45)

Recommendations

• A logic for document spanners
• Document spanners: from expressive power to decision problems
• Document Spanners: From Expressive Power to Decision Problems.
• Document spanners: a formal approach to information extraction
• Monadic Datalog and the expressive power of languages for web information extraction

Cites work

• A logic for document spanners
• A note on undecidable properties of formal languages
• An Analysis and a Reproof of Hmelevskii’s Theorem
• Bounded Regular Sets
• Characterising REGEX languages by regular languages equipped with factor-referencing
• Concatenation as a basis for arithmetic
• Deterministic regular expressions with back-references
• Document spanners: a formal approach to information extraction
• Document spanners: from expressive power to decision problems
• Expressiveness and static analysis of extended conjunctive regular path queries
• Extended regular expressions: succinctness and decidability
• From finite automata to regular expressions and back -- a summary on descriptional complexity
• Frontiers of tractability for typechecking simple XML transformations
• Generalized factorizations of words and their algorithmic properties
• Graph logics with rational relations: the role of word combinatorics
• Hierarchies of complete problems
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1339964 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• Intersection and union of regular languages and state complexity
• Introduction to algorithms.
• Language operations with regular expressions of polynomial size
• More than 1700 years of word equations
• On Extended Regular Expressions
• Patterns with bounded treewidth
• Solution sets for equations over free groups are EDT0L languages
• The complexity of satisfiability problems
• The expressibility of languages and relations by word equations
• The non-parametrizability of the word equation \(xyz=zvx\): a short proof
• Two-variable word equations

Cited in

(27)

• Document spanners: from expressive power to decision problems
• Word equations in the context of string solving
• Document spanners: a formal approach to information extraction
• A logic for document spanners
• Weight annotation in information extraction
• Recursive Programs for Document Spanners
• Document Spanners: From Expressive Power to Decision Problems.
• scientific article; zbMATH DE number 7650989 (Why is no real title available?)
• Enumerating grammar-based extractions
• Languages generated by conjunctive query fragments of FC[REG]
• Matching patterns with variables under edit distance
• The Complexity of Aggregates over Extractions by Regular Expressions
• 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
• Languages generated by conjunctive query fragments of FC[REG]
• On the structure of solution sets to regular word equations
• A general information extraction framework based on formal languages
• Refl-spanners: a purely regular approach to non-regular core spanners
• A purely regular approach to non-regular core spanners
• Grammars for document spanners
• The complexity of aggregates over extractions by regular expressions
• The theory of concatenation over finite models
• A framework for extraction and transformation of documents
• FC-Datalog as a framework for efficient string querying
• The equivalence problem of E-pattern languages with length constraints is undecidable
• The equivalence problem of E-pattern languages with regular constraints is undecidable

This page was built for publication: A logic for document spanners

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