The tractability frontier of graph-like first-order query sets

DOI10.1145/3073409MaRDI QIDQ4640277zbMATH OpenOpenAlexFDO

Authors Hubie Chen

Publication date 17 May 2018

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

Full work available at URL https://eprints.bbk.ac.uk/id/eprint/21933/1/graphlike-post.pdf

zbMATH Keywords

dichotomy theoremfirst-order model checkingparameterized complexity

Mathematics Subject Classification ID

Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• The tractability frontier of graph-like first-order query sets
• On the complexity of existential positive queries
• First-Order Model Checking Problems Parameterized by the Model
• Fixed-parameter tractability, definability, and model-checking
• On the complexity of the model checking problem

Cited in

(6)

• First-order queries on databases embedded in an infinite structure
• \(N\)-dimensional versus \((N-1)\)-dimensional connectivity testing of first-order queries to semi-algebraic sets
• The tractability frontier of graph-like first-order query sets
• First-order queries on structures of bounded degree are computable with constant delay
• Optimally rewriting formulas and database queries: a confluence of term rewriting, structural decomposition, and complexity
• Optimally rewriting formulas and database queries: a confluence of term rewriting, structural decomposition, and complexity

This page was built for publication: The tractability frontier of graph-like first-order query sets

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