First-order queries on structures of bounded degree are computable with constant delay

DOI10.1145/1276920.1276923zbMath1367.68086arXivcs/0507020OpenAlexW2030076354MaRDI QIDQ5277786

Etienne Grandjean, Arnaud Durand

Publication date: 12 July 2017

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0507020

zbMATH Keywords

computational complexityfirst-order logicenumeration problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Logic in computer science (03B70) Specification and verification (program logics, model checking, etc.) (68Q60) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantifier elimination, model completeness, and related topics (03C10)

Related Items (18)

Enumeration for FO Queries over Nowhere Dense Graphs ⋮ A logical approach to locality in pictures languages ⋮ Tree inclusions in windows and slices ⋮ Unnamed Item ⋮ On enumerating monomials and other combinatorial structures by polynomial interpolation ⋮ Faster Property Testers in a Variation of the Bounded Degree Model ⋮ Efficient First-Order Model-Checking Using Short Labels ⋮ Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries ⋮ Compact labelings for efficient first-order model-checking ⋮ An optimal construction of Hanf sentences ⋮ Unnamed Item ⋮ Computing thejth solution of a first-order query ⋮ Linear delay enumeration and monadic second-order logic ⋮ A complexity theory for hard enumeration problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Structural tractability of enumerating CSP solutions

This page was built for publication: First-order queries on structures of bounded degree are computable with constant delay