Tractable Combinations of Temporal CSPs

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

Abstract

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(T 1 ∪ T 2) where T 1 and T 2 are theories with disjoint finite relational signatures. We prove that if T 1 and T 2 are the theories of temporal structures, i.e., structures where all relations have a first-order definition in (Q; <), then CSP(T 1 ∪ T 2) 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; <).

Details

OriginalspracheEnglisch
Aufsatznummer2
Seiten (von - bis)11:1-11:33
FachzeitschriftLogical Methods in Computer Science
Jahrgang18
Ausgabenummer2
PublikationsstatusVeröffentlicht - 2022
Peer-Review-StatusJa

Externe IDs

ORCID /0000-0001-8228-3611/work/174429272
Scopus 85133430854