A dichotomy for first-order reducts of unary structures

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

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

OriginalspracheEnglisch
Aufsatznummer13
FachzeitschriftLogical methods in computer science
Jahrgang14
Ausgabenummer2
PublikationsstatusVeröffentlicht - 22 Mai 2018
Peer-Review-StatusJa

Externe IDs

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

Schlagworte