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

DOI10.1145/2603088.2603119MaRDI QIDQ4635615zbMATH OpenOpenAlexFDO

Authors Hubie Chen

Publication date 23 April 2018

Published in Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (Search for Journal in Brave)

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

zbMATH Keywords

first-order queriesparameterized complexityquery evaluationtreewidth

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Database theory (68P15) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Abstract: We study first-order model checking, by which we refer to the problem of deciding whether or not a given first-order sentence is satisfied by a given finite structure. In particular, we aim to understand on which sets of sentences this problem is tractable, in the sense of parameterized complexity theory. To this end, we define the notion of a graph-like sentence set, which definition is inspired by previous work on first-order model checking wherein the permitted connectives and quantifiers were restricted. Our main theorem is the complete tractability classification of such graph-like sentence sets, which is (to our knowledge) the first complexity classification theorem concerning a class of sentences that has no restriction on the connectives and quantifiers. To present and prove our classification, we introduce and develop a novel complexity-theoretic framework which is built on parameterized complexity and includes new notions of reduction.

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

(8)

• First-order queries on databases embedded in an infinite structure
• Characterizing tractability of simple well-designed pattern trees with projection
• How many variables are needed to express an existential positive query?
• \(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
• Quantified Constraints in Twenty Seventeen
• scientific article; zbMATH DE number 7561480 (Why is no real title available?)
• First-order queries on structures of bounded degree are computable with constant delay

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 Q4635615)