A Dichotomy for First-Order Reducts of Unary Structures

Many natural decision problems can be formulated as constraint satisfaction problems for reducts $\mathbb{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...

Full description

Bibliographic Details
Main Authors: Manuel Bodirsky, Antoine Mottet
Format: Article
Language:English
Published: Logical Methods in Computer Science e.V. 2018-05-01
Series:Logical Methods in Computer Science
Subjects:
Online Access:https://lmcs.episciences.org/3264/pdf