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