Loading [MathJax]/jax/output/HTML-CSS/jax.js

Manuel Bodirsky ; Johannes Greiner ; Jakub Rydval - Tractable Combinations of Temporal CSPs

lmcs:7013 - Logical Methods in Computer Science, May 25, 2022, Volume 18, Issue 2 - https://doi.org/10.46298/lmcs-18(2:11)2022
Tractable Combinations of Temporal CSPsArticle

Authors: Manuel Bodirsky ORCID; Johannes Greiner ; Jakub Rydval

    The constraint satisfaction problem (CSP) of a first-order theory T is the computational problem of deciding whether a given conjunction of atomic formulas is satisfiable in some model of T. We study the computational complexity of CSP(T1T2) where T1 and T2 are theories with disjoint finite relational signatures. We prove that if T1 and T2 are the theories of temporal structures, i.e., structures where all relations have a first-order definition in (Q;<), then CSP(T1T2) is in P or NP-complete. To this end we prove a purely algebraic statement about the structure of the lattice of locally closed clones over the domain Q that contain Aut(Q;<).


    Volume: Volume 18, Issue 2
    Published on: May 25, 2022
    Accepted on: March 1, 2022
    Submitted on: December 22, 2020
    Keywords: Mathematics - Logic,Computer Science - Computational Complexity,Computer Science - Logic in Computer Science,06A05, 68Q25, 08A70,F.4.1,F.2.2,G.2.1
    Funding:
      Source : OpenAIRE Graph
    • Homogeneous Structures, Constraint Satisfaction Problems, and Topological Clones; Funder: European Commission; Code: 681988

    Consultation statistics

    This page has been seen 2414 times.
    This article's PDF has been downloaded 644 times.