Languages generated by conjunctive query fragments of FC[REG]

DOI10.1007/978-3-031-33264-7_19MaRDI QIDQ6088950

Dominik D. Freydenberger, Sam M. Thompson

Publication date: 16 November 2023

Published in: Developments in Language Theory (Search for Journal in Brave)

zbMATH Keywords

decision problemsexpressive powerword equationsdescriptional complexityconjunctive queries

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extended regular expressions: succinctness and decidability
• On Goedel speed-up and succinctness of language representations
• Finding patterns common to a set of strings
• Document spanners: from expressive power to decision problems
• Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup
• Deterministic regular expressions with back-references
• A logic for document spanners
• The existential theory of equations with rational constraints in free groups is PSPACE-complete
• Characterising REGEX languages by regular languages equipped with factor-referencing
• Document Spanners
• Polynomial-Time Algorithms for Learning Typed Pattern Languages
• Inside the Class of REGEX Languages
• The expressibility of languages and relations by word equations
• The hardness of solving simple word equations
• THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS

This page was built for publication: Languages generated by conjunctive query fragments of FC[REG]