A dichotomy for first-order reducts of unary structures

Research output: Contribution to journalResearch articleContributedpeer-review

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 languageEnglish
Article number13
JournalLogical methods in computer science
Volume14
Issue number2
Publication statusPublished - 22 May 2018
Peer-reviewedYes

External IDs

ORCID /0000-0001-8228-3611/work/142241080

Keywords