The Tractability Frontier of Graph-Like First-Order Query Sets

DOI10.1145/3073409zbMATH Open1425.68253OpenAlexW2747797425MaRDI QIDQ4640277

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

parameterized complexitydichotomy theoremfirst-order model checking

Mathematics Subject Classification ID

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

Related Items (2)

First-order queries on structures of bounded degree are computable with constant delay ⋮ \(N\)-dimensional versus \((N-1)\)-dimensional connectivity testing of first-order queries to semi-algebraic sets

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)