A logic for document spanners

DOI10.1007/s00224-018-9874-1zbMath1430.68081OpenAlexW2890631112WikidataQ129264752 ScholiaQ129264752MaRDI QIDQ2322723

Dominik D. Freydenberger

Publication date: 5 September 2019

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

Full work available at URL: https://doi.org/10.1007/s00224-018-9874-1

zbMATH Keywords

word equationsdescriptional complexityinformation extractiondocument spannersxregexCRPQs with string equality

Mathematics Subject Classification ID

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

Related Items (6)

Word equations in the context of string solving ⋮ 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 ⋮ Unnamed Item

Cites Work

• Extended regular expressions: succinctness and decidability
• Expressiveness and static analysis of extended conjunctive regular path queries
• Patterns with bounded treewidth
• Frontiers of tractability for typechecking simple XML transformations
• Intersection and union of regular languages and state complexity
• Hierarchies of complete problems
• Generalized factorizations of words and their algorithmic properties
• Document spanners: from expressive power to decision problems
• Language operations with regular expressions of polynomial size
• The non-parametrizability of the word equation \(xyz=zvx\): a short proof
• Characterising REGEX languages by regular languages equipped with factor-referencing
• Two-variable word equations
• Document Spanners
• From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity
• More Than 1700 Years of Word Equations
• Solution Sets for Equations over Free Groups are EDT0L Languages
• An Analysis and a Reproof of Hmelevskii’s Theorem
• On Extended Regular Expressions
• The expressibility of languages and relations by word equations
• Graph Logics with Rational Relations
• The complexity of satisfiability problems
• Bounded Regular Sets
• A note on undecidable properties of formal languages
• Concatenation as a basis for arithmetic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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