18211 LABEL:LastPageDec. 22, 2020May 25, 2022

# Tractable Combinations of Temporal CSPs

Manuel Bodirskya  ,  Johannes Greinera  Institut für Algebra, Technische
Universität Dresden, 01062 Dresden, Germany<EMAIL_ADDRESS><EMAIL_ADDRESS>and  Jakub Rydvalb  Institut für
Theoretische Informatik, Technische Universität Dresden, 01062 Dresden,
Germany<EMAIL_ADDRESS>
###### 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 $\mathrm{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 $(\mathbb{Q};<)$, then
$\mathrm{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 ${\mathbb{Q}}$ that contain
$\operatorname{Aut}(\mathbb{Q};<)$.

All authors have received funding from the European Research Council (ERC
Grant Agreement no. 681988, CSP-Infinity) and the DFG Graduiertenkolleg 1763
(QuantLA)

##  1\. Introduction

Deciding the satisfiability of formulas with respect to a given theory or
structure is one of the fundamental problems in theoretical computer science.
One large class of problems of this kind are _Constraint Satisfaction
Problems_ (CSPs). For a finite relational signature $\tau$, the CSP of a
$\tau$-theory $T$, written $\mathrm{CSP}(T)$, is the computational problem of
deciding whether a given finite set $S$ of atomic $\tau$-formulas is
satisfiable in some model of $T$. A general goal is to identify theories $T$
such that $\mathrm{CSP}(T)$ can be solved in polynomial time.

Many theories that are relevant in program verification and automated
deduction are of the form $T_{1}\cup T_{2}$ where the signatures of $T_{1}$
and $T_{2}$ are disjoint; satisfiability problems of the form
$\mathrm{CSP}(T_{1}\cup T_{2})$ are also studied in the field of
Satisfiability Modulo Theories (SMT). If we already have a decision procedure
for $\mathrm{CSP}(T_{1})$ and for $\mathrm{CSP}(T_{2})$, then, under certain
conditions, we can use these decision procedures to construct a decision
procedure for $\mathrm{CSP}(T_{1}\cup T_{2})$ in a generic way. Most results
in the area of combinations of decision procedures concern decidability,
rather than polynomial-time decidability; see for example [Ghi04, TR03,
BGN+06, Rin96]. We are particularly interested in polynomial-time decidability
and the borderline to NP-hardness. The seminal result in this direction is due
to Greg Nelson and Derek C. Oppen, who provided a criterion assuring that
satisfiability of conjunctions of atomic and negated atomic formulas can be
decided in polynomial time [NO79, Opp80]. The work of Nelson and Oppen has
been further developed later on (see for example [BS01]) and their algorithm
has been implemented in many SMT solvers (see for example [KG07]). While their
result directly gives sufficient conditions for polynomial-time tractability
of $\mathrm{CSP}(T_{1}\cup T_{2})$, one of their conditions called ‘convexity’
can be weakened to ‘independence of $\neq$’ (see [BJR02]) without changing
their proof, if we only consider conjunctions of atomic formulas as input (see
Section 2.3 and Section 3 for details). Interestingly, the weakened criterion
also turns out to be remarkably tight; Schulz [Sch00] as well as Bodirsky and
Greiner [BG20] proved that in many cases not covered by the weaker criterion,
$\mathrm{CSP}(T_{1}\cup T_{2})$ is NP-hard even though both
$\mathrm{CSP}(T_{1})$ and $\mathrm{CSP}(T_{2})$ can be solved in polynomial
time. However, there are examples of theories $T_{1}$ and $T_{2}$ that do not
satisfy the weakened conditions of Nelson and Oppen, but
$\mathrm{CSP}(T_{1}\cup T_{2})$ can be solved in polynomial time nevertheless
(see [BG21]). Unfortunately, there is still no general theory of polynomial-
time tractability for combinations of theories.

An important subclass of constraint satisfaction problems are _temporal CSPs_
, which are CSPs for the theories of structures of the form
$({\mathbb{Q}};R_{1},\dots,R_{n})$ where $R_{1},\dots,R_{n}$ are relations
defined by quantifier-free first-order formulas over $({\mathbb{Q}};<)$; we
refer to such structures as _temporal structures_. A well-known example of
such a structure is $({\mathbb{Q}};\operatorname{Betw})$ where
$\operatorname{Betw}:=\\{(a,b,c)\mid a<b<c\vee c<b<a\\}$. The CSP for the
theory of this structure is the so-called _Betweenness problem_ and is NP-
complete [Opa79]. Other well-known temporal CSPs are the Cyclic Ordering
problem [GM77], Ord-Horn constraints [NB95], the network satisfaction problem
for the point algebra [VKvB89], and scheduling with and/or precedence
constraints [MSS04]. It has been shown that every temporal CSP is in P or NP-
complete [BK09]. Temporal CSPs are of particular importance for the study of
polynomial-time procedures for combinations of theories, because many of the
polynomial-time tractable cases do _not_ satisfy the weakened conditions of
Nelson and Oppen because $\neq$ is not independent in these cases. This is
unlike several other classifications for CSPs where all the polynomial-time
tractable cases do satisfy the weakened conditions of Nelson and Oppen [BK08,
BMPP19, BW12, BP15, BH12, KP18, BMM21] and hence CSPs for combinations of such
theories can be solved in polynomial time. Some results about the complexity
of CSPs for combinations of theories of temporal structures were obtained in
[BG20], but they were restricted to temporal structures that contain the
relations $<$ and $\neq$.

###  1.1. Contributions

Our main result is a complexity dichotomy for all problems of the form
$\mathrm{CSP}(T_{1}\cup T_{2})$ where $T_{1}$ and $T_{2}$ are first-order
theories of temporal structures with disjoint finite signatures. In order to
phrase our results in this section, we need the concepts of _primitive
positive definability_ and _polymorphisms_ , which are of fundamental
importance in universal algebra and will be recalled in Section 2.2. The main
result is the following:

######  Theorem 1.

Let $T_{1}$ and $T_{2}$ be the theories of temporal structures
$\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ with disjoint finite signatures.
Then $\mathrm{CSP}(T_{1}\cup T_{2})$ is polynomial-time tractable if

  1. (1)

for both $i\in\\{1,2\\}$, the structure $\mathfrak{A}_{i}$ has a binary
injective polymorphism and $\mathrm{CSP}(\mathfrak{A}_{i})$ is in P, or

  2. (2)

for both $i\in\\{1,2\\}$, the structure $\mathfrak{A}_{i}$ has a constant
polymorphism, or

  3. (3)

there is a temporal structure $\mathfrak{B}$ such that
$\mathrm{CSP}(\mathfrak{B})=\mathrm{CSP}(T_{1}\cup T_{2})$, and
$\mathrm{CSP}(\mathfrak{B})$ is in P (this happens if, for some
$i\in\\{1,2\\}$, all permutations are polymorphisms of $\mathfrak{A}_{i}$).

Otherwise, $\mathrm{CSP}(T_{1}\cup T_{2})$ is NP-complete.

The technique we use to prove NP-hardness in Theorem 1 is based on the notion
of cross prevention introduced in [BG20].

A $\tau$-structure $\mathfrak{B}$ _can prevent crosses_ if there exists a
primitive positive $\tau$-formula $\phi(x,y,u,v)$ such that

  1. (1)

$\phi(x,y,u,v)\and x=y\and u\neq v\and x\neq u\and x\neq v$ is satisfiable in
$\mathfrak{B}$,

  2. (2)

$\phi(x,y,u,v)\and x\neq y\and u=v\and x\neq u\and y\neq u$ is satisfiable in
$\mathfrak{B}$, and

  3. (3)

$\phi(x,y,u,v)\and x=y\and u=v$ is not satisfiable in $\mathfrak{B}$.

Any such formula $\phi$ will be referred to as a _cross prevention formula_ of
$\mathfrak{B}$.

An example of a structure that can prevent crosses is $(\mathbb{Q};<)$; a
cross prevention formula is $u<x\wedge y<v$. Another example is
$(\mathbb{N};E,N)$ where $E$ is an equivalence relation where all classes have
exactly two elements and $N$ is the complement of $E$. In this structure
$E(x,u)\and N(y,v)$ is a cross prevention formula.

Our next contribution, Theorem 2, is the complexity result underlying the
hardness proof for Theorem 1 and is not limited to temporal structures. It
uses the relation $R^{\operatorname{mix}}$, which is of fundamental importance
to this article and defined as follows:

$\displaystyle R^{\operatorname{mix}}\coloneqq\;$
$\displaystyle\big{\\{}(a_{1},a_{2},a_{3})\in\mathbb{Q}^{3}\mid(a_{1}=a_{2})\vee(a_{3}<a_{1}\wedge
a_{3}<a_{2})\big{\\}}$ $\displaystyle=\;$
$\displaystyle\big{\\{}(a_{1},a_{2},a_{3})\in{\mathbb{Q}}^{n}\mid
a_{3}\geq\min(a_{1},a_{2})\Rightarrow a_{1}=a_{2}\big{\\}}.$

######  Theorem 2.

Let $\mathfrak{A}$ be a countably infinite $\omega$-categorical structure with
finite relational signature and without algebraicity. If $\mathfrak{A}$ can
prevent crosses, then
$\mathrm{CSP}(\operatorname{Th}({\mathbb{Q}};<,R^{\operatorname{mix}})\cup\operatorname{Th}(\mathfrak{A}))$
is NP-hard.

Examples of $\omega$-categorical structures without algebraicity and with
cross prevention can be found in Section 6.

Our third contribution is the algebraic cornerstone of this article, which is
a result about the definability of $R^{\operatorname{mix}}$. If $R$ is a
temporal relation, then $-R$ denotes the _dual of $R$_, which is the temporal
relation $\\{(a_{1},\dots,a_{n})\in\mathbb{Q}^{n}\mid(-a_{1},\dots,-a_{n})\in
R\\}$. The _dual_ of an operation $f\colon{\mathbb{Q}}^{n}\to{\mathbb{Q}}$ is
defined by $(x_{1},\dots,x_{n})\mapsto-f(-x_{1},\dots,-x_{n})$. Hence, for any
temporal relation $R$ and any operation $f$ on $\mathbb{Q}$, the operation $f$
preserves $R$ if and only if the dual of $f$ preserves the dual of $R$. The
functions $\min,\min,\operatorname{mx}$ and ll will be explained in Section
2.5.

######  Theorem 3.

Let $\mathfrak{A}$ be a first-order expansion of $(\mathbb{Q};<)$ with a
finite relational signature such that $\min$, $\operatorname{mi}$,
$\operatorname{mx}$, ll or one of their duals is a polymorphism of
$\mathfrak{A}$. Then the following are equivalent:

  * •

$\mathfrak{A}$ does not have a binary injective polymorphism.

  * •

$R^{\operatorname{mix}}$ or its dual $-R^{\operatorname{mix}}$ has a primitive
positive definition in $\mathfrak{A}$.

Theorem 3 characterises the first-order expansions of $(\mathbb{Q};<)$ among
the polynomial-time tractable cases in the dichotomy of Bodirsky and Kára (see
Theorem 2.5.2) whose first-order theory does not satisfy the weakened
tractability conditions by Nelson and Oppen because $\neq$ is not independent
from their theory (see Section 2.3 for the definition).

###  1.2. Significance of the Result in Universal Algebra

Theorem 3 is of independent interest in universal algebra; for an introduction
to the universal-algebraic concepts that appear in this section we refer the
reader to Section 2.2. Theorem 3 can be seen as a result about locally closed
clones on a countably infinite domain $B$ that are _highly set-transitive_. A
permutation group $G$ on a set $B$ is said to be highly set-transitive if for
all finite subsets $S_{1}$ and $S_{2}$ of $B$ of equal size there exists a
permutation in $G$ that maps $S_{1}$ to $S_{2}$. An operation clone on a set
$B$ is said to be highly set-transitive if it contains a highly set-transitive
permutation group.

It can be shown that the highly set-transitive locally closed clones are
precisely the polymorphism clones of temporal structures (possibly with
infinitely many relations), up to a bijection between $B$ and $\mathbb{Q}$
[BK09]. These objects form a lattice: the meet of two clones is the
intersection of the clones and the join can be obtained as the polymorphism
clone of all relations preserved by both of the clones (see, e.g., Section 6.1
in [Bod21]). Similarly, as the lattice of clones over the set $\\{0,1\\}$
plays a fundamental role for studying finite algebras (it has been classified
by Post [Pos41]), the lattice of locally closed highly set-transitive clones
over $\mathbb{Q}$ is of fundamental importance for the study of locally closed
clones in general. This lattice is of size $2^{\omega}$ even if we restrict
our attention to closed clones that contain all permutations [BCP10]. However,
the lower parts of the lattice appears to be more structured and amenable to
classification. We pose the following question.

Are there only countably many locally closed highly set-transitive clones over
a fixed countably infinite set that do not contain a binary injective
operation?

Question 1.2 has a positive answer in the case that the clone contains all
permutations of the base set [BCP10]. Theorem 2.5.1 below shows that answering
Question 1.2 can be split into finitely many cases, depending on whether the
clone contains a constant operation, or whether it preserves one out of a
finite list of temporal relations. Theorem 3 shows that in case 1 of Theorem
2.5.2, we can even focus on clones that preserve the relation
$R^{\operatorname{mix}}$ or its dual.

###  1.3. Outline of the Article

We first recall some basic concepts from model theory in Section 2.1. Then,
the classical Nelson-Oppen conditions for obtaining polynomial-time decision
procedures for combined theories are presented in Section 2.3; a slight
generalisation of their results can be found in Section 3. We then define the
model-theoretic notion of a _generic combination_ of two structures with
disjoint relational signatures in Section 2.4, which plays a crucial role in
our proof. The reason is that we may apply universal algebra to study the
complexity of CSPs of structures but not of theories. Basic universal-
algebraic concepts are introduced in Section 2.2. Our results build on the
classification of the temporal CSPs that can be solved in polynomial time
[BK09], which we present along with other known facts about temporal
structures in Section 2.5.

The proof of Theorem 3 is organised as follows. The difficult direction is to
find a primitive positive definition of $R^{\operatorname{mix}}$ in
$\mathfrak{A}$ if $\mathfrak{A}$ is not preserved by a binary injective
polymorphism. If $\operatorname{Pol}(\mathfrak{A})$ contains
$\operatorname{mi}$, then the proof is easier if $\leq$ is primitively
positively definable in the structure $\mathfrak{A}$. If the relation $\leq$
is not primitively positively definable in $\mathfrak{A}$, then a certain
operation $\operatorname{mix}$ is a polymorphism of $\mathfrak{A}$. We discuss
$\operatorname{mix}$ in Section 4 and use results thereof in Section 5.1 to
show the primitive positive definability of $R^{\operatorname{mix}}$ in
$\mathfrak{A}$.

The case that $\operatorname{Pol}(\mathfrak{A})$ contains $\operatorname{mx}$
but not $\operatorname{mi}$ is treated in Section 5.2, and the case that
$\operatorname{Pol}(\mathfrak{A})$ contains $\min$ but neither
$\operatorname{mi}$ nor $\operatorname{mx}$ is treated in Section 5.3. All of
these partial results are put together in Section 5.4.

Finally, Section 6 uses our definability dichotomy theorem (Theorem 3) to
prove the complexity dichotomy for combinations of temporal CSPs.

##  2\. Preliminaries

We use the notation $[k]$ for the set
$\\!\left\\{1,\dots,k\right\\}\subseteq\mathbb{N}$.

###  2.1. Model Theory

A _relational signature_ is a set of relation symbols, each endowed with a
natural number, stating its arity. Let $\tau$ be relational signature. A
_$\tau$ -structure_ $\mathfrak{A}$ consists of a set $A$, the _domain_ of
$\mathfrak{A}$, and a relation $R\subseteq A^{k}$ for each $R\in\tau$ of arity
$k$. We use the notation $\mathfrak{A}=(A;R_{1},\dots,R_{n})$ for relational
structures with finite signature.

A $\tau$-formula is _atomic_ if it is of the form $x_{1}=x_{2}$, $\bot$ (the
logical “false”), or $R(x_{1},\dots,x_{n})$ for $R\in\tau$ of arity $n$ where
$x_{1},\dots,x_{n}$ are variables. A _literal_ is either an atomic formula or
a negated atomic formula. A $\tau$-formula is _primitive positive (pp)_ if it
is of the form $\exists
x_{k},x_{k+1},\dots,x_{\ell}\ldotp\phi(x_{1},\dots,x_{\ell})$ where $\phi$ is
a conjunction of atomic $\tau$-formulas and $k\geq 1$ is allowed to be larger
than $\ell$, in which case all variables are unquantified. A $\tau$-formula is
_existential positive_ if it is a disjunction of primitive positive formulas;
note that every first-order formula which does not contain negation or
universal quantification is equivalent to such a formula. A _$\tau$ -theory_
is a set of first-order $\tau$-sentences, i.e., $\tau$-formulas without free
variables. For a $\tau$-strucutre $\mathfrak{A}$ the _(first-order) theory of
$\mathfrak{A}$_, denoted by $\operatorname{Th}(\mathfrak{A})$, is the set of
all first-order $\tau$-sentences that hold in $\mathfrak{A}$. If $T$ is a
$\tau$-theory and $\mathfrak{A}$ a $\tau$-structure, then $\mathfrak{A}$ is a
_model_ for $T$, written $\mathfrak{A}\models T$, if all sentences in $T$ hold
in $\mathfrak{A}$. In particular
$\mathfrak{A}\models\operatorname{Th}(\mathfrak{A})$.

The CSP of a $\tau$-structure $\mathfrak{A}$, written
$\mathrm{CSP}(\mathfrak{A})$, is the computational problem of deciding, given
a conjunction of atomic $\tau$-formulas, whether or not the conjunction is
satisfiable in $\mathfrak{A}$. More generally, the CSP of a $\tau$-theory $T$,
written $\mathrm{CSP}(T)$, is the computational problem of deciding whether a
given conjunction of atomic $\tau$-formulas is satisfiable in _some_ model of
$T$. Note that $\mathrm{CSP}(\mathfrak{A})$ and
$\mathrm{CSP}(\operatorname{Th}(\mathfrak{A}))$ are the same problem. Let
$\mathfrak{A}$ be a relational $\tau$-structure and $\mathfrak{B}$ a
relational $\sigma$-structure with $\tau\subseteq\sigma$.

If $\mathfrak{A}$ is a $\tau$-structure and $\phi(x_{1},\dots,x_{n})$ is a
$\tau$-formula with free variables $x_{1},\dots,x_{n}$, then the _relation
defined by $\phi$_ is the relation $\\!\left\\{(a_{1},\dots,a_{n})\in
A^{n}\mid\mathfrak{A}\models\phi(a_{1},\dots,a_{n})\right\\}$. We say that a
relation is _primitively positively definable_ in $\mathfrak{A}$ if there is a
primitive positive formula that defines $R$ in $\mathfrak{A}$. First-order and
existential positive definability are defined analogously. Notice that a
definition of a relation $R$ via a formula $\phi$ in the above way also yields
a bijection between coordinates of tuples of $R$ and the free variables of
$\phi$. We will use this bijection implicitly whenever we say that $t\in R$
_satisfies_ a formula on the free variables of $\phi$.

If $\mathfrak{A}$ can be obtained from $\mathfrak{B}$ by deleting relations
from $\mathfrak{B}$, then $\mathfrak{A}$ is called a _reduct_ of
$\mathfrak{B}$, and $\mathfrak{B}$ is called an _expansion_ of $\mathfrak{A}$.
If the signature of $\mathfrak{A}$ equals $\tau$, then the reduct
$\mathfrak{A}$ of $\mathfrak{B}$ is also denoted by $\mathfrak{B}^{\tau}$. An
expansion $\mathfrak{B}$ of $\mathfrak{A}$ is called _first-order expansion_
if all relations in $\mathfrak{B}$ have a first-order definition in
$\mathfrak{A}$. The expansion of $\mathfrak{A}$ by a relation $R$ is denoted
by $(\mathfrak{A};R)$. As usual, $\operatorname{Aut}(\mathfrak{A})$ denotes
the set of all automorphisms of $\mathfrak{A}$, i.e., isomorphisms from
$\mathfrak{A}$ to $\mathfrak{A}$. For $k\in\mathbb{N}$ and $a\in A^{k}$, the
set
$\operatorname{Aut}(\mathfrak{A})a\coloneqq\\!\left\\{(\alpha(a_{1}),\dots,\alpha(a_{k}))\mid\alpha\in\operatorname{Aut}(\mathfrak{A})\right\\}$
is called the _orbit_ of $a$.

The theory of $(\mathbb{Q};<)$, or any first-order expansion thereof, has the
remarkable property of _$\omega$ -categoricity_, that is, it has only one
countable model up to isomorphism (see, e.g., [Hod97]). The class of
$\omega$-categorical relational structures can be characterised by the
following theorem.

[Engeler, Ryll-Nardzewski, Svenonius, see [Hod97], p. 171] Let $\mathfrak{A}$
be a countably infinite structure with countable signature. Then, the
following are equivalent:

  1. (1)

$\mathfrak{A}$ is $\omega$-categorical;

  2. (2)

for all $n\geq 1$ every orbit of $n$-tuples is first-order definable in
$\mathfrak{A}$;

  3. (3)

for all $n\geq 1$ there are only finitely many orbits of $n$-tuples.

###  2.2. Universal Algebra

A operation $f\colon A^{m}\rightarrow A$ _preserves_ a relation $R\subseteq
A^{n}$ if for all $t_{1},\dots,t_{m}\in R$ we have $f(t_{1},\dots,t_{m})\in R$
where $f$ is applied component-wise. For instance, the projection of arity $n$
to the $i$-th coordinate, denoted by $\pi^{n}_{i}$, preserves every relation
over $A$. For a set $S$ of relations over $A$ we define
$\operatorname{Pol}(S)$ as the set of all operations on $A$ that preserve all
relations in $S$. We define $\operatorname{Pol}(\mathfrak{A})$ as
$\operatorname{Pol}(S)$ where $S$ is the set of all relations of
$\mathfrak{A}$. Unary polymorphisms are also called _endomorphisms_ of
$\mathfrak{A}$; the set of all endomorphisms is denoted by
$\operatorname{End}(\mathfrak{A})$.

For a set $S$ of functions on a set $A$ we define $\operatorname{Inv}(S)$
(‘invariants of $S$’) as the set of all finitary relations over $A$ which are
preserved by all functions in $S$.

[[BN06], Theorem 4] Let $\mathfrak{A}$ be a countable $\omega$-categorical
relational structure. Then a relation $R$ over $A$ is preserved by the
polymorphisms of $\mathfrak{A}$ if and only if $R$ has a primitive positive
definition in $\mathfrak{A}$.

As a consequence of Theorem 2.2, we may go back and forth between the
existence of certain polymorphisms and the primitive positive definability of
certain relations. Furthermore, Theorem 2.2 implies that the set of
polymorphisms of an $\omega$-categorical relational structure $\mathfrak{A}$
fully captures the complexity of $\mathrm{CSP}(\mathfrak{A})$.

One of the central notions of universal algebra is that of a clone. A set of
operations on a common domain is a _clone_ if it contains all projections and
is closed under composition of functions. Thus, if we fix the domain, an
arbitrary intersection of clones is again a clone. Therefore, given a set of
operations $F$ over a common domain, there is a unique minimal clone $\langle
F\rangle$ containing $F$, which we call the clone _generated_ by $F$. For a
clone $\mathcal{F}$ on domain $A$ we will also need the _local closure_ of
$\mathcal{F}$, denoted by $\overline{\mathcal{F}}$, which is the smallest
clone which contains $\mathcal{F}$ and for any $n\in\mathbb{N}$ and $g\colon
A^{n}\rightarrow A$ the following holds: If for all finite $S\subseteq A$
there exists $f_{S}\in\mathcal{F}$ such that $f_{S}|_{S^{n}}=g|_{S^{n}}$ then
$g\in\overline{\mathcal{F}}$. If $\mathcal{F}=\overline{\mathcal{F}}$, then
$\mathcal{F}$ is _locally closed_. It is easy to show that
$\operatorname{Pol}(\mathfrak{A})$ is always a locally closed clone for any
relational structure $\mathfrak{A}$.

###  2.3. The Conditions of Nelson and Oppen

In this section we recall the classical conditions of Nelson and Oppen on
theories $T_{1}$ and $T_{2}$ with disjoint signatures that guarantee the
polynomial-time tractability of $\mathrm{CSP}(T_{1}\cup T_{2})$. Their
condition can be found in [NO79, Opp80] and [BS01] and are the following:

  * •

Both theories $T_{1}$ and $T_{2}$ must be _stably infinite_ , i.e., whenever a
finite set of literals $S$ is satisfiable in a model of the theory, then there
is also an infinite model of the theory where $S$ is satisfiable.

  * •

Both theories must be _convex_ , i.e., if we choose a finite set of literals
$S$ such that for all $i\in[n]$ there exist a model of the theory where
$S\cup\\!\left\\{x_{i}\neq y_{i}\right\\}$ is satisfiable, then there exists a
model of the theory where $S\cup\\!\left\\{x_{1}\neq y_{1},\dots,x_{n}\neq
y_{n}\right\\}$ is satisfiable.

  * •

For $i=1$ and $i=2$ there exist polynomial-time decision procedures to decide
whether a finite set of $\tau_{i}$-literals is satisfiable in some model of
$T_{i}$.

The theorem of Nelson and Oppen states that if $T_{1}$ and $T_{2}$ satisfy
these three conditions, then there exists a polynomial-time procedure that
decides whether a given set of literals over the signatures of $T_{1}$ and
$T_{2}$ is satisfiable in a model of $T_{1}\cup T_{2}$. Note that this
decision problem is in general not equal to $\mathrm{CSP}(T_{1}\cup T_{2})$,
as $S$ is restricted to atomic formulas in the latter. Nelson and Oppen always
allow relations of the form $x\neq y$ in the input, which we would like to
avoid, because there are first-order expansions $\mathfrak{A}$ of
$(\mathbb{Q};<)$ with a polynomial-time tractable CSP where adding the
relation $\neq$ to $\mathfrak{A}$ makes the CSP hard, as the following
examples shows.

Let $\mathfrak{A}$ be the temporal structure $(\mathbb{Q};<,R^{\min}_{\leq})$
where $R^{\min}_{\leq}$ is the relation defined by $\phi(x,y,z)\coloneqq x\geq
y\vee x\geq z$. Then $\mathrm{CSP}(\mathfrak{A})$ is in P by Theorem 2.5.2
below because $\mathfrak{A}$ is preserved by $\min$. But
$\mathrm{CSP}(\mathfrak{A};\neq)$ is NP-hard by Theorem 2.5.2 because
$(\mathfrak{A};\neq)$ is neither preserved by a constant operation,
$\operatorname{mi}$, $\operatorname{mx}$, $\min$, nor by their duals.

An analysis of the correctness proof of the algorithm of Nelson and Oppen
yields that the set of literals in the definition of convexity can be replaced
by a set of atomic formulas if the input of the decision problem is restricted
to a set of atomic formulas, i.e., we only require that _$\neq$ is independent
from $T_{1}$ and $T_{2}$_ (see Definition 3). Independence of $\neq$, stably
infinite theories, tractable CSPs and the presence of $\neq$ in the signature
of $T_{1}$ and $T_{2}$ is what we refer to as the _weakened_ conditions of
Nelson and Open.

Furthermore, Nelson and Oppen did not require that the signature is purely
relational. However, this difference is rather a formal one, because a
function can be represented by its graph and nested functions can be unnested
in polynomial time by introducing new existentially quantified variables for
nested terms. In Section 3 we will prove a tractability criterion which is
slightly stronger than the criterion of Nelson and Oppen with weakened
conditions.

###  2.4. Generic Combinations

In the context of combining decision procedures for CSPs, the notion of
generic combinations has been introduced in [BG20]. However, others have
studied such structures before (for instance in [Cam90, KPT05, BPP15, LP15]).

Let $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ be countably infinite
$\omega$-categorical structures with disjoint relational signatures $\tau_{1}$
and $\tau_{2}$. A countable model $\mathfrak{A}$ of
$\operatorname{Th}(\mathfrak{A}_{1})\cup\operatorname{Th}(\mathfrak{A}_{2})$
is called a _generic combination of $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$_
if for any $k\in\mathbb{N}$ and any $a,b\in A^{k}$ with pairwise distinct
coordinates

$\displaystyle\operatorname{Aut}(\mathfrak{A}^{\tau_{1}})a\cap\operatorname{Aut}(\mathfrak{A}^{\tau_{2}})b\neq\emptyset\quad\text{and}$
$\displaystyle\operatorname{Aut}(\mathfrak{A}^{\tau_{1}})a\cap\operatorname{Aut}(\mathfrak{A}^{\tau_{2}})a=\operatorname{Aut}(\mathfrak{A})a.$

All generic combinations of $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ are
isomorphic (Lemma 2.8 in [BG20]), so we will speak of _the_ generic
combination of two structures, and denote it by
$\mathfrak{A}_{1}*\mathfrak{A}_{2}$.

By definition, the $\tau_{i}$ reduct of
$\mathfrak{A}\coloneqq\mathfrak{A}_{1}*\mathfrak{A}_{2}$ is a model of
$\operatorname{Th}(\mathfrak{A}_{i})$, which is $\omega$-categorical, and
therefore, $\mathfrak{A}^{\tau_{i}}\cong\mathfrak{A}_{i}$ for $i=1$ and $i=2$.
Hence, we may assume without loss of generality that $\mathfrak{A}_{1}$,
$\mathfrak{A}_{2}$, and $\mathfrak{A}$ have the same domain. It is an easy
observation that an instance $\phi_{1}\and\phi_{2}$ of $\mathrm{CSP}(T_{1}\cup
T_{2})$, where $\phi_{i}$ is a $\tau_{i}$-formula, is satisfiable if and only
if for $i=1$ and $i=2$ there exist models $\mathfrak{A}_{i}$ of $T_{i}$ with
$\lvert A_{1}\rvert=\lvert A_{2}\rvert$ such that $\phi_{i}$ is satisfiable in
$\mathfrak{A}_{i}$ and the satisfying assignments of $\phi_{1}$ and $\phi_{2}$
identify exactly the same variables. Therefore, the fact that
$\mathrm{CSP}(\mathfrak{A})=\mathrm{CSP}(\operatorname{Th}(\mathfrak{A}_{1})\cup\operatorname{Th}(\mathfrak{A}_{2}))$
easily follows from
$\operatorname{Aut}(\mathfrak{A}^{\tau_{1}})a\cap\operatorname{Aut}(\mathfrak{A}^{\tau_{2}})b\neq\emptyset$
and $\omega$-categoricity of $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$.

A structure $\mathfrak{A}$ has _no algebraicity_ if every set defined by a
first-order formula over $\mathfrak{A}$ with parameters from $A$ is either
contained in the set of parameters or infinite. The following proposition
characterises when generic combinations of $\omega$-categorical structures
exist.

[Proposition 1.1 in [BG20]] Let $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ be
countably infinite $\omega$-categorical structures with disjoint relational
signatures. Then $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ have a generic
combination if and only if either both $\mathfrak{A}_{1}$ and
$\mathfrak{A}_{2}$ do not have algebraicity or one of $\mathfrak{A}_{1}$ and
$\mathfrak{A}_{2}$ does have algebraicity and the other structure is preserved
by all permutations.

###  2.5. Temporal Structures

A relation with a first-order definition over $(\mathbb{Q};<)$ is called
_temporal_. An example of a temporal relation is the relation
$\operatorname{Betw}$ from the introduction. A _temporal structure_ is a
relational structure $\mathfrak{A}$ with domain $\mathbb{Q}$ all of whose
relations are temporal. The structure $(\mathbb{Q};<)$ is homogeneous, i.e.,
every order-preserving map between two finite subsets of $\mathbb{Q}$ can be
extended to an automorphism of $(\mathbb{Q};<)$. Therefore, the orbit of a
tuple in $\mathfrak{A}$ is determined by identifications and the ordering
among the coordinates. It follows from Theorem 2.1 that all temporal
structures are $\omega$-categorical.

####  2.5.1. Polymorphisms of Temporal Structures

One of the fundamental results in the proof of the complexity dichotomy for
temporal CSPs, Theorem 2.5.1 below, also plays an important role for
combinations of temporal CSPs. To understand Theorem 2.5.1 and for later use,
we define the relations $\operatorname{Cycl}$, $\operatorname{Betw}$, and
$\operatorname{Sep}$:

$\displaystyle\operatorname{Betw}\coloneqq\\{(x,y,z)\in\mathbb{Q}^{3}\mid\,$
$\displaystyle(x<y<z)\vee(z<y<x)\\}$
$\displaystyle\operatorname{Cycl}\coloneqq\\{(x,y,z)\in\mathbb{Q}^{3}\mid\,$
$\displaystyle(x<y<z)\vee(y<z<x)\vee(z<x<y)\\}$
$\displaystyle\operatorname{Sep}\coloneqq\\{(x,y,u,v)\in\mathbb{Q}^{3}\mid\,$
$\displaystyle(x<u<y<v)\vee(y<u<x<v)\vee$
$\displaystyle(x<v<y<u)\vee(y<v<x<u)\\}$

[Bodirsky and Kára [BK09], Theorem 20] Let $\mathfrak{A}$ be a temporal
structure. Then at least one of the following cases applies.

  * •

$\mathfrak{A}$ has a constant endomorphism;

  * •

One of the relations $<$, $\operatorname{Cycl}$, $\operatorname{Betw}$, or
$\operatorname{Sep}$ has a primitive positive definition in $\mathfrak{A}$.

  * •

$\mathfrak{A}$ is preserved by all permutations of $\mathbb{Q}$.

We introduce several notions that are needed to describe the polynomial-time
tractable temporal CSPs from [BK09]. However, as opposed to [BK09] we flip the
roles of $0$ and $1$ in the following definition because in this way the
resulting systems of equations are homogeneous (see Theorem 2.5.3 (4) below;
we follow [BPR20]). For a tuple $t\in\mathbb{Q}^{n}$ we define the _min-
indicator function_ $\chi\colon\mathbb{Q}^{n}\rightarrow\\{0,1\\}^{n}$ by
$\chi(t)[i]\coloneqq 1$ if and only if $t[i]\leq t[j]$ for all $1\leq j\leq
n$. The tuple $\chi(t)\in\\{0,1\\}^{n}$ is called the _min-tuple_ of
$t\in\mathbb{Q}^{n}$. For an $n$-ary relation $R$ we define

$\chi(R)\coloneqq\\!\left\\{\chi(t)\mid t\in R\right\\}\text{ and
}\chi_{0}(R)\coloneqq\chi(R)\cup\\{(\underbrace{0,\dots,0}_{n\text{
zeros}})\\}.$

Let $\min$ denote the binary minimum operation on $\mathbb{Q}$. For any fixed
endomorphisms $\alpha,\beta,\gamma$ of $(\mathbb{Q};<)$ which satisfy
$\alpha(a)<\beta(a)<\gamma(a)<\alpha(a+\epsilon)$ for every $a\in\mathbb{Q}$
and every $\epsilon\in\mathbb{Q}$ with $\epsilon>0$, the binary operation
$\operatorname{mi}$ on $\mathbb{Q}$ is defined by

$\operatorname{mi}(x,y)\coloneqq\left\\{\begin{array}[]{ll}\alpha(x)&\text{ if
}x=y,\\\ \beta(y)&\text{ if }x>y,\\\ \gamma(x)&\text{ if
}x<y.\end{array}\right.$

The intuition behind this definition is best explained through illustrations;
for such illustrations, additional explanation, and the argument why such
functions do exist we refer the reader to [BK09] or [Bod21]; the same applies
to the operations that are introduced in this section. For $\alpha,\beta$
satisfying the same conditions, $\operatorname{mx}$ is the binary operation on
$\mathbb{Q}$ defined by

$\operatorname{mx}(x,y)\coloneqq\left\\{\begin{array}[]{ll}\alpha(\min(x,y))&\text{
if }x\neq y,\\\ \beta(x)&\text{ if }x=y.\end{array}\right.$

[[BPR20], Lemma 4.1 and Theorem 5.2] We have

$\overline{\langle\\{\operatorname{mx}\\}\cup\operatorname{Aut}({\mathbb{Q}};<)\rangle}=\operatorname{Pol}({\mathbb{Q}};X)$

where

$X\coloneqq\\{(x,y,z)\in\mathbb{Q}^{3}\mid x=y<z\vee x=z<y\vee y=z<x\\}.$

Moreover, every temporal structure $\mathfrak{B}$ preserved by
$\operatorname{mx}$ either admits a primitive positive definition of $X$ or is
preserved by a constant operation or by $\min$.

Let ll be an arbitrary binary operation on $\mathbb{Q}$ such that
$\textup{{ll}}(a,b)<\textup{{ll}}(a^{\prime},b^{\prime})$ if and only if

  * •

$a\leq 0$ and $a<a^{\prime}$, or

  * •

$a\leq 0$ and $a=a^{\prime}$ and $b<b^{\prime}$, or

  * •

$a,a^{\prime}>0$ and $b<b^{\prime}$, or

  * •

$a>0$ and $b=b^{\prime}$ and $a<a^{\prime}$.

Let $\operatorname{lex}\colon\mathbb{Q}^{2}\rightarrow\mathbb{Q}$ be an
arbitrary operation that induces the lexicographic order on $\mathbb{Q}^{2}$
(just like ll if the first argument is not positive). Let
$\operatorname{pp}\colon\mathbb{Q}^{2}\rightarrow\mathbb{Q}$ be an arbitrary
operation such that
$\operatorname{pp}(a,b)\leq\operatorname{pp}(a^{\prime},b^{\prime})$ if and
only if either

  * •

$a\leq 0$ and $a\leq a^{\prime}$, or

  * •

$0<a$, $0<a^{\prime}$ and $b\leq b^{\prime}$ holds.

Notice that the functions $\operatorname{mi}$, $\operatorname{mx}$,
$\operatorname{pp}$, ll, their duals, and $\operatorname{lex}$ are not
uniquely specified by their definitions. They rather specify a unique weak
linear order on $\mathbb{Q}^{2}$. By Observation 10.2.3 in [Bod12], any two
functions in $\operatorname{Pol}(\mathbb{Q};<)$ which generate the same weak
linear order on $\mathbb{Q}^{2}$ are equivalent with respect to containment in
subclones of $\operatorname{Pol}(\mathbb{Q};<)$. Hence, we may assume the
following additional properties for convenience:

  * •

$\operatorname{mx}(0,0)=1$ and $\operatorname{mx}(1,0)=0$,

  * •

$\operatorname{mi}(0,0)=0,\operatorname{mi}(1,0)=1,\operatorname{mi}(0,1)=2,\operatorname{mi}(1,1)=3$,

  * •

$\textup{{ll}}(0,0)=0$, $\textup{{ll}}(1,0)=1$, $\textup{{ll}}(2,0)=2$,
$\textup{{ll}}(3,0)=3$ and $\textup{{ll}}(1,1)=4$.

The polymorphisms we presented are connected by the following inclusions (see
[BK09] or Chapter 12 in [Bod21]). For
$m\in\\!\left\\{\min,\operatorname{mi},\operatorname{mx}\right\\}$ and
$l\in\\!\left\\{\textup{{ll}},\operatorname{dual-ll}\right\\}$ we have

$\displaystyle\overline{\langle\operatorname{pp},\operatorname{Aut}(\mathbb{Q})\rangle}$
$\displaystyle\subseteq\overline{\langle
m,\operatorname{Aut}(\mathbb{Q})\rangle},$
$\displaystyle\overline{\langle\operatorname{dual-
pp},\operatorname{Aut}(\mathbb{Q})\rangle}$
$\displaystyle\subseteq\overline{\langle\textup{dual-}m,\operatorname{Aut}(\mathbb{Q})\rangle},$
$\displaystyle\overline{\langle\operatorname{lex},\operatorname{Aut}(\mathbb{Q})\rangle}$
$\displaystyle\subseteq\overline{\langle
l,\operatorname{Aut}(\mathbb{Q})\rangle}.$

####  2.5.2. Complexity of Temporal CSPs

We can now state the complexity dichotomy for temporal CSPs.

[[BK09], Theorem 50] Let $\mathfrak{A}$ be a temporal structure with finite
signature. Then one of the following applies:

  1. (1)

$\mathfrak{A}$ is preserved by $\min$, $\operatorname{mi}$,
$\operatorname{mx}$, ll, the dual of one of these operations, or by a constant
operation. In this case $\mathrm{CSP}(\mathfrak{A})$, is in P.

  2. (2)

$\mathrm{CSP}(\mathfrak{A})$ is NP-complete.

In our proofs, we also need some intermediate results from [BK09]. In
particular, we use the ternary temporal relation introduced in Definition 3 in
[BK09]:

$T_{3}\coloneqq\\!\left\\{(x,y,z)\mid x=y<z\vee x=z<y\right\\}$

$T_{3}$ is preserved by $\operatorname{pp}$, but by none of the polymorphisms
listed in item (1) of Theorem 2.5.2 and therefore
$\mathrm{CSP}(\mathbb{Q};T_{3})$ is NP-complete.

[[BK09], Lemma 36] Let $\mathfrak{A}$ be a first-order expansion of
$(\mathbb{Q};<)$ preserved by $\operatorname{pp}$. Then either $T_{3}$ has a
primitive positive definition in $\mathfrak{A}$, or $\mathfrak{A}$ is
preserved by $\operatorname{mi}$, $\operatorname{mx}$, or $\min$.

####  2.5.3. Known Syntactic Descriptions of Temporal Relations

We also need syntactic descriptions for temporal relations preserved by the
operations introduced in the previous sections.

[[BCW14] (Theorems 4, 5, and 6), [Bod12] (Proposition 10.4.7 and Theorem
10.5.18), and [BK09] (observation above Theorem 42)] A temporal relation $R$
is preserved by

  1. (1)

$\operatorname{pp}$ if and only if $R$ can be defined by a conjunction of
formulas of the form

$\displaystyle x_{1}\circ_{2}x_{2}\vee\dots\vee x_{1}\circ_{n}x_{n}\text{
where }\circ_{i}\in\\{\neq,\geq\\};$

  2. (2)

$\min$ if and only if $R$ can be defined by a conjunction of formulas of the
form

$\displaystyle x_{1}\circ_{2}x_{2}\vee\dots\vee x_{1}\circ_{n}x_{n}\text{
where }\circ_{i}\in\\{>,\geq\\}.$

  3. (3)

$\operatorname{mi}$ if and only if $R$ can be defined by a conjunction of
formulas of the form

$\displaystyle x_{1}\circ_{2}x_{2}\vee\dots\vee x_{1}\circ_{n}x_{n}\text{
where }\circ_{i}\in\\!\left\\{\neq,>,\geq\right\\}\text{ with at most one
}\circ_{i}\text{ equal to }\geq.$

  4. (4)

$\operatorname{mx}$ if and only if $R$ can be defined by a conjunction of
$\\{<\\}$-formulas $\phi(x_{1},\dots,x_{n})$ for which there exists a
homogeneous system $Ax=0$ of linear equations over $\operatorname{GF}_{2}$
such that for every $t\in\mathbb{Q}^{n}$

$\displaystyle t\text{ satisfies }\phi\text{ if and only if }A\chi(t)=0.$

In this case, there exists a homogeneous system $Ax=0$ of linear equations
over $\operatorname{GF}_{2}$ with solution space $\chi_{0}(R)$.

  5. (5)

ll if and only if $R$ can be defined by a conjunction of formulas of the form

$\displaystyle(x_{1}>x_{2}\vee\dots\vee
x_{1}>x_{m})\vee(x_{1}=\dots=x_{m})\vee\bigvee_{m<2i<n}x_{2i}\neq x_{2i+1},$

where the clause $x_{1}=\dots=x_{m}$ may be omitted.

Note that the relation $R^{\operatorname{mix}}$ can equivalently be written as

$R^{\operatorname{mix}}=\big{\\{}(a,b,c)\in\mathbb{Q}^{3}\mid(a\geq b\vee
a>c)\wedge(b\geq a\vee b>c)\\}.$

Theorem 2.5.3 then implies that $R^{\operatorname{mix}}$ is preserved by
$\min$ and $\operatorname{mi}$. To see that $R^{\operatorname{mix}}$ is also
preserved by $\operatorname{mx}$, note that
$\chi_{0}(R^{\operatorname{mix}})=\\{(1,1,1),(1,1,0),(0,0,1),(0,0,0)\\}$,
which is the solution space of the linear equation $x_{1}=x_{2}$, and
$R^{\operatorname{mix}}$ contains all triples over ${\mathbb{Q}}$ whose
$\min$-tuple satisfies $x_{1}=x_{2}$.

Every temporal relation can be defined by a quantifier-free $\\{<\\}$-formula
$\phi$ and one may assume that $\phi$ is written in _conjunctive normal form
(CNF)_

$\bigwedge_{\ell=1}^{k}\bigvee_{i\in I_{\ell}}\phi_{\ell,i}$

where $\phi_{\ell,i}$ is an atomic $\\{<\\}$-formula. We say that $\phi$ is in
_reduced CNF_ if we cannot remove any disjunct $\phi_{\ell,i}$ from $\phi$
without altering the defined relation. If $\phi$ is in reduced CNF, then for
any $\ell\in[k]$ and $i\in I_{\ell}$ there exists $t\in R$ that satisfies
$\phi_{\ell,i}$ and does not satisfy any other disjunct $\phi_{\ell,j}$ for
$j\in I_{\ell}\setminus\\{i\\}$. We use the symbols $\leq,\neq,\geq,>$ as the
usual shortcuts, for $x<y\vee x=y$, etc. Clearly, every formula is equivalent
to a formula in reduced CNF. Remarkably, the syntactic form in 2 is preserved
by removing literals; hence, in 2 we may assume without loss of generality
that the definition of $R$ is additionally reduced.

###  2.6. Known Relational Generating Sets

Many important temporal structures $\mathfrak{A}$ can also be described
elegantly and concisely by specifying a finite set of temporal relations such
that the temporal relations of $\mathfrak{A}$ are precisely those that have a
primitive positive definition in $\mathfrak{A}$. Note that such a finite set
might not exist even if $\mathfrak{A}$ contains all relations that are
primitively positively definable in $\mathfrak{A}$. We need such a result for
the temporal structure that contains all temporal relations preserved by
$\operatorname{pp}$.

[[Bod21], Theorem 12.7.4] A temporal relation is preserved by
$\operatorname{pp}$ if and only if it has a primitive positive definition in
$(\mathbb{Q};\neq,R^{\min}_{\leq},S^{\operatorname{mi}})$ where

$\displaystyle R^{\min}_{\leq}$
$\displaystyle\coloneqq\\!\left\\{(x,y,z)\in\mathbb{Q}^{3}\mid x\geq y\vee
x\geq z\right\\}\quad\text{ and }$ $\displaystyle S^{\operatorname{mi}}$
$\displaystyle\coloneqq\\!\left\\{(x,y,z)\in\mathbb{Q}^{3}\mid x\neq y\vee
x\geq z\right\\}.$

##  3\. Polynomial-Time Tractable Combinations

The following definition already appeared in [Bod21] and [BJR02] and is
closely related to the convexity condition of Nelson and Oppen. The key
difference to convexity of $T$ is that we consider conjunctions of atomic
formulas instead of conjunctions of literals.

Let $T$ be a $\tau$-theory. We say that _$\neq$ is independent from $T$_ if
for any conjunction of atomic $\tau$-formulas $\phi$ the formula
$\phi\and\bigwedge_{i=1}^{k}x_{i}\neq y_{i}$ is satisfiable in some model of
$T$ whenever the formula $\phi\and x_{i}\neq y_{i}$ is satisfiable in some
model of $T$ for every $i\in[k]$.

The following is easy to see (see, e.g., [Bod21]).

######  Proposition 4.

For every structure $\mathfrak{A}$ with a binary injective polymorphism,
$\neq$ is independent from $\operatorname{Th}(\mathfrak{A})$.

Nelson and Oppen require that both theories are stably infinite. We will make
a weaker assumption captured by the following notion.

Let $T_{1}$ and $T_{2}$ be theories with signatures $\tau_{1}$ and $\tau_{2}$,
respectively. We say that $T_{1}$ and $T_{2}$ are _cardinality compatible_ if
for all for $i\in[2]$ and all conjunctions $\phi_{i}(x_{1},\dots,x_{n})$ of
atomic $\tau_{i}$-formulas, such that $\\!\left\\{\exists
x_{1},\dots,x_{n}.\,\phi_{i}\right\\}\cup T_{i}$ has a model, there are models
of $\\!\left\\{\exists x_{1},\dots,x_{n}.\,\phi_{1}\right\\}\cup T_{1}$ and
$\\!\left\\{\exists x_{1},\dots,x_{n}.\,\phi_{2}\right\\}\cup T_{2}$ of equal
cardinality.

Clearly, if $T_{1}$ and $T_{2}$ are stably infinite, then they are also
cardinality compatible. Contrary to stably infinite theories where we require
that we can choose the cardinality of the models to be countably infinite, the
definition of cardinality compatibility also allows theories with finite
models only. We also allow theories where some formulas are only satisfiable
in finite models while others have infinite models, as the following example
shows.

Let $T$ be the theory $\\!\left\\{\forall x,y\,(\neg Q(x)\vee x=y)\right\\}$
whose signature only contains the unary relation symbol $Q$. There is an
infinite model for $T$ where $Q$ is empty. However, if $\phi$ is the formula
$Q(x)$, then all models for $T\cup\\!\left\\{\phi\right\\}$ have exactly one
element and this element is contained in $Q$. Hence, $T$ is not stably
infinite, but cardinality compatible with itself.

The sufficient conditions for polynomial-time tractability of
$\mathrm{CSP}(T_{1}\cup T_{2})$ given in the following theorem are slightly
weaker than those by Nelson and Oppen.

######  Theorem 5.

Let $T_{1}$ and $T_{2}$ be cardinality compatible theories with finite,
disjoint relational signatures and polynomial-time tractable CSPs. If $\neq$
is independent from both $T_{1}$ and $T_{2}$ and $\neq$ has an ep-definition
in both $T_{1}$ and $T_{2}$, then $\mathrm{CSP}(T_{1}\cup T_{2})$ is
polynomial-time tractable.

######  Proof 3.1.

Let $\tau_{1}$ and $\tau_{2}$ be the signatures of $T_{1}$ and $T_{2}$,
respectively. Let $S$ be a set of atomic $\tau_{1}\cup\tau_{2}$-formulas with
free variables among $x_{1},\dots,x_{n}$. Then we may partition $S$ into
$S_{1}$ and $S_{2}$ such that $S_{i}$ is a set of $\tau_{i}$-formulas and
$S=S_{1}\cup S_{2}$. Without loss of generality, we may assume that all
variables occur in both $S_{1}$ and $S_{2}$ (this can also be attained by
introduction of dummy constraints like $x=x$). Let $\phi_{i}(x,y)$ be an
existential positive definition of $x\neq y$ in $T_{i}$ for $i\in\\{1,2\\}$.
For $i=1$ and $i=2$ and for each tuple of variables $(x_{k},x_{l})$ and each
disjunct $D(\cdot\,,\cdot)$ in $\phi_{i}$ we test whether
$S_{i}\cup\\!\left\\{D(x_{k},x_{l})\right\\}$ is satisfiable is some model of
$T_{i}$. If, for a fixed tuple $(x_{k},x_{l})$, the answer is
_‘unsatisfiable’_ for all disjuncts of $\phi_{i}$, then we replace all
occurrences of $x_{l}$ in $S_{1}$ and in $S_{2}$ by $x_{k}$. We iterate this
procedure until no more replacements are made. If $S_{1}$ or $S_{2}$ is
unsatisfiable in all models of $T_{1},T_{2}$ respectively thereafter, we
return _‘unsatisfiable’_. Otherwise, we return _‘satisfiable’_.

To prove that this algorithm is correct, notice that if
$S_{i}\cup\\!\left\\{D(x_{k},x_{l})\right\\}$ is unsatisfiable for all
disjuncts $D$ of $\phi_{i}$, then clearly $S_{i}\cup\\!\left\\{x_{k}\neq
x_{l}\right\\}$ is not satisfiable. Moreover, if $S_{1}$ or $S_{2}$ is
unsatisfiable, then their union is unsatisfiable as well. Hence, the
substitutions done by the algorithm do not change the satisfiability of
$S_{1}\cup S_{2}$ in models of $T_{1}\cup T_{2}$. Let us therefore assume that
after the substitution process both $S_{1}$ and $S_{2}$ are satisfiable in
some model of $T_{1}$ and $T_{2}$, respectively. Without loss of generality we
may assume that the variables $x_{1},\dots,x_{m}$ remain in $S_{1}$ and in
$S_{2}$. Furthermore, we know that $S_{i}\cup\\!\left\\{x_{k}\neq
x_{l}\right\\}$ is satisfiable for all $k\neq l$ with $k,l\leq m$ and both
$i\in\\!\left\\{1,2\right\\}$. Therefore, $S_{i}\cup\bigcup_{k\neq
l}\\!\left\\{x_{k}\neq x_{l}\right\\}$ is satisfiable in some model of
$T_{i}$, because $\neq$ is independent from $T_{i}$, i.e., there exists
$\mathfrak{M}_{i}\models T_{i}$ and an injective assignment
$s_{i}\colon\\!\left\\{x_{1},\dots,x_{m}\right\\}\rightarrow\mathfrak{M}_{i}$
such that $\mathfrak{M}_{i}\models\bigwedge_{\sigma\in S_{i}}\sigma(s_{i})$,
where $\sigma(s_{i})$ denotes $\sigma(s_{i}(y_{1}),\dots,s_{i}(y_{k}))$ and
$y_{1},\dots,y_{k}$ denote the variables in $\sigma$. By the cardinality
compatibility of $T_{1}$ and $T_{2}$, we may assume that $\mathfrak{M}_{1}$
and $\mathfrak{M}_{2}$ have the same cardinality. Therefore, there exists a
bijection $f\colon M_{1}\rightarrow M_{2}$ between their domains such that
$f(s_{1}(x_{k}))=s_{2}(x_{k})$ for all $k\in[m]$. With this bijection we
define a $\tau_{1}\cup\tau_{2}$ structure $\mathfrak{M}$ which is a model of
$T_{1}\cup T_{2}$ via $R^{\mathfrak{M}}\coloneqq R^{\mathfrak{M}_{1}}$ for
$R\in\tau_{1}$, and $a\in R^{\mathfrak{M}}$ if and only if $f(a)\in
R^{\mathfrak{M}_{2}}$ for $R\in\tau_{2}$. This is well-defined, because the
signatures of $T_{1}$ and $T_{2}$ are disjoint and because $s_{1}$ and $s_{2}$
are both injective. It is easy to verify that $\mathfrak{M}$ is a model of
$T_{1}\cup T_{2}$ and $\mathfrak{M}\models\bigwedge_{\sigma\in
S_{1}}\sigma(s_{1})\and\bigwedge_{\sigma\in S_{2}}\sigma(s_{1})$ and hence,
the original instance is satisfiable.

The number of calls to the decision procedures for $T_{1}$ and $T_{2}$ is
bounded by the number of pairs $(x_{k},x_{l})$ multiplied by the maximal
number of rounds of substitutions and the number of disjuncts in $\phi_{1}$
and $\phi_{2}$. Hence, the runtime of the algorithm is in $O(n^{3})$.

Notice that the tractability result by Nelson and Oppen can be obtained as a
special case of Theorem 5 when we consider theories which are stably infinite
and where the set of atomic formulas is closed under negation. The following
example shows that our condition covers strictly more cases already for
combinations of temporal CSPs.

For $i=1$ and $i=2$, let $({\mathbb{Q}};<_{i},\leq_{i})$ be a structure where
$<_{i}$ denotes the usual strict linear order on the rational numbers, and
$\leq_{i}$ denotes the corresponding weak linear order. Let
$T_{i}\coloneqq\operatorname{Th}({\mathbb{Q}};<_{i},\leq_{i})$. Note that the
relation $\neq$ does not have a primitive positive definition in
$({\mathbb{Q}};<_{i},\leq_{i})$; however, it has the existential positive
definition $x<_{1}y\vee y<_{1}x$. It is well-known that
$\mathrm{CSP}({\mathbb{Q}};<_{i},\leq_{i})$ can be solved in polynomial time
[VKvB89] and that $\neq$ is independent from $T_{i}$ [BJR02]. Then $T_{1}$ and
$T_{2}$ satisfy the conditions from Theorem 5 but do not satisfy the
conditions of Nelson and Oppen.

##  4\. The Operation $\operatorname{mix}$

A certain temporal structure plays an important role in our proof; it contains
the set of all temporal relations preserved by an operation, which we call
$\operatorname{mix}$, and which is similar to the polymorphisms
$\operatorname{mi}$ and $\operatorname{mx}$. We also present an equivalent
description of these relations in terms of syntactically restricted
quantifier-free $\\{<\\}$-formulas (Theorem 9).

Let $\alpha,\beta,\gamma$ be endomorphisms of $(\mathbb{Q};<)$ such that
$\gamma(a)<\alpha(a)<\beta(a)<\gamma(a+\epsilon)$ for every
$a,\epsilon\in\mathbb{Q}$ with $\epsilon>0$. Then $\operatorname{mix}$ is the
binary operation on $\mathbb{Q}$ defined by

$\operatorname{mix}(x,y)\coloneqq\left\\{\begin{array}[]{ll}\alpha(x)&\text{
if }x<y,\\\ \beta(x)&\text{ if }x=y,\\\ \gamma(y)&\text{ if
}x>y.\end{array}\right.$

In analogy to our convention in the case of the operations mi, mx, and ll, we
fix some concrete values for the operation mix. We claim that the
endomorphisms $\alpha$, $\beta$, and $\gamma$ from the definition of mix can
be chosen so that $\gamma(x)=3x$, $\alpha(x)=3x+1$, and $\beta(x)=3x+2$ for
every $x\in\mathbb{Z}^{+}$. Figure 1 shows some values for
$\operatorname{mix}$. For every $k\in\mathbb{Z}^{+}$, we define $\gamma_{k},$
$\alpha_{k}$, and $\beta_{k}$ inductively as follows. In the _base case_
$k=0$, we set $\alpha_{0}\coloneqq\delta_{0}\circ\alpha$,
$\beta_{0}\coloneqq\delta_{0}\circ\beta$, and
$\gamma_{0}\coloneqq\delta_{0}\circ\gamma$, where $\alpha,\beta,\gamma$ are
arbitrary operations satisfying the requirements in Definition 24 and
$\delta_{0}$ is an automorphism of $(\mathbb{Q};<)$ such that
$(\delta_{0}\circ\gamma)(0)=0$, $(\delta_{0}\circ\alpha)(0)=1$, and
$(\delta_{0}\circ\beta)(0)=2$. Such $\delta_{0}$ exists because
$(\mathbb{Q};<)$ is homogeneous and $\gamma(0)<\alpha(0)<\beta(0)$. In the
_induction step_ $k\to k+1$ we assume that, for every integer $0\leq\ell\leq
k$, the endomorphisms $\alpha_{\ell}$, $\beta_{\ell}$, and $\gamma_{\ell}$ of
$(\mathbb{Q};<)$ are already defined and satisfy:

  1. (1)

the requirements in Definition 24;

  2. (2)

$\gamma_{\ell}(\ell)=3\ell$, $\alpha_{\ell}(\ell)=3\ell+1$, and
$\beta_{\ell}(\ell)=3\ell+2$;

  3. (3)

if $\ell>0$, then $\alpha_{\ell},$ $\beta_{\ell}$, and $\gamma_{\ell}$ take
the same values as $\alpha_{\ell-1},$ $\beta_{\ell-1}$, and $\gamma_{\ell-1}$
on $(-\infty,\ell-1]$, respectively.

We set $\alpha_{k+1}\coloneqq\delta_{k+1}\circ\alpha_{k}$,
$\beta_{k+1}\coloneqq\delta_{k+1}\circ\beta_{k}$, and
$\gamma_{k+1}\coloneqq\delta_{k+1}\circ\gamma_{k}$, where $\delta_{k+1}$ is
the identity map on $(-\infty,3k+2]$ and otherwise a piecewise affine
transformation sending

  * •

$[3k+2,\gamma_{k}(k+1)]$ to $[3k+2,3(k+1)]$,

  * •

$[\gamma_{k}(k+1),\alpha_{k}(k+1)]$ to $[3(k+1),3(k+1)+1]$,

  * •

$[\alpha_{k}(k+1),\beta_{k}(k+1)]$ to $[3(k+1)+1,3(k+1)+2]$, and

  * •

$[\beta_{k}(k+1),\infty)$ to $[3(k+1)+2,\infty)$.

Such $\delta_{k+1}$ is clearly an automorphism of $(\mathbb{Q};<)$ and
$\alpha_{k+1}$, $\beta_{k+1}$, and $\gamma_{k+1}$ satisfy the items 1-3. from
above. The sequences $(\alpha_{k})$, $(\beta_{k})$, and $(\gamma_{k})$
converge pointwise to endomorphisms $\alpha,\beta,\gamma$ of $(\mathbb{Q};<)$
with the desired properties.

0011223320001115334486711 Figure 1. The image of $\operatorname{mix}$ on
$\\!\left\\{0,1,2,3\right\\}^{2}$.

######  Lemma 6.

The locally closed clone generated by $\operatorname{mix}$ and
$\operatorname{Aut}(\mathbb{Q};<)$ contains $\operatorname{mi}$.

######  Proof 4.1.

It is easy to check that
$f(x,y)\coloneqq\operatorname{mix}(\operatorname{mix}(x,y),3y)$ induces the
same linear order as $\operatorname{mi}(x,y)$ on $(\mathbb{Z}^{+})^{2}$.
Hence, for any finite set $S\subseteq\mathbb{Q}$ there exist
$\alpha,\beta,\gamma\in\operatorname{Aut}(\mathbb{Q};<)$ such that $\alpha
f(\beta(x),\gamma(y))|_{S^{2}}=\operatorname{mi}(x,y)|_{S^{2}}$. Then, by
definition,
$\operatorname{mi}\in\overline{\langle\operatorname{mix},\operatorname{Aut}(\mathbb{Q};<)\rangle}$.

The relation $R^{\operatorname{mix}}$ has the generalisation
$R^{\operatorname{mix}}_{n}$ of arity $n\geq 3$ defined as follows.

$\displaystyle R^{\operatorname{mix}}_{n}$
$\displaystyle\coloneqq\big{\\{}(a_{1},\dots,a_{n})\in{\mathbb{Q}}^{n}\mid\min(a_{3},\dots,a_{n})\geq\min(a_{1},a_{2})\Rightarrow
a_{1}=a_{2}\big{\\}}$ (1)

Note that $R^{\operatorname{mix}}_{n}(x_{1},\dots,x_{n})$ has the following
definition in CNF

$\phi^{\operatorname{mix}}_{n}(x_{1},\dots,x_{n})\coloneqq\big{(}x_{1}\geq
x_{2}\vee\bigvee_{i\in\\{3,\dots,n\\}}x_{1}>x_{i})\and(x_{2}\geq
x_{1}\vee\bigvee_{i\in\\{3,\dots,n\\}}x_{2}>x_{i}\big{\\}}$

which is both of the form described in item 2 and of the form described in 3
in Theorem 2.5.3. Hence, $R^{\operatorname{mix}}_{n}$ is preserved by $\min$
and by $\operatorname{mi}$. Also note that
$R^{\operatorname{mix}}=R^{\operatorname{mix}}_{3}$ and that
$R^{\operatorname{mix}}(a,b,c)$ is equivalent to
$R^{\operatorname{mi}}(a,b,c)\wedge R^{\operatorname{mi}}(b,a,c)$ where

$R^{\operatorname{mi}}\coloneqq\big{\\{}(a,b,c)\in\mathbb{Q}^{3}\mid a\geq
b\vee a>c\big{\\}}.$

The relation $R^{\operatorname{mix}}_{n}$ is also preserved by
$\operatorname{mx}$; we first prove this for $R^{\operatorname{mix}}_{3}$.

######  Lemma 7.

For every $n\geq 3$, the relation $R^{\operatorname{mix}}_{n}$ has a primitive
positive definition in $(\mathbb{Q};<,R^{\operatorname{mix}})$.

######  Proof 4.2.

A primitive positive definition of $R^{\operatorname{mix}}_{n}$ can be
obtained inductively by the observation that
$R^{\operatorname{mix}}_{n}(x_{1},\dots,x_{n})$ is equivalent to the following
formula.

$\displaystyle\exists
h\,\big{(}R^{\operatorname{mix}}_{n-1}(x_{1},h,x_{3},\dotsc,x_{n-1})\and
R^{\operatorname{mix}}(h,x_{2},x_{n})\big{)}$ (2)

Every tuple $t\in R^{\operatorname{mix}}_{n}$ satisfies (2): if $t$ satisfies
$x_{1}=x_{2}$ or if $t$ satisfies $x_{n}<\min(x_{1},x_{2})$, choose $h=x_{1}$;
if $t$ satisfies $x_{i}<\min(x_{1},x_{2})$ for some $i\in\\{3,\dots,n-1\\}$,
choose $h=x_{2}$. Conversely, suppose that $t\in{\mathbb{Q}}^{n}$ satisfies
(2). If $t$ satisfies $x_{1}=h$, then $t$ satisfies $x_{1}=x_{2}=h$ or
$x_{n}<x_{1}\and x_{n}<x_{2}$ and therefore $R^{\operatorname{mix}}_{n}$. The
case that $t$ satisfies $x_{2}=h$ is analogous. If $t$ satisfies $x_{n}<h\and
x_{n}<x_{2}$ and $x_{i}<x_{1}\and x_{i}<h$ for some $i\in\\{3,\dots,n\\}$,
then it also satisfies $\min(x_{i},x_{n})<\min(x_{1},x_{2})$ and hence $t$
satisfies $R^{\operatorname{mix}}_{n}$.

######  Lemma 8.

For every $n\geq 3$, the operation $\operatorname{mix}$ preserves
$R^{\operatorname{mix}}_{n}$.

######  Proof 4.3.

To prove that $\operatorname{mix}$ preserves $R^{\operatorname{mix}}_{n}$ it
suffices prove that $\operatorname{mix}$ preserves $R^{\operatorname{mix}}$
due to Lemma 7 and Theorem 2.2. Suppose for contradiction that there are
$t_{1},t_{2}\in R^{\operatorname{mix}}$ such that
$t_{3}\coloneqq\operatorname{mix}(t_{1},t_{2})\not\in R^{\operatorname{mix}}$.
Then $t_{3}$ must satisfy $(x<y\and x\leq z)\vee(y<x\and y\leq z)$. Without
loss of generality we may assume that $t_{3}$ satisfies the first disjunct. As
$t_{3}[x]$ is minimal in $t_{3}$, the coordinate $x$ must be minimal in either
$t_{1}$ or $t_{2}$. Assume the coordinate $x$ is minimal in $t_{1}$; the case
with $t_{2}$ can be proven analogously. Then $t_{1}$ satisfies $x=y$ because
$t_{1}\in R^{\operatorname{mix}}$. If $t_{2}$ satisfies $x=y$ then $t_{3}$
satisfies $x=y$, contrary to our assumptions. This implies that $t_{2}\in
R^{\operatorname{mix}}$ satisfies $z<\min(x,y)$. If $t_{2}[z]<t_{1}[x]$ then
$\min(t_{1}[z],t_{2}[z])=t_{2}[z]<\min(t_{1}[x],t_{2}[x])$, and hence
$t_{3}[z]<t_{3}[x]$, a contradiction. Therefore,
$\min(t_{2}[x],t_{2}[y])>t_{1}[x]=t_{1}[y]$ and hence $t_{3}[x]=t_{3}[y]$, a
contradiction.

######  Theorem 9.

A temporal relation is preserved by $\operatorname{mix}$ if and only if it has
a definition by a conjunction of clauses of the form

$\displaystyle\bigvee_{i=1}^{n}x\neq
z_{i}\vee\bigvee_{i=1}^{m}x>y_{i}\qquad\text{for }n,m\in\mathbb{N}$ (3) and
$\displaystyle\phi^{\operatorname{mix}}_{n}(x_{1},x_{2},x_{3},\dotsc,x_{n})\qquad\text{for
}n\geq 3.$ (4)

######  Proof 4.4.

Let $R$ be a temporal relation preserved by $\operatorname{mix}$. Due to Lemma
6, the relation $R$ is also preserved by $\operatorname{mi}$. By Theorem 2.5.3
case 3 the relation $R$ can be defined by a conjunction $\phi$ of clauses of
the form

$\displaystyle x\geq y\vee\bigvee_{i=1}^{n}x\neq
z_{i}\vee\bigvee_{i=1}^{m}x>y_{i}\qquad\text{for }n,m\in\mathbb{N}$ (5)

where the literal $x\geq y$ can be omitted. Let $U_{\phi}$ be the set of
clauses in $\phi$ which do have a literal of the form $x\geq y$ and which
cannot be paired with another clause such that their conjunction is of the
form $\phi^{\operatorname{mix}}_{k}$ for some $k$. Without loss of generality,
we may assume that $\phi$ is chosen such that $\lvert U_{\phi}\rvert$ is
minimal and such that no literal of the form $x\neq z_{j}$ can be replaced by
$x>z_{j}$ without altering the relation defined by $\phi$. If $U_{\phi}$ is
empty, then we are done. Suppose towards a contradiction that $U_{\phi}$
contains a clause $C\coloneqq\big{(}x\geq y\vee\bigvee_{1}^{n}x\neq
z_{i}\vee\bigvee_{1}^{m}x>y_{i}\big{)}$. Consider the new formulas
$\phi_{1},\dots,\phi_{n+3}$ obtained from $\phi$ by replacing $C$ by,
respectively,

$\displaystyle x>y\vee\bigvee_{1}^{n}x\neq z_{i}\vee\bigvee_{1}^{m}x>y_{i},$
(6) $\displaystyle x\geq y\vee x>z_{1}\vee\bigvee_{2}^{n}x\neq
z_{i}\vee\bigvee_{1}^{m}x>y_{i},$ (7)
$\displaystyle\phi^{\operatorname{mix}}_{2+n+m}(x,y,z_{1},\dots,z_{n},y_{1},\dots,y_{m}),$
(8) or
$\displaystyle\phi^{\operatorname{mix}}_{2+n+m}(z_{i},y,z_{1},\dots,z_{i-1},x,z_{i+1},\dots,z_{n},y_{1},\dots,y_{m})\quad\text{for
some }i\in[n].$ (9)

Note that $\phi_{j}$ implies $\phi$ for each $j\in[n+3]$. Also note that if
$\phi$ is equivalent to $\phi_{j}$ we found a contradiction to our choice of
$\phi$ because either $\lvert U_{\phi_{j}}\rvert<\lvert U_{\phi}\rvert$ or we
can replace a literal of the form $x\neq z_{j}$. This implies the existence of
tuples $t_{1},\dots,t_{n+3}\in R$ that do not satisfy
$\phi_{1},\dots,\phi_{n+3}$, respectively. We start the analysis of these
tuples with the special case $n=0$. In this case we get

  * •

a tuple $t_{1}\in R$ that does not satisfy Clause (6). Since $t_{1}\in R$ it
must satisfy $U$, and hence it satisfies $x=y\and\bigwedge_{i=1}^{m}x\leq
y_{i}$;

  * •

a tuple $t_{3}\in R$ that does not satisfy Clause (8), i.e., $t_{3}$ satisfies
$x>y\and\bigwedge_{i=1}^{m}y\leq y_{i}$.

But then there exist $\alpha,\beta\in\operatorname{Aut}(\mathbb{Q};<)$ such
that $t\coloneqq\operatorname{mix}(\alpha(t_{3}),\beta(t_{1}))$ does not
satisfy $C$. The automorphisms $\alpha$ and $\beta$ have nothing to do with
$\alpha$ and $\beta$ from the definition of $\operatorname{mix}$, and their
behaviour is illustrated in Table 1. The automorphism $\alpha$ maps the
coordinate of $t_{3}$ corresponding to $x$ in $C$ to some value greater $0$.
Likewise for the other entries of Table 1.

Therefore, $t$ does not satisfy $\phi$, contradicting the assumption that $R$
is preserved by $\operatorname{mix}$.

$\begin{array}[]{r|rrc}&\lx@intercol\hfil x\hfil\lx@intercol&\lx@intercol\hfil
y\hfil\lx@intercol&\lx@intercol\hfil y_{1\leq i\leq m}\hfil\lx@intercol\\\
\hline\cr t_{3}^{\prime}\coloneqq\alpha(t_{3})&>0&0&\geq 0\\\
t_{1}^{\prime}\coloneqq\beta(t_{1})&0&0&\geq 0\\\
\hline\cr\operatorname{mix}(t_{3}^{\prime},t_{1}^{\prime})&0&>0&\geq
0\end{array}$

Table 1. Calculation for the proof of Theorem 9 in case $n=0$.

If $n\geq 1$ the tuples are as follows:

  * •

$t_{1}$ does not satisfy Clause (6), i.e., $t_{1}$ satisfies
$x=y\and\bigwedge_{i=1}^{n}x=z_{i}\and\bigwedge_{i=1}^{m}x\leq y_{i}$;

  * •

$t_{2}$ does not satisfy Clause (7), i.e., $t_{2}$ satisfies $x<y\and
x<z_{1}\and\bigwedge_{i=2}^{n}x=z_{i}\and\bigwedge_{i=1}^{m}x\leq y_{i}$;

  * •

$t_{4}$ does not satisfy Clause (9) for $i=1$, i.e., $t_{4}$ satisfies

$z_{1}\neq y\and(x\geq z_{1}\vee x\geq y)\and\bigwedge_{j=2}^{n}(z_{j}\geq
z_{1}\vee z_{j}\geq y)\and\bigwedge_{j=1}^{m}(y_{j}\geq z_{1}\vee y_{j}\geq
y).$

One of the following cases must apply:

  1. (1)

$R$ contains $t_{4,z_{1}}$ satisfying $\psi_{z_{1}}\coloneqq y>z_{1}\and
x>z_{1}\and\bigwedge_{j=2}^{n}z_{j}\geq z_{1}\and\bigwedge_{j=1}^{m}y_{j}\geq
z_{1}$;

  2. (2)

$R$ contains $t_{4,xz_{1}}$ satisfying $\psi_{xz_{1}}\coloneqq y>z_{1}\and
x=z_{1}\and\bigwedge_{j=2}^{n}z_{j}\geq z_{1}\and\bigwedge_{j=1}^{m}y_{j}\geq
z_{1}$;

  3. (3)

$R$ contains $t_{4,y}$ satisfying $\psi_{y}\coloneqq z_{1}>y\and
x>y\and\bigwedge_{j=2}^{n}z_{j}\geq y\and\bigwedge_{j=1}^{m}y_{j}\geq y$;

  4. (4)

$R$ contains $t_{4,xy}$ satisfying $\psi_{xy}\coloneqq z_{1}>y\and
x=y\and\bigwedge_{j=2}^{n}z_{j}\geq y\and\bigwedge_{j=1}^{m}y_{j}\geq y$.

Using suitable automorphisms
$\alpha_{1},\dots,\alpha_{6}\in\operatorname{Aut}(\mathbb{Q};<)$, we deduce
the following (see Table 2):

  * •

in case (1) there is also $t^{\prime\prime\prime}_{4,y}\in R$ satisfying
$\psi_{y}$, so we are also in case (3);

  * •

in case (2) there is also $t^{\prime\prime}_{4,y}\in R$ satisfying $\psi_{y}$,
so we also in case (3);

  * •

in case (3) the tuple
$t^{*}\coloneqq\operatorname{mix}(t^{\prime}_{4,y},t^{\prime}_{1})\in R$ does
not satisfy $C$, a contradiction.

  * •

in case (4) there is also $t^{\prime\prime}_{4,z_{1}}\in R$ satisfying
$\psi_{z_{1}}$, so we are also in case (3).

Hence, in each case we reached a contradiction, which shows that the
assumption that $U_{\phi}$ is non-empty must be false.

$\begin{array}[]{r|rrrrc}&\lx@intercol\hfil
x\hfil\lx@intercol&\lx@intercol\hfil y\hfil\lx@intercol&\lx@intercol\hfil
z_{1}\hfil\lx@intercol&\lx@intercol\hfil z_{2\leq i\leq
n}\hfil\lx@intercol&\lx@intercol\hfil y_{1\leq i\leq m}\hfil\lx@intercol\\\
\hline\cr t_{2}^{\prime}\coloneqq\alpha_{2}(t_{2})&0&>0&>0&0&\geq 0\\\
t_{1}^{\prime}\coloneqq\alpha_{1}(t_{1})&0&0&0&0&\geq 0\\\ \hline\cr
t_{yz_{1}}\coloneqq\operatorname{mix}(t_{2}^{\prime},t_{1}^{\prime})&>0&0&0&>0&\geq
0\\\ \hline\cr\hline\cr
t^{\prime}_{4,xz_{1}}\coloneqq\alpha_{3}(t_{4,xz_{1}})&0&>0&0&\geq 0&\geq 0\\\
t_{yz_{1}}&>0&0&0&>0&\geq 0\\\ \hline\cr
t_{4,y}^{\prime\prime}\coloneqq\operatorname{mix}(t^{\prime}_{4,xz_{1}},t_{yz_{1}})&>0&0&>0&>0&\geq
0\\\ \hline\cr\hline\cr
t_{4,xy}^{\prime}\coloneqq\alpha_{4}(t_{4,xy})&0&0&>0&\geq 0&\geq 0\\\
t_{1}^{\prime}&0&0&0&0&\geq 0\\\ \hline\cr
t_{4,z_{1}}^{\prime\prime}\coloneqq\operatorname{mix}(t_{4,xy}^{\prime},t_{1}^{\prime})&>0&>0&0&\geq
0&\geq 0\\\ \hline\cr\hline\cr
t_{4,z_{1}}^{\prime}\coloneqq\alpha_{5}(t_{4,z_{1}})&>0&>0&0&\geq 0&\geq 0\\\
t_{yz_{1}}&>0&0&0&>0&\geq 0\\\ \hline\cr
t_{4,y}^{\prime\prime\prime}\coloneqq\operatorname{mix}(t_{4,z_{1}}^{\prime},t_{yz_{1}})&>0&0&>0&>0&\geq
0\\\ \hline\cr\hline\cr
t_{4,y}^{\prime}\coloneqq\alpha_{6}(t_{4,y})&>0&0&>0&>0&\geq 0\\\
t_{1}^{\prime}&0&0&0&0&\geq 0\\\ \hline\cr
t^{*}\coloneqq\operatorname{mix}(t_{4,y}^{\prime},t_{1}^{\prime})&0&>0&0&0&\geq
0\\\ \end{array}$

Table 2. Calculation for the proof of Lemma 9 in case $n\geq 1$.

It remains to show that conjunctions of clauses of the form (3) and (4) are
preserved by $\operatorname{mix}$. It suffices to verify that every relation
defined by a single clause of this form is preserved by $\operatorname{mix}$.
For the clauses of the form (4) we have already shown this in Lemma 8. Let $S$
be the relation defined by $\bigvee_{i=1}^{n}x\neq
z_{i}\vee\bigvee_{i=1}^{m}x>y_{i}$. Suppose for contradiction that there exist
$t_{1},t_{2}\in S$ such that
$t_{3}\coloneqq\operatorname{mix}(t_{1},t_{2})\not\in S$. Then $t_{3}$ must
satisfy $x=z_{1}=\dots=z_{n}\and\bigwedge_{i=1}^{m}x\leq y_{i}$. Therefore,
either $t_{1}$ or $t_{2}$ must satisfy $C\coloneqq x=z_{1}=\dots=z_{n}>y_{j}$
for some $j$, because $\operatorname{mix}$ is only constant on a set of pairs
if one coordinate is constant and the other coordinate is bigger or equal to
the first one. Without loss of generality we may assume that $t_{1}$ satisfies
$C$ with $j=1$.

If $t_{2}$ satisfies $C$ with some $j_{2}$ then
$\min(t_{1}[x],t_{2}[x])>\min(t_{1}[y_{1}],t_{2}[y_{j_{2}}])$ and therefore
$t_{3}[x]>\min(t_{3}[y_{1}],t_{3}[y_{j_{2}}])$, contradicting $t_{3}\not\in
R$. If $t_{2}$ satisfies $x\neq z_{j}$ for some $j$, then
$t_{3}[x]=t_{3}[z_{j}]$ implies that $\min(t_{2}[x],t_{2}[z_{j}])>t_{1}[x]$.
But then $t_{3}[x]>t_{3}[y_{1}]$, contradicting $t_{3}\not\in S$.

##  5\. Primitive Positive Definability of the Relation
$R^{\operatorname{mix}}$

In this section we prove the following theorem.

######  Theorem 10.

Let $\mathfrak{A}$ be a first-order expansion of $({\mathbb{Q}};<)$ that is
preserved by $\operatorname{pp}$. Then $R^{\operatorname{mix}}$ has a
primitive positive definition in $\mathfrak{A}$ if and only if $\mathfrak{A}$
is not preserved by ll.

The proof of this results is organised as follows. If the relation $T_{3}$ is
primitively positively definable in $\mathfrak{A}$, then so is
$R^{\operatorname{mix}}$ (Proposition 20). Otherwise, Theorem 2.5.2 implies
that $\mathfrak{A}$ is preserved by $\operatorname{mi}$, $\operatorname{mx}$,
or $\min$. It therefore suffices to treat first-order expansions
$\mathfrak{A}$ of $({\mathbb{Q}};<)$ that are

  * •

preserved by $\operatorname{mi}$ (Section 5.1),

  * •

preserved by $\operatorname{mx}$ but not by $\operatorname{mi}$ (Section 5.2),
and finally

  * •

preserved by $\min$ but not by $\operatorname{mi}$ and not by
$\operatorname{mx}$ (Section 5.3).

###  5.1. Temporal Structures Preserved by $\operatorname{mi}$

In this section we prove Theorem 10 for first-order expansions $\mathfrak{A}$
of $({\mathbb{Q}};<)$ that are preserved by $\operatorname{mi}$ (Proposition
15). For this purpose, it turns out to be highly useful to distinguish whether
the relation $\leq$ has a primitive positive definition in $\mathfrak{A}$ or
not. If yes, then the statement can be shown directly (Proposition 11).
Otherwise, $\mathfrak{A}$ is preserved by the operation $\operatorname{mix}$
from Section 4 (Proposition 13). Then the syntactic normal form for temporal
relations preserved by $\operatorname{mix}$ from Section 4 can be used to show
the statement.

######  Proposition 11.

Let $\mathfrak{A}$ be a first-order expansion of $({\mathbb{Q}};\leq)$ which
is preserved by $\operatorname{mi}$ but not by ll. Then
$R^{\operatorname{mi}}$ and $R^{\operatorname{mix}}$ have a primitive positive
definition in $\mathfrak{A}$.

######  Proof 5.1.

Let $R$ be a relation of $\mathfrak{A}$ which is not preserved by ll. As $R$
is preserved by $\operatorname{mi}$, Theorem 2.5.3 3 implies that $R$ can be
defined by a conjunction $\phi$ of clauses of the form

$x\geq y\vee\bigvee_{i=1}^{m}x>y_{i}\vee\bigvee_{i=1}^{n}x\neq z_{i}.$

We may assume that the literals $x>y_{1},\dots,x>y_{m}$ cannot be removed from
such clauses without changing the relation defined by the formula. As $R$ is
not preserved by ll, Theorem 2.5.3 5 implies that $\phi$ must contain a
conjunct $C$ of the form $x\geq
y\vee\bigvee_{i=1}^{m}x>y_{i}\vee\bigvee_{i=1}^{n}x\neq z_{i}$ where $m\geq
1$. Assume for contradiction that $\phi\wedge x=y$ implies
$x=y_{1}=\dots=y_{m}\vee\bigvee_{i=1}^{m}x>y_{i}\vee\bigvee_{i=1}^{n}x\neq
z_{i}$. Then we can replace $C$ by $x>y\vee\bigvee_{i=1}^{m}x>y_{i}\vee
x=y=y_{1}=\dots=y_{m}\vee\bigvee_{i=1}^{n}x\neq z_{i}$. However, if this is
possible for all $C$ with $m\geq 1$, then $R$ is preserved by ll,
contradiction. So we may suppose that there exists a tuple $t_{1}\in R$ and
$j\in[m]$ such that

$\displaystyle t_{1}\text{ satisfies }\quad$ $\displaystyle x=y\and
x<y_{j}\and\bigwedge_{i\neq j}x\leq y_{i}\and\bigwedge_{i=1}^{n}x=z_{i}.$

For the sake of notation, we assume that $j=1$. As the literal $x>y_{1}$ can
not be removed from $C$ without changing the relation defined by $\phi$, there
is a tuple $t_{2}\in R$ such that

$\displaystyle t_{2}\text{ satisfies }\quad$ $\displaystyle y>x\and
x>y_{1}\and\bigwedge_{i\neq j}x\leq y_{i}\and\bigwedge_{i=1}^{n}x=z_{i}.$

We may assume that $x,y,y_{1},\dots,y_{m},z_{1},\dots,z_{n}$ refer to the
first $2+m+n$ coordinates of $R$, in that order. Choose $k\in\mathbb{N}$ such
that $2+m+n+k$ is the arity of $R$ and let $u_{1},\dots,u_{k},y^{\prime},z$ be
fresh variables. The following is a primitive positive definition of
$R^{\operatorname{mi}}$ in $\mathfrak{A}$:

$\displaystyle\psi(x,y^{\prime},z)\coloneqq\;\exists$ $\displaystyle
y,y_{1},y_{2},\dots,y_{m},z_{1},\dots,z_{n},u_{1},\dots,u_{k}\Big{(}y^{\prime}\leq
y\wedge z\leq y_{1}$
$\displaystyle\wedge\,R(x,y,y_{1},\dots,y_{m},z_{1},\dots,z_{n},u_{1},\dots,u_{k})\and\bigwedge_{i=2}^{m}x\leq
y_{i}\and\bigwedge_{i=1}^{n}x=z_{i}\Big{)}$

To see this, first note that the quantifier-free part of $\psi$ implies that
$x\geq y\vee x>y_{1}$, and hence that $x\geq y^{\prime}\vee x>z$.

Conversely, choose $(a,b,c)\in R^{\operatorname{mi}}$. If $a\geq b$ then
choose $\alpha\in\operatorname{Aut}(\mathbb{Q};<)$ such that
$\alpha(t_{1}[x])=a$ and $\alpha(t_{1}[y_{1}])\geq c$ and set $y^{\prime}=b$
and $z=c$. This is possible because $t_{1}[y_{1}]>t_{1}[x]$. Then
$\alpha(t_{1})$ provides values for $y,y_{1},\dots,u_{k}$ which satisfy all
conjuncts of $\psi$: the conjunct $R(x,y,y_{1},\dots)$ is satisfied because
$\alpha(t_{1})\in R$, and for the other conjuncts this is immediate. Hence,
$\psi(a,b,c)$ holds. If $a>c$ then choose
$\alpha\in\operatorname{Aut}(\mathbb{Q};<)$ such that $\alpha(t_{2}[x])=a$,
$\alpha(t_{2}(y))\geq b$ and $\alpha(t_{2}[y_{1}])=c$, $y^{\prime}=b$ and
$z=c$. This is possible because $t_{2}[y]>t_{2}[x]>t_{2}[y_{1}]$. Then
$\alpha(t_{2})$ provides values for $y,y_{1},\dots,u_{k}$ which satisfy all
conjuncts of $\psi$: the conjunct $R(x,y,y_{1},\dots)$ is satisfied because
$\alpha(t_{2})\in R$ and for the other conjuncts this is immediate.

######  Lemma 12.

Let $\mathfrak{A}$ be a first-order expansion of $(\mathbb{Q};<)$ which is
preserved by $\operatorname{mi}$ and where $\leq$ is not primitively
positively definable. Then $\mathfrak{A}$ has a binary polymorphism $f$ such
that for all positive $a_{1},a_{2},b_{1},b_{2}\in\mathbb{Q}$

$\displaystyle 2=f(0,0)>f(0,b_{1})=1=f(0,b_{2})>f(a_{1},0)=f(a_{2},0)=0.$ (10)

######  Proof 5.2.

By Theorem 2.2 there exists a polymorphism of $\mathfrak{A}$ that does not
preserve $\leq$. There is also a binary polymorphism $g$ with this property,
by Lemma 10 in [BK09]. We can without loss of generality assume that there
exist $p_{1},p_{2},q\in\mathbb{Q}$ such that $p_{1}<p_{2}$ and
$g(p_{1},q)>g(p_{2},q)$. Define $g^{\prime}\coloneqq\gamma g(\alpha,\beta)$
with $\alpha,\beta,\gamma\in\operatorname{Aut}(\mathbb{Q};<)$ such that
$\alpha^{-1}(p_{1},p_{2})=(0,1)$, $\beta^{-1}(q)=0$, and
$\gamma(g(p_{1},q),g(p_{2},q))=(1,0)$. Then $g^{\prime}(0,0)=1$ and
$g^{\prime}(1,0)=0$. Defining $g^{\prime\prime}(x,y)\coloneqq
g^{\prime}(\operatorname{mi}(x,y),y)$ we get
$g^{\prime\prime}(0,0)=g^{\prime}(0,0)=1$ and for all $c>0$ we get
$g^{\prime\prime}(c,0)=g^{\prime}(1,0)=0$ and
$g^{\prime\prime}(0,c)=g^{\prime}(2,c)=:d>1$. Defining
$f(x,y)\coloneqq\operatorname{mi}(g^{\prime\prime}(y,x),g^{\prime\prime}(x,y))$
we get $f(0,0)=\operatorname{mi}(1,1)=3$, and for all $c>0$ we get
$f(c,0)=\operatorname{mi}(d,0)=1$, and $f(0,c)=\operatorname{mi}(0,d)=2$. As
$x\mapsto x-1$ is in $\operatorname{Aut}(\mathfrak{A})$, the function
$(x,y)\mapsto f(x,y)-1$ satisfies (10).

The following proposition is similar to Proposition 10.5.13 in [Bod12].

######  Proposition 13.

Let $\mathfrak{A}$ be a temporal structure preserved by $\operatorname{pp}$
such that $\leq$ does not have a primitive positive definition in
$\mathfrak{A}$. Then $\mathfrak{A}$ is preserved by $\operatorname{mix}$.

######  Proof 5.3.

Let $R$ be a $k$-ary relation of $\mathfrak{A}$ and $r,s\in R$. We have to
show that $t\coloneqq\operatorname{mix}(r,s)$ is in $R$. Let
$\alpha,\beta,\gamma\in\operatorname{End}(\mathbb{Q};<)$ be from the
definition of $\operatorname{mix}$. Let $v_{1}<\dots<v_{l}$ be the shortest
sequence of rational numbers such that
$t_{i}\in\bigcup_{j\in[l]}\\!\left\\{\alpha(v_{j}),\beta(v_{j}),\gamma(v_{j})\right\\}$
for every $i\in[k]$. For every $j\in[l]$ we define

$M_{j}\coloneqq\big{\\{}i\in[k]\mid
t_{i}\in\\!\left\\{\alpha(v_{j}),\beta(v_{j}),\gamma(v_{j})\right\\}\big{\\}}.$

Observe that $M_{1},\dots,M_{l}$ is a partition of $[k]$ and therefore defines
a partition on $\\{t_{1},\dotsc,t_{k}\\}$. Furthermore, for each $i\in M_{j}$
either $v_{j}=r_{i}\leq s_{i}$ or $v_{j}=s_{i}\leq r_{i}$ holds. This defines
a partition of $M_{j}$ into three parts:

$\displaystyle M_{j}^{\alpha}$ $\displaystyle\coloneqq\\{i\in M_{j}\mid
v_{j}=r_{j}<s_{j}\\},$ $\displaystyle M_{j}^{\beta}$
$\displaystyle\coloneqq\\{i\in M_{j}\mid v_{j}=r_{j}=s_{j}\\},$
$\displaystyle\text{and }\quad M_{j}^{\gamma}$ $\displaystyle\coloneqq\\{i\in
M_{j}\mid v_{j}=s_{j}<r_{j}\\}.$

Let $\alpha_{1},\dots,\alpha_{l}\in\operatorname{Aut}(\mathbb{Q};<)$ be such
that $\alpha_{j}(v_{j})=0$ for all $j\in[l]$. By Lemma 12 there is a binary
$f\in\operatorname{Pol}(\mathfrak{A})$ satisfying (10). For each $j\in[l]$ we
define

$u^{j}\coloneqq\operatorname{pp}\big{(}f(\alpha_{j}r,\alpha_{j}s),\operatorname{pp}(\alpha_{j}s,\alpha_{j}r)\big{)}$

It is easy to verify that for all $i\in M_{j}$ and $w,w^{\prime}>0$

$\displaystyle\text{if }i\in M^{\alpha}_{j}\text{ then }$ $\displaystyle
u^{j}_{i}=\operatorname{pp}(f(0,w),\operatorname{pp}(w^{\prime},0))=\operatorname{pp}(1,\operatorname{pp}(1,0)),$
$\displaystyle\text{if }i\in M^{\beta}_{j}\text{ then }$ $\displaystyle
u^{j}_{i}=\operatorname{pp}(f(0,0),\operatorname{pp}(0,0))=\operatorname{pp}(2,\operatorname{pp}(0,0)),$
$\displaystyle\text{and if }i\in M^{\gamma}_{j}\text{ then }$ $\displaystyle
u^{j}_{i}=\operatorname{pp}(f(w,0),\operatorname{pp}(0,w^{\prime}))=\operatorname{pp}(0,0).$

In particular, $u^{j}$ is constant on each of $M_{j}^{\alpha}$,
$M_{j}^{\beta}$, $M_{j}^{\gamma}$ and $u^{j}_{i}>u^{j}_{i^{\prime}}$ for $i\in
M^{\alpha}_{j}$ and $i^{\prime}\in M^{\beta}_{j}$. We apply $f$ again to
obtain $z^{j}\coloneqq f(\alpha_{j}r,\beta_{j}u^{j})$ where
$\beta_{j}\in\operatorname{Aut}(\mathbb{Q};<)$ is such that
$\beta_{j}(\operatorname{pp}(2,\operatorname{pp}(0,0)))=0$. Then we get for
all $i\in M_{j}$ and $w>0$ that

$\displaystyle\text{if }i\in M^{\alpha}_{j}\text{ then }$ $\displaystyle
z^{j}_{i}=f(0,w)=1,$ $\displaystyle\text{if }i\in M^{\beta}_{j}\text{ then }$
$\displaystyle z^{j}_{i}=f(0,0)=2,$ $\displaystyle\text{and if }i\in
M^{\gamma}_{j}\text{ then }$ $\displaystyle
z^{j}_{i}=f(w,e)<f(0,e^{\prime})=0\text{ for some }e^{\prime}<e<0.$

Thus, we found $z^{1},\dots,z^{l}\in R$ such that for all $i\in
M_{j}^{\beta}$, $i^{\prime}\in M_{j}^{\alpha}$, and $i^{\prime\prime}\in
M_{j}^{\gamma}$ we have
$z^{j}_{i}>z^{j}_{i^{\prime}}>z^{j}_{i^{\prime\prime}}$. Take any
$j,j^{\prime}\in[l]$ such that $j<j^{\prime}$ and choose $i\in M_{j}^{\beta}$
and $i^{\prime}\in M_{j^{\prime}}$. Then
$v_{j}=r_{i}=s_{i}<v_{j^{\prime}}=\min(s_{i^{\prime}},r_{i^{\prime}})$ and
therefore $z^{j}_{i}<z^{j^{\prime}}_{i^{\prime}}$ because $f$,
$\operatorname{pp}$, and all automorphisms preserve $<$. Therefore, we can
apply Lemma 10.5.3 in [Bod12] to $z^{1},\dots,z^{l}$ which yields the
existence of a tuple $t^{*}\in R$ with satisfies
$t^{*}_{i}<t^{*}_{i^{\prime}}$ if and only if there exists $j<j^{\prime}$ such
that $i\in M_{j},i^{\prime}\in M_{j^{\prime}}$, and
$z^{j}_{i}<z^{j^{\prime}}_{i^{\prime}}$. However, this is the same ordering
that $t$ satisfies and hence, $t\in R$.

######  Proposition 14.

Let $\mathfrak{A}$ be a first-order expansion of $({\mathbb{Q}};<)$ preserved
by $\operatorname{mix}$ but not by ll. Then $R^{\operatorname{mix}}$ has a
primitive positive definition in $\mathfrak{A}$.

######  Proof 5.4.

Let $R$ be a relation in $\mathfrak{A}$ that is not preserved by ll. Lemma 9
implies that $R$ can be defined by conjunctions of clauses the form (3) and
(4). As $R$ is not preserved by ll, any such definition must include at least
on clause of the form (4). Consider a clause of the form (4), written in CNF
$\phi^{\operatorname{mix}}_{n}=C_{x}\and C_{y}$ with

$\displaystyle C_{x}$ $\displaystyle\coloneqq\left(x\geq
y\vee\bigvee_{i=1}^{n}x>z_{i}\right)$ $\displaystyle C_{y}$
$\displaystyle\coloneqq\left(y\geq x\vee\bigvee_{i=1}^{n}y>z_{i}\right).$

Claim 1. Suppose that the literal $x\geq y$ can be replaced by $x>y$ in
$C_{x}$ without changing the relation defined by $\phi$. Then we can also
replace the literal $y\geq x$ by $y>x$ in $C_{y}$ without changing the
relation defined by $\phi$.

The assumption implies that if $x\geq y$ is satisfied by a tuple $t\in R$ then
either $t$ satisfies $x>y$, or $t$ satisfies $x=y$ and there exists $i$ such
that $t$ satisfies $x>z_{i}$. In the first case $t$ satisfies $y>z_{j}$ (in
order to satisfy $C_{y}$) and hence $t$ still satisfies $\phi$ after replacing
$y\geq x$ by $y>x$ in $C_{y}$. In the second case, $t$ satisfies $y=x>z_{i}$
and thus again satisfies $C_{y}$ after the same replacement.

Claim 2. Suppose that for some $i\in[n]$, the literal $x>z_{i}$ can be removed
from $C_{x}$ without changing the relation defined by $\phi$. Then $y>z_{i}$
can be removed from $C_{y}$ without changing the relation defined by $\phi$.

Case 1: All tuples $t\in R$ satisfy $x\leq z_{i}$, i.e., $x>z_{i}$ is never
true. If there is $t\in R$ such that $t$ satisfies $y>z_{i}$, then $t$ also
satisfies $y>x$. Hence, we can also remove $y>z_{i}$ from $C_{y}$ without
altering the relation defined by the formula.

$\begin{array}[]{r|rrrr}&\lx@intercol\hfil
x\hfil\lx@intercol&\lx@intercol\hfil y\hfil\lx@intercol&\lx@intercol\hfil
z_{i}\hfil\lx@intercol&\lx@intercol\hfil z_{j\neq i}\hfil\lx@intercol\\\
\hline\cr t^{\prime}\coloneqq\alpha_{1}(t_{y,i})&2&1&0&\geq 1\\\
t_{c}^{\prime}\coloneqq\alpha_{2}(t_{c})&1&1&\geq 1&\geq 1\\\
\hline\cr\operatorname{mix}(t^{\prime},t_{c}^{\prime})&3&5&1&\geq
3\end{array}$

Table 3. Calculation for Claim 2 (Case 2) in the proof of Proposition 14.

Case 2: There exists $t\in R$ where $x>z_{i}$ holds. Suppose for contradiction
that there exists a tuple $t_{y,i}\in R$ which does not satisfy $C_{y}$ after
deletion of $y>z_{i}$ in $C_{y}$. Then

$t_{y,i}\text{ satisfies }x>y\and y>z_{i}\and\bigwedge_{j\neq i}z_{j}\geq y.$

As we already know that literal replacement can be applied to $C$ (Claim 1),
we can assume that no literal in $\phi$ can be replaced. Therefore, there
exists $t_{c}\in R$ such that

$t_{c}\text{ satisfies }\quad x=y\wedge\bigwedge_{i=1}^{n}x\leq z_{i}.$

Then there exist $\alpha_{1},\alpha_{2}\in\operatorname{Aut}(\mathbb{Q};<)$
such that $\operatorname{mix}(t_{y,i},t_{c})$ satisfies $y>x\and
x>z_{i}\and\bigwedge_{j\neq i}z_{j}\geq x$ (see Table 3), contradicting the
assumption that we can remove $x>z_{i}$.

Claims 1 and 2 imply that we may assume without loss of generality that the
literal $x\geq y$ cannot be replaced by $x>y$, that the literal $x>z_{i}$
cannot be removed from $C_{x}$ and, symmetrically, that $y>z_{i}$ cannot be
removed from $C_{y}$ without changing the relation defined by $\phi$. Hence,
there are $t_{c},t_{x,i},t_{y,i}\in R$ such that for all $1\leq i\leq n$

$\displaystyle t_{c}\text{ satisfies }\quad$ $\displaystyle
x=y\wedge\bigwedge_{i=1}^{n}x\leq z_{i},$ $\displaystyle t_{x,i}\text{
satisfies }\quad$ $\displaystyle z_{i}<x<y\and\bigwedge_{j\neq i}x\leq z_{j},$
and $t_{y,i}$ satisfies $\displaystyle z_{i}<y<x\and\bigwedge_{j\neq i}y\leq
z_{j}.$

Now we apply automorphisms and $\operatorname{mix}$ to $t_{c}$, $t_{x,i}$, and
$t_{y,i}$ to prove that $R$ contains tuples with more specific properties. We
first prove that $R$ must contain a tuple $t_{c}^{*}$ satisfying

$\displaystyle x=y\and\bigwedge_{i\in[n]}x<z_{i}.$ (11)

Choose $t_{c}$ as above such that the number $m$ of indices $j\in[n]$ such
that $t_{c}$ satisfies $x<z_{j}$ is maximal. If $m=n$, then $t_{c}$ satisfies
(11) and hence satisfies the requirements for $t_{c}^{*}$. Otherwise, there
exists $i\in[n]$ such that $t_{c}$ satisfies $x=z_{i}$; this case will lead to
a contradiction. Choose automorphisms
$\alpha_{1},\alpha_{2}\in\operatorname{Aut}(\mathbb{Q};<)$ such that
$\alpha_{1}(t_{c})$ satisfies $x=0$ and $\alpha_{2}(t_{x,i})$ satisfies
$z_{i}=0$. Then

$t_{c}^{\prime}\coloneqq\operatorname{mix}(\alpha_{1}(t_{c}),\alpha_{2}(t_{x,i}))\in
R$

satisfies $z_{i}>x$ and $x=y$ (see Table 4). Moreover, if $k\in[n]$ is such
that $\alpha_{1}(t_{c})$ satisfies $x<z_{k}$ then $t_{c}^{\prime}$ satisfies
$x<z_{k}$ as well. Hence, the number $m$ of indices $j\in[n]$ such that
$t_{c}^{\prime}$ satisfies $x<z_{j}$ is at least $m+1$, a contradiction to the
choice of $t_{c}$.

$\begin{array}[]{r|rrrr}&\lx@intercol\hfil
x\hfil\lx@intercol&\lx@intercol\hfil y\hfil\lx@intercol&\lx@intercol\hfil
z_{k}\hfil\lx@intercol&\lx@intercol\hfil z_{i}\hfil\lx@intercol\\\
\hline\cr\alpha_{1}(t_{c})&0&0&>0&0\\\ \alpha_{2}(t_{x,i})&1&2&\geq 1&0\\\
\hline\cr
t_{c}^{\prime}\coloneqq\operatorname{mix}(\alpha_{1}(t_{c}),\alpha_{2}(t_{x,i}))&1&1&>2&2\end{array}$

Table 4. Calculation of $t_{c}^{\prime}$ in the proof of Proposition 14.

Our next goal is to prove the existence of $t_{x,i}^{*},t_{y,i}^{*}\in R$ such
that

$\displaystyle t_{x,i}^{*}\text{ satisfies }\quad$ $\displaystyle
z_{i}<x<y\and\bigwedge_{j\neq i}y<z_{j}$ $\displaystyle\text{and }\quad
t_{y,i}^{*}\text{ satisfies }\quad$ $\displaystyle
z_{i}<y<x\and\bigwedge_{j\neq i}x<z_{j}.$

Using $t_{c}^{*}$ and appropriately chosen
$\alpha_{1},\dots,\alpha_{5}\in\operatorname{Aut}(\mathbb{Q};<)$ we may first
produce $h_{x,i},h_{y,i}\in R$ and combine them to get
$t_{x,i}^{*},t_{y,i}^{*}\in R$ as shown in Table 5.

$\begin{array}[]{r|rrrr}&\lx@intercol\hfil
x\hfil\lx@intercol&\lx@intercol\hfil y\hfil\lx@intercol&\lx@intercol\hfil
z_{i}\hfil\lx@intercol&\lx@intercol\hfil z_{j\neq i}\hfil\lx@intercol\\\
\hline\cr t_{x,i}^{\prime}\coloneqq\alpha_{1}(t_{x,i})&1&2&0&\geq 1\\\
{t_{c}^{*}}^{\prime}\coloneqq\alpha_{2}(t_{c}^{*})&1&1&>1&>1\\\ \hline\cr
h_{x,i}\coloneqq\operatorname{mix}(t_{x,i}^{\prime},{t_{c}^{*}}^{\prime})&5&3&1&\geq
4\\\ \hline\cr\hline\cr
t_{y,i}^{\prime}\coloneqq\alpha_{3}(t_{y,i})&2&1&0&\geq 1\\\
{t_{c}^{*}}^{\prime}&1&1&>1&>1\\\ \hline\cr
h_{y,i}\coloneqq\operatorname{mix}(t_{y,i}^{\prime},{t_{c}^{*}}^{\prime})&3&5&1&\geq
4\\\ \hline\cr\hline\cr
h_{x,i}^{\prime}\coloneqq\alpha_{4}(h_{x,i})&3&1&0&\geq 2\\\
h_{y,i}^{\prime}\coloneqq\alpha_{5}(h_{y,i})&1&3&0&\geq 2\\\ \hline\cr
t_{x,i}^{*}\coloneqq\operatorname{mix}(h^{\prime}_{x,i},h^{\prime}_{y,i})&3&4&2&\geq
6\\\ \hline\cr\hline\cr h_{y,i}^{\prime}&1&3&0&\geq 2\\\
h_{x,i}^{\prime}&3&1&0&\geq 2\\\ \hline\cr
t_{y,i}^{*}\coloneqq\operatorname{mix}(h_{y,i}^{\prime},h_{x,i}^{\prime})&4&3&2&\geq
6\\\ \end{array}$

Table 5. Calculation of $t_{x,i}^{*}$ and $t_{y,i}^{*}$ in the proof of
Proposition 14.

Without loss of generality we may assume that $x,y,z_{1},\dots,z_{n}$
correspond to the first $n+2$ coordinates in $R$. Let $u_{1},\dots,u_{m}$ be
fresh variables such that the arity of $R$ is $2+n+m$ and define

$\displaystyle\psi(x,y,\bar{z},\bar{u})$ $\displaystyle\coloneqq
R(x,y,\bar{z},\bar{u})\wedge\bigwedge_{i=2}^{n}x<z_{i}\and y<z_{i}$
$\displaystyle\text{ and }\quad\psi^{\prime}(x,y,z)$
$\displaystyle\coloneqq\exists
z_{1},\dots,z_{k},u_{1},\dots,u_{m}\big{(}\psi(x,y,\bar{z},\bar{u})\and
z<z_{1}\big{)}.$

To show that $\psi^{\prime}$ defines $R^{\operatorname{mix}}$, first notice
that $t_{x,1}^{*}$, $t_{y,1}^{*}$, and $t_{c}^{*}$ satisfy $\psi$ and that
$\psi$ implies $x\geq y\vee x>z_{1}$ and $y\geq x\vee y>z_{1}$ because all
disjuncts of $C_{x}$ and $C_{y}$ involving $z_{2},\dotsc,z_{n}$ do not hold.
This in turn implies that the set of orbits of $(x,y,z_{1})$ in tuples that
satisfy $\psi$ is contained in $R^{\operatorname{mix}}$. It follows that if
$(a,b,c)$ satisfies $\psi^{\prime}$, then either $a=b$, or there exists
$z_{1}$ such that $c<z_{1}<\min(a,b)$, so $(a,b,c)\in R^{\operatorname{mix}}$.

Conversely, let $(a,b,c)$ be in $R^{\operatorname{mix}}$. If $a=b$ and we may
choose $\alpha\in\operatorname{Aut}(\mathfrak{A})$ such that
$\alpha(t_{c}^{*}[x])=a$ and $\alpha(t_{c}^{*}[z_{1}])>c$, in which case
$\alpha(t_{c}^{*})$ yields values for $z_{1},\dots,u_{m}$ which prove that
$(a,b,c)$ satisfies $\psi^{\prime}$. If $c<a<b$ then there exists
$\alpha\in\operatorname{Aut}(\mathfrak{A})$ such that
$\alpha(t_{x,1}^{*})[x]=a$, $\alpha(t_{x,1}^{*})[y]=b$ and
$\alpha(t_{x,1}^{*})[z_{1}]>c$. Hence, $\alpha(t_{x,1}^{*})$ shows that
$(a,b,c)$ satisfies $\psi^{\prime}$. The argument for $c<b<a$ works with
$t_{y,1}^{*}$ in an analogous way.

Now we are ready to prove the main result of this subsection.

######  Proposition 15.

Let $\mathfrak{A}$ be a first-order expansion of $({\mathbb{Q}};<)$ which is
preserved by $\operatorname{mi}$, but not by ll. Then $R^{\operatorname{mix}}$
has a primitive positive definition in $\mathfrak{A}$.

######  Proof 5.5.

If $\leq$ is primitively positively definable in $\mathfrak{A}$, then
Proposition 11 yields that $R^{\operatorname{mix}}$ is primitively positively
definable in $\mathfrak{A}$. If $\leq$ is not primitively positively definable
in $\mathfrak{A}$ then Proposition 13 yields that $\mathfrak{A}$ is preserved
by $\operatorname{mix}$. In this case Proposition 14 implies that
$R^{\operatorname{mix}}$ is primitively positively definable.

###  5.2. Temporal Structures Preserved by $\operatorname{mx}$

In this section we consider first-order expansions of $({\mathbb{Q}};<)$ that
are preserved by $\operatorname{mx}$. We distinguish the cases whether $X$ is
primitively positively definable in $\mathfrak{A}$ or not. Theorem 2.5.1
implies that if $X$ is not primitively positively definable in $\mathfrak{A}$,
then $\mathfrak{A}$ is also preserved by $\min$. So we first consider the
situation that $\mathfrak{A}$ is preserved by both $\operatorname{mx}$ and
$\min$. For $R\subseteq\mathbb{Q}^{n}$, $t=(t_{1},\dots,t_{n})\in R$ and
$I=\\{i_{1},\dots,i_{l}\\}\subseteq[n]$ we write $\pi_{I}(t)$ for the tuple
$(t_{i_{1}},\dots,t_{i_{l}})$ where $i_{1}<i_{2}<\dots<i_{l}$ and $\pi_{I}(R)$
for the relation $\\!\left\\{\pi_{I}(t)\mid t\in R\right\\}$.

######  Proposition 16.

Let $\mathfrak{A}$ be a first-order expansion of $({\mathbb{Q}};<)$ that is
preserved by $\operatorname{mx}$ and $\min$. Then $\mathfrak{A}$ is preserved
by $\operatorname{mi}$.

######  Proof 5.6.

Let $R$ be a relation in $\mathfrak{A}$. The proof proceeds by induction on
the arity $n$ of $R$. For $n=1$, or if $R$ is empty, there is nothing to be
shown. Suppose that the statement holds for all relations of arity less than
$n$ and that $R$ is not empty. For every $I\subseteq[n]$ we fix a homogeneous
system $A^{R}_{I}x=0$ of Boolean linear equations with solution space
$\chi_{0}(\pi_{I}(R))$, which exists due to case 4 in Theorem 2.5.3. As $R$ is
preserved by $\min$, the Boolean maximum operation preserves
$\chi_{0}(\pi_{I}(R))$. Furthermore, the solution space of a system of
homogeneous linear equations over $\operatorname{GF}_{2}$ is also preserved by
the operation $(x,y,z)\mapsto x+y+z\mod 2$ (because it is a subspace of
$\operatorname{GF}_{2}^{3}$), we get that $\chi_{0}(\pi_{I}(R))$ is also
preserved by $\min$ because $\min(x,y)=\max(x,y)+x+y\mod 2$. For every pair
$t,t^{\prime}\in R$ we want to show that $\operatorname{mi}(t,t^{\prime})\in
R$. If $\min(t)=\min(t^{\prime})$, we consider the set
$S\coloneqq\\!\left\\{i\in[n]\mid\chi(t)[i]=\chi(t^{\prime})[i]=1\right\\}$
and distinguish two cases:

  1. (1)

If $S\neq\emptyset$ then
$\chi(\operatorname{mi}(t,t^{\prime}))=\min(\chi(t),\chi(t^{\prime}))\in\chi(R)$.

  2. (2)

If $S=\emptyset$, then
$\chi(\operatorname{mi}(t,t^{\prime}))=\chi(t^{\prime})\in\chi(R)$.

If $\min(t)\neq\min(t^{\prime})$, then
$\chi(\operatorname{mi}(t,t^{\prime}))\in\\{\chi(t),\chi(t^{\prime})\\}\subseteq\chi(R)$.

Thus, there exists a tuple $c\in R$ with
$\chi(c)=\chi(\operatorname{mi}(t,t^{\prime}))$. Let
$I\coloneqq\\!\left\\{i\mid\chi(c)[i]=1\right\\}$ and observe that $I$ is non-
empty. By induction hypothesis, the statement holds for $\pi_{[n]\setminus
I}(R)$ and we have $\pi_{[n]\setminus
I}(\operatorname{mi}(t,t^{\prime}))=\operatorname{mi}(\pi_{[n]\setminus
I}(t),\pi_{[n]\setminus I}(t^{\prime}))\in\pi_{[n]\setminus I}(R)$. Therefore,
there exists $r\in R$ with $\pi_{[n]\setminus
I}(\operatorname{mi}(t,t^{\prime}))=\pi_{[n]\setminus I}(r)$. We can apply an
automorphism of $(\mathbb{Q};<)$ to $r$ to obtain a tuple $r^{\prime}\in R$
where all entries are positive. We can also apply an automorphism to $c$ to
obtain a tuple $c^{\prime}\in R$ so that its minimal entries are $0$ and for
every other entry $i\in[n]\setminus I$ it holds that
$c^{\prime}[i]>r^{\prime}[i]$. Then $\operatorname{mx}(c^{\prime},r^{\prime})$
yields a tuple in $R$ which is minimal at the coordinates in $I$ and all other
coordinates are ordered like the coordinates in $r$, i.e.,
$\operatorname{mx}(c^{\prime},r^{\prime})$ is equal to
$\operatorname{mi}(t,t^{\prime})$ under an automorphism. Hence,
$\operatorname{mi}(t,t^{\prime})\in R$, i.e., $R$ is preserved by
$\operatorname{mi}$.

######  Proposition 17.

Let $\mathfrak{A}$ be a first-order expansion of $({\mathbb{Q}};<)$ that is
preserved by $\operatorname{mx}$ but not by $\operatorname{mi}$. Then
$R^{\operatorname{mix}}$ is primitively positively definable in
$\mathfrak{A}$.

######  Proof 5.7.

First suppose that $X$ is primitively positively definable in $\mathfrak{A}$.
It is easy to check that $\exists h\big{(}X(z,z,h)\and X(x,y,h)\big{)}$
primitively positively defines $R^{\operatorname{mix}}(x,y,z)$, and hence
$R^{\operatorname{mix}}$ is primitively positively definable in
$\mathfrak{A}$. Otherwise, if $X$ is not primitively positively definable in
$\mathfrak{A}$, then Theorem 2.5.1 implies that $\mathfrak{A}$ is also
preserved by $\min$, and hence by $\operatorname{mi}$ by Proposition 16, which
contradicts our assumptions.

###  5.3. Temporal Structures Preserved by $\min$

This section treats first-order expansions of $({\mathbb{Q}};<)$ that are
preserved by $\min$ but not by $\operatorname{mi}$ and $\operatorname{mx}$. We
first show that we may assume that $\leq$ has a primitive positive definition
in $\mathfrak{A}$.

######  Lemma 18.

Let $\mathfrak{A}$ be a first-order expansion of $({\mathbb{Q}};<)$ which is
preserved by $\operatorname{pp}$ and does not admit a primitive positive
definition of $\leq$. Then $\mathfrak{A}$ is preserved by $\operatorname{mi}$
or by $\operatorname{mx}$.

######  Proof 5.8.

By Theorem 2.2 there exists an $f\in\operatorname{Pol}(\mathfrak{A})$ that
does not preserve $\leq$. As $\leq$ is a union of two orbits of
$\operatorname{Aut}(\mathbb{Q};<)=\operatorname{Aut}(\mathfrak{A})$, there is
a binary polymorphism $f^{\prime}$ of $\mathfrak{A}$ that does not preserve
$\leq$ by Lemma 10 in [BK09]. As $\mathfrak{A}$ is also preserved by
$\operatorname{pp}$, Lemma 35 in [BK09] implies that $\mathfrak{A}$ is
preserved by an operation providing _min-intersection closure_ or _min-xor
closure_. Then $\mathfrak{A}$ is preserved by $\operatorname{mi}$ or by
$\operatorname{mx}$ by Proposition 27 and Proposition 29 in [BK09],
respectively.

######  Proposition 19.

Let $\mathfrak{A}$ be a first-order expansion of $({\mathbb{Q}};<)$ preserved
by $\min$ but not by $\operatorname{mi}$ and not by $\operatorname{mx}$. Then
$R^{\min}_{\leq}$, $R^{\operatorname{mi}}$, and $R^{\operatorname{mix}}$ have
a primitive positive definition in $\mathfrak{A}$.

######  Proof 5.9.

Let $R$ be a relation of $\mathfrak{A}$ that is not preserved by
$\operatorname{mi}$ and let $n$ be the arity of $R$. As $R$ is preserved by
$\min$, it is definable by a conjunction $\phi$ of formulas where each
conjunct is of the form as described in Theorem 2.5.3 2. Furthermore, there
must be a clause $C$ in $\phi$ that is not preserved by $\operatorname{mi}$.
By Theorem 2.5.3 3 $C$ is of the form

$x>x_{1}\vee\cdots\vee x>x_{\ell}\vee x\geq y_{1}\vee\cdots\vee x\geq y_{k}$

with $k>1$. Furthermore, we can assume that $\phi$ is in reduced CNF. Hence,
there exist tuples $t_{1},t_{2}\in R$ witnessing that the literals $x\geq
y_{1}$ and $x\geq y_{2}$ cannot be replaced by $x>y_{1}$ and by $x>y_{2}$,
respectively, i.e.,

$\displaystyle t_{1}\text{ satisfies }\quad$ $\displaystyle x=y_{1}\and
x<y_{2}\and\bigwedge_{i=1}^{\ell}x\leq x_{i}\and\bigwedge_{i=3}^{k}x<y_{i},$
$\displaystyle t_{2}\text{ satisfies }\quad$ $\displaystyle x<y_{1}\and
x=y_{2}\and\bigwedge_{i=1}^{\ell}x\leq x_{i}\and\bigwedge_{i=3}^{k}x<y_{i}.$

Let $z_{1},\dots,z_{m}$ be all the variables from $\phi$ that do not occur in
$C$. Without loss of generality, we may assume that the coordinates of $R$ are
in the following order: $x,x_{1},\dots,x_{\ell},y_{1},\dots,y_{k}$,
$z_{1},\dots,z_{m}$. As $\mathfrak{A}$ is not preserved by
$\operatorname{mx}$, Lemma 18 implies that $\leq$ has a primitive positive
definition in $\mathfrak{A}$; so we may assume that $\leq$ is among the
relations of $\mathfrak{A}$. We claim that $R^{\min}_{\leq}$ can be defined
over $\mathfrak{A}$ by the primitive positive formula $\phi(x,u,v)$ given as
follows.

$\displaystyle\exists
z_{1},\dots,z_{m},x_{1},\dots,x_{\ell},y_{1},\dots,y_{k}$
$\displaystyle\Big{(}R(x,x_{1},\dots,x_{\ell},y_{1},\dots,y_{k},z_{1},\dots,z_{m})$
$\displaystyle\wedge y_{1}\geq u\and y_{2}\geq
v\wedge\bigwedge_{i=1}^{\ell}x\leq
x_{i}\wedge\bigwedge_{i=3}^{k}x<y_{i}\Big{)}$

To prove the claim, let $(a,b,c)\in R^{\min}_{\leq}$. Assume that $a\geq b$.
There exists $\alpha\in\operatorname{Aut}(\mathfrak{A})$ such that
$t_{1}^{\prime}\coloneqq\alpha(t_{1})$ satisfies $t_{1}^{\prime}[x]=a$ and
$t_{1}^{\prime}[y_{2}]>\max(a,c)$. Now we extend $t_{1}^{\prime}$ by two
coordinates, named $u$ and $v$ such that $t_{1}^{\prime}[u]=b$ and
$t_{1}^{\prime}[v]=c$. Then
$\pi_{\\!\left\\{x,u,v\right\\}}(t_{1}^{\prime})=(a,b,c)$ and $t_{1}^{\prime}$
satisfies the quantifier-free part of $\phi$. Therefore, $\phi(a,b,c)$ holds.
The case where $a\geq c$ holds is handled analogously using $t_{2}$ instead of
$t_{1}$.

Now suppose that $(a,b,c)$ satisfies $\phi(x,u,v)$ and let $t^{*}$ be any
tuple which satisfies the quantifier-free part of $\phi$ such that
$\pi_{\\!\left\\{x,u,v\right\\}}(t^{*})=(a,b,c)$. Then $t^{*}$ satisfies $C$,
and hence $t^{*}$ satisfies $x\geq y_{1}\vee x\geq y_{2}$. Therefore, $t^{*}$
satisfies $x\geq u\vee x\geq v$, i.e., $t\in R^{\min}_{\leq}$. It is easy to
check that the formula $\exists h\,(\phi(x,h,y)\wedge h>z)$ is a primitive
positive definition of $R^{\operatorname{mi}}$ in $\mathfrak{A}$. Therefore,
$R^{\operatorname{mix}}$ is primitively positively definable in $\mathfrak{A}$
as well (see note below Theorem 2.5.3).

###  5.4. Definability Dichotomy

In this section we prove Theorem 10, following the strategy outlined earlier,
and subsequently we prove Theorem 3

######  Proposition 20.

A temporal relation has a primitive positive definition in
$(\mathbb{Q};T_{3})$ if and only if it is preserved by $\operatorname{pp}$.

######  Proof 5.10.

By Theorem 2.6, it suffices to prove that the relations $\neq$,
$R^{\min}_{\leq}$, and $S^{\operatorname{mi}}$ are primitively positively
definable in $(\mathbb{Q};T_{3})$. Clearly, $x\leq y$ is equivalent to
$\exists z.\,T_{3}(x,y,z)$ and $x\neq y$ is equivalent to $\exists
z.\,T_{3}(z,x,y)$. We claim that the following primitive positive formula
defines $R^{\min}_{\leq}$ in $(\mathbb{Q};T_{3},\leq)$.

$\displaystyle\phi(x,y,z)\coloneqq\exists
x^{\prime},y^{\prime},z^{\prime}\big{(}T_{3}(x^{\prime},y^{\prime},z^{\prime})\and
x\geq x^{\prime}\and y\leq y^{\prime}\and z\leq z^{\prime}\big{)}$

Suppose that $(a,b,c)\in R^{\min}_{\leq}$ holds. By the symmetry of the second
and third argument in $R^{\min}_{\leq}$ we may assume that $a\geq b$ holds.
Choose $a^{\prime}=b^{\prime}$ such that $b\leq a^{\prime}=b^{\prime}\leq a$
holds and $c^{\prime}>\max(a^{\prime},b^{\prime},c)$. Then
$T_{3}(a^{\prime},b^{\prime},c^{\prime})\and a\geq a^{\prime}\and b\leq
b^{\prime}\and c<c^{\prime}$ holds and therefore $(a,b,c)$ satisfies $\phi$.
For the converse direction, suppose for contradiction that $(a,b,c)$ is not in
$R^{\min}_{\leq}$ but $\phi(a,b,c)$ holds. Then we have $a<b\and a<c$. The
quantifier-free part of $\phi$ implies $x^{\prime}\leq a<b\leq y^{\prime}$ and
therefore $x^{\prime}=z^{\prime}<y^{\prime}$. However, $c\leq
z^{\prime}=x^{\prime}\leq a$ follows, contradicting $a<c$.

Finally, we claim that the formula

$\psi(x,y,z)\coloneqq\exists u,v\big{(}T_{3}(x,u,v)\wedge(u\neq y)\wedge(v\geq
z)\big{)}$

defines $S^{\operatorname{mi}}$. If $(a,b,c)$ satisfies $\psi$ we either have
$a=u\neq b$ or $a=v\geq c$. Therefore $(a,b,c)$ satisfies
$S^{\operatorname{mi}}$. If $(a,b,c)$ satisfies $S^{\operatorname{mi}}$ we
have two cases. If $a\neq b$, we choose $u=a$ and $v>\max(c,a)$. Then $b\neq
a=u<v$ and $v>c$ holds and therefore $\psi(a,b,c)$ holds. If $c\leq a$ holds,
then we choose $v=a$ and $u>\max(a,b)$. Then $c\leq a=v<u\neq b$ holds, i.e.,
$\psi(a,b,c)$ holds.

######  Proof 5.11 (Proof of Theorem 10).

$\Longrightarrow$: Suppose that $R^{\operatorname{mix}}$ has a primitive
positive definition in $\mathfrak{A}$. Then $\mathfrak{A}$ is not preserved by
ll because $R^{\operatorname{mix}}$ is not preserved by $\operatorname{lex}$:
consider for instance $\operatorname{lex}((0,0,1),(2,3,0))$, which is in the
same orbit as $(0,1,2)$ and therefore not in $R^{\operatorname{mix}}$.

$\Longleftarrow$: Suppose that $\mathfrak{A}$ is not preserved by ll. If the
relation $T_{3}$ is primitively positively definable in $\mathfrak{A}$, then
so is $R^{\operatorname{mix}}$ by Proposition 20 because
$R^{\operatorname{mix}}$ is preserved by $\operatorname{pp}$ and we are done.
Otherwise, Theorem 2.5.2 implies that $\mathfrak{A}$ is preserved by
$\operatorname{mi}$, $\operatorname{mx}$, or $\min$. If $\mathfrak{A}$ is
preserved by $\operatorname{mi}$, then $R^{\operatorname{mix}}$ is primitively
positively definable in $\mathfrak{A}$ by Proposition 15. If $\mathfrak{A}$ is
preserved by $\operatorname{mx}$ but not by $\operatorname{mi}$, then
$R^{\operatorname{mix}}$ is primitively positively definable in $\mathfrak{A}$
by Proposition 17. If $\mathfrak{A}$ is preserved by $\min$ but neither by
$\operatorname{mi}$ nor by $\operatorname{mx}$, then $\mathfrak{A}$
primitively positively defines $R^{\operatorname{mix}}$ by Proposition 19.

######  Proof 5.12 (Proof of Theorem 3).

Suppose that $\mathfrak{A}$ does not have a binary injective polymorphism.
Then $\mathfrak{A}$ is preserved by $\min,\operatorname{mi}$,
$\operatorname{mx}$, or their duals. Therefore, $\mathfrak{A}$ is preserved by
$\operatorname{pp}$ or $\operatorname{dual-pp}$ by the inclusions presented in
Section 2.5.1. If $\mathfrak{A}$ is preserved by $\operatorname{pp}$, then
Theorem 10 implies that $R^{\operatorname{mix}}$ is primitively positively
definable in $\mathfrak{A}$. If $\mathfrak{A}$ is preserved by
$\operatorname{dual-pp}$, the dual of $\mathfrak{A}$, i.e., the structure
obained from $\mathfrak{A}$ by substituting all relations by their duals, has
$\operatorname{pp}$ as a polymorphism. Hence, $R^{\operatorname{mix}}$ has a
primitive positive definition in the dual of $\mathfrak{A}$ and therefore
$-R^{\operatorname{mix}}$ has a primitive positive definition in
$\mathfrak{A}$.

It remains to show that the two cases of the theorem are mutually exclusive.
Suppose that $\mathfrak{A}$ has a binary injective polymorphism $f$; we may
also assume without loss of generality that $f(0,1)>f(1,0)$. Since $f(0,1)\neq
f(0,2)$ we have $(f(0,1),f(0,2),f(1,0))\notin R^{\operatorname{mix}}$. As
$(0,0,1),(1,2,0)\in R^{\operatorname{mix}}$ we have that
$R^{\operatorname{mix}}$ is not preserved by $f$ and hence does not have a
primitive positive definition in $\mathfrak{A}$. The dual case works
analogously. Therefore, primitive positive definability of
$R^{\operatorname{mix}}$ in $\mathfrak{A}$ and binary injective polymorphisms
in $\operatorname{Pol}(\mathfrak{A})$ are mutually exclusive by Theorem 2.2.

##  6\. Combinations of Temporal CSPs

In this section we prove that the every generic combination of the structure
$({\mathbb{Q}};<,R^{\operatorname{mix}})$ with another structure that can
prevent crosses has an NP-hard CSP (Theorem 2). We then derive our complexity
classification for the CSP of combinations of temporal structures (Theorem 1).
In our NP-hardness proof we use the following.

######  Proposition 21 (Corollary 6.1.23 in [Bod21]).

Let $\mathfrak{A}$ be a countably infinite $\omega$-categorical structure with
finite relational signature and without constant polymorphisms. If all
polymorphisms of $\mathfrak{A}$ are essentially unary then
$\mathrm{CSP}(\mathfrak{A})$ is NP-hard.

The next definition introduces the key property of the polymorphisms of
$(\mathbb{Q};R^{\operatorname{mix}})$.

For any $n,i\in\mathbb{N}$, $1\leq i\leq n$, $a\in\mathbb{Q}^{n}$, and
operations $f\colon\mathbb{Q}^{n}\rightarrow\mathbb{Q}$ we define

$\displaystyle H(a,i)$
$\displaystyle\coloneqq\\!\left\\{b\in\mathbb{Q}^{n}\mid\text{for all
}j\in[n]\setminus\\{i\\}\text{ we have }b_{j}>a_{j}\text{ and
}b_{i}=a_{i}\right\\}$ $\displaystyle\text{and}\quad I_{f}(a)$
$\displaystyle\coloneqq\\!\left\\{i\in\mathbb{N}\mid f\text{ is constant on
}H(a,i)\right\\}.$

Let ${\mathcal{K}}$ be the set of all operations
$f\colon\mathbb{Q}^{n}\rightarrow\mathbb{Q}$ with $n\geq 1$ where
$I_{f}(a)\neq\emptyset$ for all $a\in\mathbb{Q}^{n}$.

Examples of operations in ${\mathcal{K}}$ are $\min$, $\operatorname{mi}$,
$\operatorname{mix}$, $\operatorname{mx}$, $\operatorname{pp}$, and all unary
operations. Non-examples are $\max$ and ll.

######  Lemma 22.

All polymorphisms of $(\mathbb{Q};R^{\operatorname{mix}})$ are in
${\mathcal{K}}$.

######  Proof 6.1.

Let $f\colon\mathbb{Q}^{n}\rightarrow\mathbb{Q}$ be a polymorphism of
$(\mathbb{Q};R^{\operatorname{mix}})$. We proceed by induction on
$n\in{\mathbb{N}}$. If $n=1$, the statement is trivial. For $n\geq 2$, assume
towards a contradiction that $f\not\in{\mathcal{K}}$. Then there exists
$c\in\mathbb{Q}^{n}$ such that for every $k\in[n]$ there exists
$a^{k},b^{k}\in H(c,k)$ such that $f(a^{k})<f(b^{k})$. Without loss of
generality we may assume that $\max(f(b^{1}),\dots,f(b^{n}))=f(b^{1})$. If
there exists $k\neq 1$ and $e>b^{1}_{1}$ such that $f(a^{k})\neq
f(e,a^{k}_{2},\dots,a^{k}_{n})$, then $(a^{k}_{1},e,b^{1}_{1})\in
R^{\operatorname{mix}}$ and $(a^{k}_{l},a^{k}_{l},b^{1}_{l})\in
R^{\operatorname{mix}}$ for all $l\in\\!\left\\{2,\dots,n\right\\}$, but
$(f(a^{k}),f(e,a^{k}_{2},\dots,a^{k}_{n}),f(b^{1}))\not\in
R^{\operatorname{mix}}$ because $f(b^{1})\geq f(a^{k})\neq
f(e,a^{k}_{2},\dots,a^{k}_{n})$, contradicting the assumption that $f$
preserves $R^{\operatorname{mix}}$. Similarly, if there exists $k\neq 1$ and
$e>b^{1}_{1}$ such that $f(b^{k})\neq f(e,b^{k}_{2},\dots,b^{k}_{n})$, then
$(b^{k}_{1},e,b^{1}_{1})\in R^{\operatorname{mix}}$ and
$(b^{k}_{l},b^{k}_{l},b^{1}_{l})\in R^{\operatorname{mix}}$ for all
$l\in\\{2,\dots,n\\}$, but
$(f(b^{k}),f(e,b^{k}_{2},\dots,b^{k}_{n}),f(b^{1}))\not\in
R^{\operatorname{mix}}$. Hence, for every $k\neq 1$ and every $e>b^{1}_{1}$ we
have

$f(e,a^{k}_{2},\dots,a^{k}_{n})=f(a^{k})<f(b^{k})=f(e,b^{k}_{2},\dots,b^{k}_{n}).$

Choose $e>b^{1}_{1}$ and define
$f^{\prime}\colon\mathbb{Q}^{n-1}\to\mathbb{Q}$ as $(x_{2},\dots,x_{n})\mapsto
f(e,x_{2},\dots,x_{n})$; as $R^{\operatorname{mix}}$ is preserved by all
constant polymorphisms, $f^{\prime}$ is a composition of polymorphisms of
$(\mathbb{Q};R^{\operatorname{mix}})$ and hence a polymorphism of
$(\mathbb{Q};R^{\operatorname{mix}})$. Then for all
$k\in\\!\left\\{2,\dots,n\right\\}$ we have

$\displaystyle(b^{k}_{2},\dots,b^{k}_{n}),(a^{k}_{2},\dots,a^{k}_{n})$
$\displaystyle\in H((c_{2},\dots,c_{n}),k)\quad\text{and}$ $\displaystyle
f^{\prime}(a^{k}_{2},\dots,a^{k}_{n})=f(e,a^{k}_{2},\dots,a^{k}_{n})$
$\displaystyle<f(e,b^{k}_{2},\dots,b^{k}_{n})=f^{\prime}(b^{k}_{2},\dots,b^{k}_{n}).$

Therefore, $f^{\prime}$ is an $(n-1)$-ary polymorphism of $\mathfrak{A}$ which
is not in ${\mathcal{K}}$, a contradiction to the induction hypothesis.

######  Lemma 23.

Let $f\in{\mathcal{K}}\cap\operatorname{Pol}(\mathbb{Q};<)$ be of arity $n\geq
2$. Let $a,b\in\mathbb{Q}^{n}$ and $i\in I_{f}(a)$.

  1. (1)

If $b_{i}<a_{i}\and\bigwedge_{k\neq i}b_{k}>a_{k}$, then
$I_{f}(b)=\\!\left\\{i\right\\}$.

  2. (2)

If $b_{i}\leq a_{i}\and\bigwedge_{k\neq i}b_{k}\geq a_{k}$, then $i\in
I_{f}(b)$.

######  Proof 6.2.

To prove (1), suppose for contradiction that $b_{i}<a_{i}\and\bigwedge_{k\neq
i}b_{k}>a_{k}$ and $j\in I_{f}(b)$ with $j\neq i$. Then there exists $c\in
H(b,j)$ such that $b_{i}<c_{i}<a_{i}$. Now consider $d,e\in\mathbb{Q}^{n}$
such that

$\displaystyle d_{j}=c_{j}\and
d_{i}=a_{i}\and\bigwedge_{k\not\in{i,j}}d_{k}>c_{k}\quad\text{ and }\quad
e_{i}=a_{i}\and\bigwedge_{k\neq i}e_{k}>d_{k}.$

Then $e_{j}>d_{j}=c_{j}=b_{j}>a_{j}$, $d_{i}=a_{i}=e_{i}>c_{i}>b_{i}$, and
$e_{k}>d_{k}>c_{k}>b_{k}>a_{k}$ for $k\in[n]\setminus\\{i,j\\}$. Hence, $d\in
H(b,j)\cap H(a,i)$ and $e\in H(a,i)$. This implies that $f(c)=f(d)=f(e)$,
which contradicts the assumption that $f$ preserves $<$, because $c_{k}<e_{k}$
for every $k\in[n]$. Since $I_{f}(b)\neq\emptyset$ by assumption, we therefore
conclude that $I_{f}(b)=\\{i\\}$.

To prove (2), first consider the case that $b_{i}=a_{i}$. Then
$H(b,i)\subseteq H(a,i)$ and therefore $i\in I_{f}(b)$. If $b_{i}<a_{i}$,
choose $u,v\in H(b,i)$. Then there exists $b^{\prime}\in H(b,i)$ such that for
each $k\neq i$ we have $b^{\prime}_{k}<\min(u_{k},v_{k})$. Then $u,v\in
H(b^{\prime},i)$ and $b^{\prime}$ satisfies
$b^{\prime}_{i}<a_{i}\and\bigwedge_{k\neq i}b^{\prime}_{k}>a_{j}$. Hence, we
have $I_{f}(b^{\prime})=\\{i\\}$ by the first claim of the statement and
therefore $f(u)=f(v)$. As $H(b^{\prime},i)\subseteq H(b,i)$ we conclude that
$i\in I_{f}(b)$.

######  Proof 6.3 (Proof of Theorem 2).

Let $\mathfrak{B}$ be the generic combination of
$({\mathbb{Q}};<,R^{\operatorname{mix}})$ and $\mathfrak{A}$, which exists by
Theorem 2.4. Without loss of generality we may assume that the domain of
$\mathfrak{B}$ is $\mathbb{Q}$ and that $\mathfrak{A}$ and
$({\mathbb{Q}};<,R^{\operatorname{mix}})$ are reducts of $\mathfrak{B}$. Let
$f\in\operatorname{Pol}(\mathfrak{B})$ be of arity $n$. Our goal is to show
that $f$ is essentially unary; the NP-hardness of $\mathrm{CSP}(\mathfrak{B})$
then follows from Proposition 21.

By Lemma 22 we have
$\operatorname{Pol}(\mathfrak{B})\subseteq\operatorname{Pol}(\mathbb{Q};<,R^{\operatorname{mix}})\subseteq{\mathcal{K}}$
and therefore $f\in{\mathcal{K}}$. Suppose for contradiction that there are
$a,b\in\mathbb{Q}^{n}$ such that $i\in I_{f}(a)$, $j\in I_{f}(b)$, and $i\neq
j$. We will treat the case that $i=1$ and $j=2$; all other cases can be
treated analogously. Let $\phi$ be a cross prevention formula of
$\mathfrak{A}$.

Consider the following first-order formula
$\psi(\bar{x},\bar{y},\bar{u},\bar{v})$ with parameters $a_{1},\dots,a_{n}$,
$b_{1},\dots,b_{n}$.

$\displaystyle\psi\coloneqq\quad$ $\displaystyle\;x_{1}<a_{1}\and
x_{1}=y_{1}\and\bigwedge_{k\in[n]\setminus\\!\left\\{1\right\\}}(x_{k}>a_{k}\and
y_{k}>a_{k})$ $\displaystyle\;u_{2}<b_{2}\and
u_{2}=v_{2}\and\bigwedge_{k\in[n]\setminus\\!\left\\{2\right\\}}(u_{k}>b_{k}\and
v_{k}>b_{k})$

For $k\in[n]$ let $\psi^{k}(x_{k},y_{k},u_{k},v_{k})$ be the conjunction of
all atomic formulas in $\psi$ that contain $x_{k}$, $y_{k}$, $u_{k}$, or
$v_{k}$. Notice that every atomic formula in $\psi$ only contains variables
from $\\{x_{k},y_{k},u_{k},v_{k}\\}$ for a fixed $k$. Hence,
$\psi(\bar{x},\bar{y},\bar{u},\bar{v})$ is equivalent to
$\bigwedge_{k=1}^{n}\psi^{k}(x_{k},y_{k},u_{k},v_{k})$. Let
$\delta(z_{1},z_{2},z_{3},z_{4})$ be the first-order formula

$z_{1}=z_{2}\wedge z_{2}\neq z_{3}\wedge z_{3}\neq z_{4}\wedge z_{2}\neq
x_{4}.$

For each $k$ there exists an assignment
$s_{k,1}\colon\\{x_{k},y_{k},u_{k},v_{k}\\}\to\mathbb{Q}$ which satisfies
$\psi^{k}$ and additionally satisfies
$\delta(x_{k},y_{k},u_{k},v_{k})\vee\delta(u_{k},v_{k},x_{k},y_{k})$. For
$k=1$ there exists an assignment $s_{1,2}$ that satisfies
$\phi(x_{k},y_{k},u_{k},v_{k})\wedge\delta(x_{k},y_{k},u_{k},v_{k})$, and for
each $k>1$ there exists an assignment $s_{k,2}$ that satisfies
$\phi(x_{k},y_{k},u_{k},v_{k})\wedge\delta(u_{k},v_{k},x_{k},y_{k})$. For each
$k$, both $s_{k,1}$ and $s_{k,2}$ can be chosen such that their images are
disjoint to the set of all entries of
$c\coloneqq(a_{1},\dots,a_{n},b_{1},\dots,b_{n})$, because both
$(\mathbb{Q};<)$ and $\mathfrak{A}$ do not have algebraicity. Now we apply the
first statement of Lemma 2.7 in [BG20] for each $k\in[n]$ to $c$, $s_{k,1}$,
$s_{k,2}$. This yields, for each $k\in[n]$, a solution $s^{k}$ to
$\psi^{k}\wedge\phi(x_{k},y_{k},u_{k},v_{k})$. Let $s(x)$ denote
$(s^{1}(x_{1}),\dots,s^{n}(x_{n}))$ and likewise for $s(y),s(u),s(v)$. Let
$a^{\prime}$ and $b^{\prime}$ be the componentwise minimum of $a,s(x),s(y)$
and $b,s(u),s(v)$, respectively. Then $s(x),s(y)\in H(a^{\prime},1)$ and
$s(u),s(v)\in H(b^{\prime},2)$. We apply Case 2 of Lemma 23 to $a$ and
$a^{\prime}$ (in the role of $b$) and $i=1$ and get $1\in I_{f}(a^{\prime})$.
Similarly, we apply Case 2 of Lemma 23 to $b$, $b^{\prime}$ and $i=2$ and get
$2\in I_{f}(b^{\prime})$. Therefore, $f(s(x))=f(s(y))$ and $f(s(u))=f(s(v))$
must hold. However, as $f$ preserves $\phi$ we must also have
$\phi(f(s(x)),f(s(y)),f(s(u)),f(s(v)))$, contradicting the fact that
$\phi(x,y,u,v)\and x=y\and u=v$ is not satisfiable in $\mathfrak{A}$.

We conclude that there exists an $i\in[n]$ such that $I_{f}(a)=\\{i\\}$ for
all $a\in\mathbb{Q}^{n}$. This implies that $f$ only depends on the $i$-th
coordinate: to prove this, let $a,b\in\mathbb{Q}^{n}$ be such that
$a_{i}=b_{i}$. We choose any $c\in\mathbb{Q}^{n}$ such that $c_{i}=a_{i}$ and
$c_{j}<\min(a_{j},b_{j})$ for every $j\in[n]\setminus\\{i\\}$. As $a,b\in
H(c,i)$ and $i\in I_{f}(c)$ we have $f(a)=f(b)$, i.e., $f$ can only depend on
the $i$-th coordinate. The case that $f$ is constant cannot happen, because
$f$ preserves $<$. Thus, $f$ is essentially unary.

Theorem 2 is applicable to countably infinite $\omega$-categorical structures
with finite relational signature which can prevent crosses and do not have
algebraicity. Besides $(\mathbb{Q};<)$, the following structures satisfy all
of these conditions:

  * •

the random graph with edge and non-edge relation [BP15]

  * •

the univeral homogeneous $K_{n}$-free graph, for $n\geq 3$, also called Henson
graph [BMPP19] with edge relation

  * •

first-order expansions of the binary branching $C$-relation in [BJP17]

  * •

the Fraïssé-limit of all finite 3-uniform hypergraphs which do not embed a
tetrahedron (see Chapter 6 in [Hod97] for the construction method)

######  Proof 6.4 (Proof of Theorem 1).

Let $\mathfrak{B}$ be the generic combination of $\mathfrak{A}_{1}$ and
$\mathfrak{A}_{2}$, which exists by Theorem 2.4. We may assume that
$\mathfrak{B}$, $\mathfrak{A}_{1}$, and $\mathfrak{A}_{2}$ all have the domain
$\mathbb{Q}$ and that $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ are reducts of
$\mathfrak{B}$. For $i=1$ and $i=2$, let $<_{i}$ be a linear order on
$\mathbb{Q}$ such that all relations of $\mathfrak{A}_{i}$ are first-order
definable in $(\mathbb{Q};<_{i})$; correspondingly
$\operatorname{Betw}_{i},\operatorname{Cycl}_{i},\operatorname{Sep}_{i},R^{\operatorname{mix}}_{i}$
are defined as the relations
$\operatorname{Betw},\operatorname{Cycl},\operatorname{Sep},R^{\operatorname{mix}}$
but with respect to $<_{i}$ instead of $<$. The same holds for
$\min_{i},\operatorname{mi}_{i},\operatorname{mx}_{i},\textup{{ll}}_{i}$ and
their duals.

If both $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ have a constant
polymorphism, then both $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ have all
constant operations as polymorphisms, and it follows that $\mathfrak{B}$ has a
constant polymorphism, too. In this case
$\mathrm{CSP}(\mathfrak{B})=\mathrm{CSP}(T_{1}\cup T_{2})$ can be solved in
constant time because only instances with an empty relation or $\bot$ as
conjunct are unsatisfiable (item (2) of the statement). Hence, we may suppose
without loss of generality that $\mathfrak{A}_{1}$ does not have a constant
polymorphism. Then by Theorem 2.5.1, one of the following cases applies.

  * •

$\mathfrak{A}_{1}$ is preserved by all permutations;

  * •

the relation $\operatorname{Betw}_{1}$, $\operatorname{Cycl}_{1}$, or
$\operatorname{Sep}_{1}$ is primitively positively definable in
$\mathfrak{A}_{1}$;

  * •

the relation $<_{1}$ is primitively positively definable in
$\mathfrak{A}_{1}$.

In the first case, $\mathfrak{B}$ itself is a temporal structure and
$\mathrm{CSP}(\mathfrak{B})$ is in P (item (3) of the statement) or NP-
complete by Theorem 2.5.2. If one of the relations $\operatorname{Betw}_{1}$,
$\operatorname{Cycl}_{1}$, or $\operatorname{Sep}_{1}$ is primitively
positively definable in $\mathfrak{A}_{1}$, then
$\mathrm{CSP}(\mathfrak{A}_{1})$ is NP-hard and hence
$\mathrm{CSP}(\mathfrak{B})$ is NP-hard. So we may assume in the following
that $<_{1}$ is primitively positively definable in $\mathfrak{A}_{1}$. Hence,
we can assume without loss of generality that $<_{1}$ is in the signature of
$\mathfrak{A}_{1}$.

We now consider the case that both $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$
have a binary injective polymorphism. If for some $i\in\\{1,2\\}$ the problem
$\mathrm{CSP}(\mathfrak{A}_{i})$ is NP-hard, then clearly
$\mathrm{CSP}(\mathfrak{B})=\mathrm{CSP}(T_{1}\cup T_{2})$ is NP-hard as well.
Otherwise, Theorem 2.5.2 implies that for $i=1$ and $i=2$, the structure
$\mathfrak{A}_{i}$ is preserved by ll or by $\operatorname{dual-ll}$ (or P=NP,
in which case Theorem 1 is trivial). Note that ll and $\operatorname{dual-ll}$
also preserve $\neq$, so we may add $\neq$ to the signature of
$\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$. As $\neq$ is independent from
$T_{1}$ and from $T_{2}$ by Proposition 4, the polynomial-time tractability of
$\mathrm{CSP}(T_{1}\cup T_{2})$ then follows from Theorem 5.

If $\mathfrak{A}_{1}$ does not have a binary injective polymorphism, then
$\mathrm{CSP}(\mathfrak{A}_{1})$ and $\mathrm{CSP}(\mathfrak{B})$ are NP-hard
unless $\operatorname{mx}_{1}$, $\min_{1}$, $\operatorname{mi}_{1}$, or one of
their duals is a polymorphism of $\mathfrak{A}_{1}$, by Theorem 2.5.2. We
assume in the following that $\mathfrak{A}_{1}$ is preserved by
$\operatorname{mx}_{1}$, $\min_{1}$, or $\operatorname{mi}_{1}$; if
$\mathfrak{A}_{1}$ is preserved by one of their duals, then the NP-hardness of
$\mathrm{CSP}(T_{1}\cup T_{2})$ can be shown analogously. By Theorem 3, the
relation $R^{\operatorname{mix}}_{1}$ has a primitive positive definition in
$\mathfrak{A}_{1}$.

Now, we make a case distinction for $\mathfrak{A}_{2}$. If the structure
$\mathfrak{A}_{2}$ is preserved by all permutations, we are again done (this
is analogous to the situation that $\mathfrak{A}_{1}$ is preserved by all
permutations, which was already treated above). Otherwise, we apply Theorem
2.5.1 to $(\mathfrak{A}_{2};\neq)$ and obtain that a relation
$R\in\\{<_{2},\operatorname{Betw}_{2},\operatorname{Cycl}_{2},\operatorname{Sep}_{2}\\}$
has a primitive positive definition $\phi$ in $(\mathfrak{A}_{2};\neq)$. Let
$E$ be the set of all sets $\\!\left\\{x_{i},x_{j}\right\\}$ such that
$x_{i}\neq x_{j}$ appears in $\phi$ and $n$ the arity of $R$. Then, for some
$m\geq n$, the formula $\phi$ can be written in the following way:
$\phi(x_{1},\dots,x_{n})=\exists
x_{n+1},\dots,x_{m}\big{(}\psi(x_{1},\dots,x_{m})\and\bigwedge_{{i,j}\in
E}x_{i}\neq x_{j}\big{)}$ where $\psi$ is a primitive positive
$\tau_{2}$-formula. Notice that for all $i,j\in[n]$ with $i\neq j$ we may add
$\\!\left\\{i,j\right\\}$ to $E$ because for any choice of $R$, all
coordinates in tuples of $R$ are pairwise distinct.

Consider the undirected graph $([m],E)$. We may choose any linear order
$E_{d}^{\prime}$ on $[n]$ and extend $E_{d}^{\prime}$ to $E_{d}$ on $[m]$ by
choosing a direction for each edge in $E$ such that $([m],E_{d})$ is a cycle-
free directed graph. Because $x<y\vee x>y$ defines $x\neq y$ we have

$\displaystyle\phi(x_{1},\dots,x_{n})\equiv\exists x_{n+1},\dots,x_{m}\Big{(}$
$\displaystyle(\psi(x_{1},\dots,x_{m})\and\bigwedge_{(i,j)\in
E_{d}}((x_{i}<_{1}x_{j})\vee(x_{j}<_{1}x_{i}))\Big{)}.$

Now notice that $\exists
x_{n+1},\dots,x_{m}\big{(}\psi(x_{1},\dots,x_{m})\and\bigwedge_{(i,j)\in
E_{d}}x_{i}<_{1}x_{j}\big{)}$ is a primitive positive formula in
$\mathfrak{B}$ which defines the same relation as the formula

$R(x_{1},\dots,x_{n})\and\bigwedge_{(i,j)\in E_{d}^{\prime}}x_{i}<_{1}x_{j}$
(12)

in $\mathfrak{B}$. Now, we go through all possible choices for $R$ and present
primitive positive definitions for either $<_{2}$ or $\neq$ in $\mathfrak{B}$.
In order to simplify the presentation, we will use conjuncts of the form (12)
instead of their equivalent primitive positive definitions in $\mathfrak{B}$.

  * •

If $R$ equals $<_{2}$ then $\exists z\big{(}(x<_{2}z\and
x<_{1}z)\and(z<_{2}y\and y<_{1}z))$ is a primitive positive definition of
$x<_{2}y$. This is easy to see with the equivalent expression $\exists
z\big{(}(x<_{2}z<_{2}y)\and(x<_{1}z)\and(y<_{1}z)\big{)}$.

  * •

If $R$ equals $\operatorname{Betw}_{2}$ we claim that

$\displaystyle\exists u,v\big{(}$
$\displaystyle(\operatorname{Betw}_{2}(x,u,v)\and(x<_{1}u)\and(u<_{1}v))$
$\displaystyle\and\;$
$\displaystyle(\operatorname{Betw}_{2}(u,v,y)\and(y<_{1}u)\and(u<_{1}v))\big{)}$

is a primitive positive definition of $x\neq y$. Again we give an equivalent
expression which helps to verify the claim: $\exists
u,v\big{(}((x<_{2}u<_{2}v<_{2}y)\vee(y<_{2}v<_{2}u<_{2}x))\and(x<_{1}u<_{1}v)\and(y<_{1}u)\big{)}$.
In the latter, it is clear that $x\neq y$ always holds and that all distinct
$x,y$ satisfy the formula.

  * •

If $R$ equals $\operatorname{Cycl}_{2}$ we claim that

$\displaystyle\exists u,v\big{(}$
$\displaystyle(\operatorname{Cycl}_{2}(x,u,v)\and(x<_{1}u)\and(u<_{1}v))$
$\displaystyle\and\;$
$\displaystyle(\operatorname{Cycl}_{2}(u,y,v)\and(y<_{1}u)\and(u<_{1}v))\big{)}$

is a primitive positive definition of $x\neq y$. A case analysis of
$\operatorname{Cycl}_{2}(x,u,v)$ yields that the given formula is equivalent
to

$\displaystyle\exists u,v\big{(}\big{(}$
$\displaystyle\quad(x<_{2}u<_{2}y<_{2}v)$
$\displaystyle\vee(u<_{2}y<_{2}v<_{2}x)$
$\displaystyle\vee(y<_{2}v<_{2}x<_{2}u)$
$\displaystyle\vee(v<_{2}x<_{2}u<_{2}y)\big{)}$ $\displaystyle\and\;$
$\displaystyle(x<_{1}u<_{1}v)\and(y<_{1}u)\big{)}.$

In the latter formula, it is clear that $x\neq y$ must always hold and that
for any distinct $x,y$ the formula is satisfiable.

  * •

If $R$ equals $\operatorname{Sep}_{2}$ we claim that

$\displaystyle\exists u,v,w\big{(}$
$\displaystyle(\operatorname{Sep}_{2}(x,u,v,w)\and(x<_{1}u)\and(u<_{1}v)\and(v<_{1}w))$
$\displaystyle\and\;$
$\displaystyle(\operatorname{Sep}_{2}(u,v,w,y)\and(y<_{1}u)\and(u<_{1}v)\and(v<_{1}w))\big{)}$

is a primitive positive definition of $x\neq y$. Similarly to above, a case
analysis of $\operatorname{Sep}_{2}$ yields an equivalent expression

$\displaystyle\exists u,v,w\big{(}\big{(}$
$\displaystyle\quad(x<_{2}v<_{2}y<_{2}u<_{2}w)$
$\displaystyle\vee(x<_{2}w<_{2}u<_{2}y<_{2}v)$
$\displaystyle\vee(u<_{2}y<_{2}v<_{2}x<_{2}w)$
$\displaystyle\vee(u<_{2}w<_{2}x<_{2}v<_{2}y)\vee(y<_{2}u<_{2}w<_{2}x<_{2}v)$
$\displaystyle\vee(v<_{2}x<_{2}w<_{2}y<_{2}u)$
$\displaystyle\vee(v<_{2}u<_{2}y<_{2}w<_{2}x)$
$\displaystyle\vee(w<_{2}y<_{2}u<_{2}v<_{2}x)$
$\displaystyle\vee(w<_{2}x<_{2}v<_{2}u<_{2}y)\vee(y<_{2}w<_{2}x<_{2}v<_{2}u)\big{)}$
$\displaystyle\and\;$ $\displaystyle(x<_{1}u<_{1}v<_{1}w)\and(y<_{1}u)\big{)}$

for which the claim is easily verified because $x\neq y$ always holds and for
any distinct $x,y$ there exist $u,v,w$ satisfying the formula.

Choose a relation $S$ from $\\!\left\\{\neq,<_{2}\right\\}$ which is
primitively positively definable in $\mathfrak{B}$ and let
$\mathfrak{A}^{\prime}_{2}$ be the expansion of $\mathfrak{A}_{2}$ by $S$ and
$\mathfrak{B}^{\prime}\coloneqq\mathfrak{A}_{1}\ast\mathfrak{A}_{2}^{\prime}$.
As $S$ is primitively positively definable in $\mathfrak{B}$, it suffices to
show NP-hardness of $\mathrm{CSP}(\mathfrak{B}^{\prime})$ instead of
$\mathrm{CSP}(\mathfrak{B})=\mathrm{CSP}(T_{1}\cup T_{2})$.

If $S$ is $<_{2}$, then $\mathfrak{A}_{2}^{\prime}$ has cross prevention, so
the NP-hardness of $\mathrm{CSP}(\mathfrak{B}^{\prime})$ follows from Theorem
2. If $S$ is $\neq$, then we may again apply Theorem 2.5.1 to
$\mathfrak{A}_{2}^{\prime}$ to conclude that the relation $<_{2}$,
$\operatorname{Betw}_{2}$, $\operatorname{Cycl}_{2}$, or
$\operatorname{Sep}_{2}$ is primitively positively definable in
$\mathfrak{A}^{\prime}_{2}$. The first case has already been treated above. In
the remaining cases we get NP-hardness of
$\mathrm{CSP}(\mathfrak{A}_{2}^{\prime})$ and hence of
$\mathrm{CSP}(\mathfrak{B}^{\prime})$.

##  7\. Conclusion and Outlook

Our results show that there are two temporal relations, namely
$R^{\operatorname{mix}}$ and its dual, with the property that every first-
order expansion of $(\mathbb{Q};<)$ where the weakened Nelson-Oppen conditions
do not apply, i.e., $\neq$ is not independent from their theory, can define
one of these relations primitively positively. We also showed that
$\mathrm{CSP}({\operatorname{Th}(\mathbb{Q};R^{\operatorname{mix}},<)}\cup\operatorname{Th}(\mathfrak{A}))$
is NP-hard for structures $\mathfrak{A}$ that satisfy the fairly weak
assumption of cross prevention and have a generic combination with
$(\mathbb{Q};<)$. These results can be used to prove a complexity dichotomy
for combinations of temporal CSPs: they are either in P or NP-complete. Our
results also motivate the following conjecture, which remains open in general.

######  Conjecture 24.

Let $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ be countably infinite
$\omega$-categorical structures without algebraicity that are not preserved by
all permutations and that have the cross prevention property. If

  * •

$\mathrm{CSP}(\mathfrak{A}_{i})$ is in P and $\mathfrak{A}_{i}$ has a binary
injective polymorphism for both $i=1$ and $i=2$, or

  * •

$\mathfrak{A}_{i}$ has a constant polymorphism for both $i=1$ and $i=2$,

then
$\mathrm{CSP}(\operatorname{Th}(\mathfrak{A}_{1})\cup\operatorname{Th}(\mathfrak{A}_{2}))$
is in P. Otherwise,
$\mathrm{CSP}(\operatorname{Th}(\mathfrak{A}_{1})\cup\operatorname{Th}(\mathfrak{A}_{2}))$
is NP-hard.

## References

  * [BCP10] Manuel Bodirsky, Hubie Chen, and Michael Pinsker.  The reducts of equality up to primitive positive interdefinability.  Journal of Symbolic Logic, 75(4):1249–1292, 2010.  doi:10.2178/jsl/1286198146.
  * [BCW14] Manuel Bodirsky, Hubie Chen, and Michał Wrona.  Tractability of quantified temporal constraints to the max.  International Journal of Algebra and Computation, 24(8):1141–1156, 2014.  doi:10.1142/S0218196714500507.
  * [BG20] Manuel Bodirsky and Johannes Greiner.  The Complexity of Combinations of Qualitative Constraint Satisfaction Problems.  Logical Methods in Computer Science, Volume 16, Issue 1, February 2020.  URL: https://lmcs.episciences.org/6129, doi:10.23638/LMCS-16(1:21)2020.
  * [BG21] Manuel Bodirsky and Johannes Greiner.  Tractable combinations of theories via sampling.  In Logics in Artificial Intelligence - 17th European Conference, JELIA 2021, Virtual Event, May 17-20, 2021, Proceedings, pages 133–146, 2021\.  doi:10.1007/978-3-030-75775-5\\_10.
  * [BGN+06] Maria Paola Bonacina, Silvio Ghilardi, Enrica Nicolini, Silvio Ranise, and Daniele Zucchelli.  Decidability and undecidability results for nelson-oppen and rewrite-based decision procedures.  In Ulrich Furbach and Natarajan Shankar, editors, Automated Reasoning, pages 513–527, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
  * [BH12] Manuel Bodirsky and Martin Hils.  Tractable set constraints.  Journal of Artificial Intelligence Research, 45:731–759, 2012.  doi:10.1613/jair.3747.
  * [BJP17] Manuel Bodirsky, Peter Jonsson, and Trung Van Pham.  The Complexity of Phylogeny Constraint Satisfaction Problems.  ACM Transactions on Computational Logic (TOCL), 18(3), 2017.  An extended abstract appeared in the conference STACS 2016.  doi:10.4230/LIPIcs.STACS.2016.20.
  * [BJR02] Mathias Broxvall, Peter Jonsson, and Jochen Renz.  Disjunctions, independence, refinements.  Artificial Intelligence, 140(1/2):153–173, 2002.
  * [BK08] Manuel Bodirsky and Jan Kára.  The complexity of equality constraint languages.  Theory of Computing Systems, 3(2):136–158, 2008.  A conference version appeared in the proceedings of Computer Science Russia (CSR’06).  doi:10.1007/s00224-007-9083-9.
  * [BK09] Manuel Bodirsky and Jan Kára.  The complexity of temporal constraint satisfaction problems.  Journal of the ACM, 57(2):1–41, 2009.  An extended abstract appeared in the Proceedings of the Symposium on Theory of Computing (STOC).  doi:10.1145/1667053.1667058.
  * [BMM21] Manuel Bodirsky, Florent R. Madelaine, and Antoine Mottet.  A proof of the algebraic tractability conjecture for monotone monadic SNP.  SIAM J. Comput., 50(4):1359–1409, 2021.  doi:10.1137/19M128466X.
  * [BMPP19] Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and András Pongrácz.  Constraint satisfaction problems for reducts of homogeneous graphs.  SIAM Journal on Computing, 48(4):1224–1264, 2019.  A conference version appeared in the Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, pages 119:1-119:14.  doi:10.1137/16M1082974.
  * [BN06] Manuel Bodirsky and Jaroslav Nešetřil.  Constraint satisfaction with countable homogeneous templates.  Journal of Logic and Computation, 16(3):359–373, 2006.  doi:10.1093/logcom/exi083.