论文标题
颞csps的可处理组合
Tractable Combinations of Temporal CSPs
论文作者
论文摘要
一阶理论t的约束满意度问题（CSP）是计算问题，即在某些T的模型中确定给定的原子公式的结合是否可以满足。我们研究了CSP $（T_1 \ CUP T_2）$的计算复杂性，其中$ T_1 $和$ T_2 $与分离的相关签名是$ t_1 $和$ t_2 $。我们证明，如果$ t_1 $和$ t_2 $是时间结构的理论，即所有关系在$（q; <）$中均具有一阶定义的结构，则CSP $（T_1 \ cup t_2）$在p或np-complete中。为此，我们证明了关于包含aut $（q; <）$的域$ q $上本地关闭克隆晶格的结构的纯粹代数声明。
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 \cup 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 \cup 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;<)$.
