Manuel Bodirsky ; Antoine Mottet - A Dichotomy for First-Order Reducts of Unary Structures

lmcs:3264 - Logical Methods in Computer Science, May 22, 2018, Volume 14, Issue 2 -
A Dichotomy for First-Order Reducts of Unary Structures

Authors: Manuel Bodirsky ; Antoine Mottet

    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 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 $\mathbb{A}$. Moreover, we study the subclass $\mathcal{C}$ of CSPs for structures $\mathbb{A}$ that are reducts of a structure with a unary language. Also this class $\mathcal{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 $\mathcal{C}$.

    Volume: Volume 14, Issue 2
    Published on: May 22, 2018
    Accepted on: April 22, 2018
    Submitted on: April 12, 2017
    Keywords: Mathematics - Logic,Computer Science - Computational Complexity,Computer Science - Logic in Computer Science
      Source : OpenAIRE Graph
    • Homogeneous Structures, Constraint Satisfaction Problems, and Topological Clones; Funder: European Commission; Code: 681988
    • Constraint Satisfaction Problems: Algorithms and Complexity; Funder: European Commission; Code: 257039

    Linked publications - datasets - softwares

    Source : ScholeXplorer IsCitedBy ARXIV 2102.07531
    Source : ScholeXplorer IsCitedBy DOI 10.4230/lipics.icalp.2021.138
    Source : ScholeXplorer IsCitedBy DOI 10.48550/arxiv.2102.07531
    Source : ScholeXplorer IsCitedBy HANDLE 11420/12070
    • 10.48550/arxiv.2102.07531
    • 10.4230/lipics.icalp.2021.138
    • 2102.07531
    • 11420/12070
    Smooth Approximations and Relational Width Collapses
    Mottet, Antoine ; Nagy, Tomáš ; Pinsker, Michael ; Wrona, Michał ;

    Consultation statistics

    This page has been seen 900 times.
    This article's PDF has been downloaded 289 times.