A dichotomy for first-order reducts of unary structures
Research output: Contribution to journal › Research article › Contributed › peer-review
Contributors
Abstract
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.
Details
Original language | English |
---|---|
Article number | 13 |
Journal | Logical methods in computer science |
Volume | 14 |
Issue number | 2 |
Publication status | Published - 22 May 2018 |
Peer-reviewed | Yes |
External IDs
ORCID | /0000-0001-8228-3611/work/142241080 |
---|