Tractable Combinations of Temporal CSPs
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
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
Originalsprache | Englisch |
---|---|
Aufsatznummer | 2 |
Seiten (von - bis) | 11:1-11:33 |
Fachzeitschrift | Logical Methods in Computer Science |
Jahrgang | 18 |
Ausgabenummer | 2 |
Publikationsstatus | Veröffentlicht - 2022 |
Peer-Review-Status | Ja |
Externe IDs
ORCID | /0000-0001-8228-3611/work/174429272 |
---|---|
Scopus | 85133430854 |