Enumeration for FO Queries over Nowhere Dense Graphs

DOI10.1145/3517035MaRDI QIDQ5889796zbMATH OpenOpenAlexFDO

Authors Nicole Schweikardt, Luc Segoufin, Alexandre Vigny

Publication date 27 April 2023

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3517035

zbMATH Keywords

constant-delay enumerationquery evaluationsparse graphs

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Constant delay enumeration for FO queries over databases with local bounded expansion
• First-order queries on classes of structures with bounded expansion
• Enumerating answers to first-order queries over databases of low degree
• Nowhere dense classes of graphs

Cites work

• Answering FO+MOD queries under updates on bounded degree databases
• Answering UCQs under updates and in the presence of integrity constraints
• Constant delay enumeration for FO queries over databases with local bounded expansion
• Constant-delay enumeration for nondeterministic document spanners
• Deciding first-order properties of locally tree-decomposable structures
• Domination problems in nowhere-dense classes of graphs
• Elements of finite model theory.
• Enumerating answers to first-order queries over databases of low degree
• Enumeration for FO Queries over Nowhere Dense Graphs
• Enumeration of monadic second-order queries on trees
• First order properties on nowhere dense structures
• First-order queries on structures of bounded degree are computable with constant delay
• Generalized model-checking over locally tree-decomposable classes
• scientific article; zbMATH DE number 5596834 (Why is no real title available?)
• scientific article; zbMATH DE number 3819693 (Why is no real title available?)
• scientific article; zbMATH DE number 1222098 (Why is no real title available?)
• scientific article; zbMATH DE number 1953123 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• MSO Queries on Tree Decomposable Structures Are Computable with Linear Delay
• On Acyclic Conjunctive Queries and Constant Delay Enumeration
• On nowhere dense graphs
• Storing a sparse table
• The complexity of first-order and monadic second-order logic revisited
• The succinctness of first-order logic on linear orders

Cited in

(7)

• Enumerating answers to first-order queries over databases of low degree
• First-order queries on classes of structures with bounded expansion
• Enumeration for FO Queries over Nowhere Dense Graphs
• Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries
• Ranked enumeration for MSO on trees via knowledge compilation
• Constant-delay enumeration for SLP-compressed documents
• FO-query enumeration over SLP-compressed structures of bounded degree

This page was built for publication: Enumeration for FO Queries over Nowhere Dense Graphs

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