A dichotomy for first-order reducts of unary structures
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
Many natural decision problems can be formulated as constraint satisfaction problems for reducts A of finitely bounded homogeneous structures. This class of problems is a large generalisation of the class of CSPs over finite domains. Our first result is a general polynomial-time reduction from such infinite-domain CSPs to finite-domain CSPs. We use this reduction to obtain new powerful polynomial-time tractability conditions that can be expressed in terms of the topological polymorphism clone of A. Moreover, we study the subclass C of CSPs for structures A that are reducts of a structure with a unary language. Also this class C properly extends the class of all finite-domain CSPs. We apply our new tractability conditions to prove the general tractability conjecture of Bodirsky and Pinsker for reducts of finitely bounded homogeneous structures for the class C.
|Fachzeitschrift||Logical methods in computer science|
|Publikationsstatus||Veröffentlicht - 22 Mai 2018|