Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction

DOI10.1145/2933575.2934515MaRDI QIDQ4635923zbMATH OpenOpenAlexFDO

Authors Manuel Bodirsky, Antoine Mottet

Publication date 23 April 2018

Published in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

abstract tractability conditionscanonical functionsconstraint satisfaction problems

Mathematics Subject Classification ID

Basic properties of first-order languages and structures (03C07) Models with special properties (saturated, rigid, etc.) (03C50) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A dichotomy for first-order reducts of unary structures
• Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
• The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems
• Asking the Metaquestions in Constraint Tractability
• The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems

Cited in

(19)

• Using model theory to find decidable and tractable description logics with concrete domains
• Description logics with concrete domains and general concept inclusions revisited
• A dichotomy for first-order reducts of unary structures
• A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
• Constraint satisfaction problems over numeric domains
• Small Promise CSPs that reduce to large CSPs
• Canonical functions: a proof via topological dynamics
• Constraint satisfaction problems for reducts of homogeneous graphs
• The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
• Non-finite axiomatisability results via reductions: CSP parallel composition and CCS restriction
• On the descriptive complexity of temporal constraint satisfaction problems
• Smooth approximations and CSPs over finitely bounded homogeneous structures
• Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
• An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
• Homogeneity and homogenizability: hard problems for the logic SNP
• An order out of nowhere: a new algorithm for infinite-domain CSPs
• Smooth approximations: an algebraic approach to CSPs over finitely bounded homogeneous structures
• Generalized completion problems with forbidden tournaments
• Three fundamental questions in modern infinite-domain constraint satisfaction

This page was built for publication: Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction

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