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

DOI10.1145/2933575.2934515zbMath1401.68109OpenAlexW2296309901MaRDI QIDQ4635923

Antoine Mottet, Manuel Bodirsky

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

constraint satisfaction problemscanonical functionsabstract tractability conditions

Mathematics Subject Classification ID

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

Related Items (7)

Constraint Satisfaction Problems over Numeric Domains ⋮ A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP ⋮ Constraint Satisfaction Problems for Reducts of Homogeneous Graphs ⋮ Using model theory to find decidable and tractable description logics with concrete domains ⋮ Unnamed Item ⋮ Description logics with concrete domains and general concept inclusions revisited ⋮ The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom

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