N_{\mathrm{rem}}\\}\big{)}\cup\\{\mathtt{U}\mathtt{\texttt{-}ReCol}_{o_{1}}^{i}(s)\mid(s,i)\in
N_{\mathrm{add}}\\}.$

By construction and the fact that $\mathcal{T}$ is in normal form,
$\mathcal{I}^{\mathcal{T}^{\mathtt{U}}}\cong\mathcal{I}^{\mathtt{U}:=A}$
witnessed by $h$. ∎

###  B-D Proofs for Section VI-D

######  Theorem 28.

Let $\mathcal{I}$ be a countable instance over a finite signature of arbitrary
arity. Then the following hold:

  * •

If $\mathcal{I}$ has finite treewidth, then $\mathcal{I}$ has finite
partitionwidth.

  * •

If $\mathcal{I}$ has finite cliquewidth, then $\mathcal{I}$ has finite
partitionwidth.

We split the proof of the theorem into two propositions.

######  Proposition 46.

Let $\mathcal{I}$ be a countable instance over a signature $\Sigma$. If
$\mathcal{I}$ has finite treewidth, then $\mathcal{I}$ has finite
partitionwidth.

###### Proof.

Courcelle showed [27, Theorem 8.1] that, given a MSO-sentence $\Psi$ talking
about hypergraphs of treewidth $n$, the set of terms representing hypergraphs
that satsify $\Psi$, is MSO-definable. In the course of this proof, he
exhibits a MSO-definition that can be used in the follwing way for our proof:
Given an instance $\mathcal{I}$ of finite treewidth, first rewrite it as a
hypergraph $\mathcal{G}_{\mathcal{I}}$. Then there is a (term-)tree
$\mathcal{T}$ representing $\mathcal{G}_{\mathcal{I}}$, meaning that the
(possibly infinite) term evaluates to $\mathcal{G}_{\mathcal{I}}$,
$\mathsf{val}(\mathcal{T})=\mathcal{G}_{\mathcal{I}}$. We can then produce a
MSO-definition of $\mathsf{val}(\mathcal{T})$ in $\mathcal{T}$. Since
$\mathcal{T}$ is a tree, we obtain that $\mathcal{G}_{\mathcal{I}}$ is MSO-
tree-definable, hence MSO-tree-interpretable. By invoking Theorem 22 and
translating our previous result to $\mathcal{I}$, we obtain that $\mathcal{I}$
has finite partitionwidth, concluding the proof. ∎

In order to disambiguate between well-decorated trees in the partitionwidth
sense (as in Definition 16) and those in the cliquewidth sense [34, Definition
6], let for a set of unary colors $\mathbb{L}$,
$\mathrm{Dec}_{\mathrm{cw}}(\mathbb{L},\mathrm{Cnst},\Sigma)$ denote the set
of decorators in the latter sense.

######  Proposition 47.

Let $\mathcal{I}$ be a countable instance over a signature $\Sigma$. If
$\mathcal{I}$ has finite cliquewidth, then $\mathcal{I}$ has finite
partitionwidth.

###### Proof.

Let $\mathcal{I}$ be an instance of finite cliquewidth over signature $\Sigma$
and set of constants $\mathrm{Const}$. Then there is a finite set of (unary)
colors $\mathbb{L}$ and $(\mathbb{L},\mathrm{Cnst},\Sigma)$-well-decorated
tree $\mathcal{T}$ in the cliquewidth sense [34, Definition 6] such that
$\mathcal{I}=\mathcal{I}^{\mathcal{T}}$ in the cliquewidth sense [34,
Definition 7]. We recall that for the notion of cliquewidth [34, Definition 8]
a MSO-interpretation of instances in well-decorated trees (in the cliquewidth
sense [34, Definition 6]) has been exhibited. Using the results obtained
there, let
$\varphi_{\top}(x_{1})=\bigvee\big{(}\mathtt{c}_{k}(x_{1})\mid\mathtt{c}\in\mathrm{Const}\cup\\{\mathtt{*}\\},k\in\mathbb{L}\big{)}$;
for all $\mathtt{c}\in\mathrm{Cnst},k\in\mathbb{L}$,
$\varphi_{\mathtt{c}}(x_{1})=\mathtt{c}_{k}(x_{1})$ and
$\varphi_{=}(x_{1},x_{2})=(x_{1}=x_{2})$. For every $\mathtt{R}\in\Sigma$ we
define a formula
$\varphi_{\mathtt{R}}(x_{1},\ldots,x_{\mathsf{ar}(\mathtt{R})})$ as follows:

Let

$\varphi_{\mathsf{up}}(x,y)=\mathtt{Succ}_{0}(y,x)\vee\mathtt{Succ}_{1}(y,x)$

and

$\varphi^{\mathrm{colIn}}_{k}(x,y)=\varphi_{\top}(x)\wedge\forall_{\ell\in\mathbb{L}}X_{\ell}.\Big{(}\big{(}\bigwedge_{\hskip
9.04166pt\psi\in M_{xy}}\psi\,\big{)}\to X_{k}(y)\Big{)},$

where $X_{\ell}$ are MSO set variables and $M_{xy}$ contains the following
formulae (for all respective elements of
$\mathrm{Dec}_{\mathrm{cw}}(\mathbb{L},\mathrm{Cnst},\Sigma)$):

$\displaystyle\mathtt{c}_{k}(x)$ $\displaystyle\to X_{k}(x)$
$\displaystyle\forall
x^{\prime}\\!y^{\prime}\\!.X_{k}(x^{\prime})\wedge\varphi_{\mathsf{up}}(x^{\prime}\\!,y^{\prime})\wedge\mathtt{Add}_{\mathtt{R},k^{\prime},k^{\prime\prime}}(y^{\prime})$
$\displaystyle\to X_{k}(y^{\prime})$ $\displaystyle\forall
x^{\prime}\\!y^{\prime}\\!.X_{k}(x^{\prime})\wedge\varphi_{\mathsf{up}}(x^{\prime}\\!,y^{\prime})\wedge\mathtt{Add}_{\mathtt{R},k^{\prime}}(y^{\prime})$
$\displaystyle\to X_{k}(y^{\prime})$ $\displaystyle\forall
x^{\prime}\\!y^{\prime}\\!.X_{k}(x^{\prime})\wedge\varphi_{\mathsf{up}}(x^{\prime}\\!,y^{\prime})\wedge\mathtt{Recolor}_{k\to
k^{\prime}}(y^{\prime})$ $\displaystyle\to X_{k^{\prime}}(y^{\prime})$
$\displaystyle\forall
x^{\prime}\\!y^{\prime}\\!.X_{k}(x^{\prime})\wedge\varphi_{\mathsf{up}}(x^{\prime}\\!,y^{\prime})\wedge\mathtt{Recolor}_{k^{\prime}\\!\to
k^{\prime\prime}}(y^{\prime})$ $\displaystyle\to X_{k}(y^{\prime})\hskip
6.45831pt\text{for }k{\neq}k^{\prime}$ $\displaystyle\forall
x^{\prime}\\!y^{\prime}\\!.X_{k}(x^{\prime})\wedge\varphi_{\mathsf{up}}(x^{\prime}\\!,y^{\prime})\wedge\oplus(y^{\prime})$
$\displaystyle\to X_{k}(y^{\prime})$

For each predicate $\mathtt{R}\in\Sigma$ of arity $n$, we define

$\displaystyle\varphi_{\mathtt{R}}(x_{1},\ldots,x_{n})$ $\displaystyle=\exists
z.\bigvee_{\hskip
6.02777pt\scaleobj{0.9}{(k_{1},\ldots,k_{n})\in\mathbb{L}^{n}}}\scaleobj{0.8}{\Big{(}}\,\mathtt{Add}_{\mathtt{R},k_{1},\ldots,k_{n}}(z)\wedge\\!\scaleobj{0.8}{\bigwedge_{\scaleobj{1.25}{1\leq
i\leq n}}}\varphi^{\mathrm{colIn}}_{k_{i}}(x_{i},z)\scaleobj{0.8}{\Big{)}}$

Then $\mathfrak{I}$ is the sequence of the MSO-formulae:
$\varphi_{\mathtt{R}}(x_{1},\ldots,x_{\mathsf{ar}(\mathtt{R})})$ for every
$\mathtt{R}\in\Sigma{\cup}\\{\top\\}$; $\varphi_{\mathtt{c}}(x_{1})$ for every
$\mathtt{c}\in\mathrm{Const}$; and $\varphi_{=}(x_{1},x_{2})$ as described
above. Hence $\mathcal{I}\leq_{\text{MSO}}\mathcal{T}$. Invoking Theorem 22 we
obtain that $\mathcal{I}$ has finite partitionwidth. ∎

######  Proposition 29.

Let $\mathcal{I}$ be a countable instance over a binary signature $\Sigma$.
$\mathcal{I}$ has finite cliquewidth iff $\mathcal{I}$ has finite
partitionwidth.

Before proving Proposition 29, we introduce some technical notions.

######  Definition 48.

Let $\mathcal{T}$ be a $(\mathbb{L},\mathrm{Cnst},\Sigma)$-well-decorated tree
and $i\in\\{0,1\\}$. Let $s$ be a node of $\mathcal{T}$ that is an ancestor of
a pseudoleaf. We call $s$ _recolor-cyclical for $i$_, if there is a $n\geq 2$
and a sequence of colors $\kappa_{1},\ldots,\kappa_{n}\in\mathbb{L}$ of the
same arity, such that
$\kappa_{2}\mathtt{\texttt{-}ReCol}_{\kappa_{1}}^{i}(s),\ldots,\kappa_{n}\mathtt{\texttt{-}ReCol}_{\kappa_{n-1}}^{i}(s),\kappa_{1}\mathtt{\texttt{-}ReCol}_{\kappa_{n}}^{i}(s)\in\mathcal{T}$.
In this case we call $(i,\kappa_{1},\ldots,\kappa_{n})$ a _recolor cycle at
$s$ for $i$_. We call $s$ _recolor-cyclical_ if it is recolor-cyclical for
some $i\in\\{0,1\\}$. If $s$ is not recolor-cyclical, we also call $s$ _non-
recolor-cyclical_. We say an instruction
$\lambda\mathtt{\texttt{-}ReCol}_{\kappa}^{i}$ _participates in a recolor-
cycle at $s$_, if there is some recolor-cycle
$(i,\kappa_{1},\ldots,\kappa_{m})$ at $s$ and either some $1\leq j\leq m-1$
such that $\kappa=\kappa_{j}$ and $\lambda=\kappa_{j+1}$ or
$\kappa=\kappa_{m}$ and $\lambda=\kappa_{1}$. $\Diamond$

######  Definition 49.

Let $\Sigma$ be a binary signature. Given a
$(\mathbb{L},\mathrm{Cnst},\Sigma)$-well-decorated tree $\mathcal{T}$ (in the
partitionwidth-sense, Definition 16) in normal form, we associate to it a
$(\mathbb{L}_{\mathrm{cw}},\mathrm{Cnst},\Sigma)$-well-decorated tree (in the
cliquewidth sense [34, Definition 6]) inductively in the following manner:
First define the set of (unary) colors
$\mathbb{L}_{\mathrm{cw}}=\mathbb{L}_{1}\oplus(\mathbb{L}_{1}\times\\{0,1\\})\oplus\\{\mu_{\mathrm{cb}}\\}$,
where $\mathbb{L}_{1}\subseteq\mathbb{L}$ is the subset of all unary colors of
$\mathbb{L}$ and $\mu_{\mathrm{cb}}$ is a as of yet unused color. The
following auxillary maps will be defined along the construction:
$\mathsf{r}^{\mathcal{T}}\colon P\oplus A_{P}\to\\{0,1\\}^{*}$,
$\mathsf{suc}^{\mathcal{T}}_{0}\colon A_{P}\to\\{0,1\\}^{*}$,
$\mathsf{suc}^{\mathcal{T}}_{1}\colon A_{P}\to\\{0,1\\}^{*}$, and a map
associating to every $s\in P\oplus A_{P}$ an instance
$\mathcal{T}_{\mathrm{cw}}^{s}$. Let $s\in P\oplus A_{P}$ and
$\mathsf{r}^{\mathcal{T}},\mathsf{suc}^{\mathcal{T}}_{0},\mathsf{suc}^{\mathcal{T}}_{1}$
be defined for every proper ancestor $s^{\prime}$ of $s$ but not for $s$. If
$s=\varepsilon$, initialize
$\mathsf{r}^{\mathcal{T}}\\!(\varepsilon)=\varepsilon$. Otherwise define
$\mathsf{r}^{\mathcal{T}}\\!(s)=\mathsf{suc}_{i_{s}}^{\mathcal{T}}(s^{\prime})$
where $s^{\prime}i_{s}=s$, i.e. $s^{\prime}$ is the unique predecessor of $s$.
We distinguish between two cases:

  * •

_$s$ is a pseudoleaf_. Then set
$\mathcal{T}_{\mathrm{cw}}^{s}=\\{\mathtt{c}_{o_{1}}(\mathsf{r}^{\mathcal{T}}\\!(s))\mid\mathtt{c}_{o_{1}}(s)\in\mathcal{T}\\}$.

  * •

_$s$ is not a pseudoleaf_. Then define with $i\in\\{0,1\\}$ the sets

$\displaystyle\mathsf{PRec}^{i}_{s}=\\{\lambda\mathtt{\texttt{-}ReCol}_{\kappa}^{i}\mid\kappa\in\mathbb{L}_{1},\lambda\mathtt{\texttt{-}ReCol}_{\kappa}^{i}(s)\in\mathcal{T}\\},\hskip
21.52771pt\mathsf{URel}^{i}_{s}=\\{\mathtt{R}\mathtt{\texttt{-}Add}_{\lambda}^{i}\mid\mathtt{R}\in\Sigma\\},\text{
and}$
$\displaystyle\mathsf{Rel}_{s}=\\{\mathtt{R}\mathtt{\texttt{-}Add}^{I}_{\kappa_{1}\kappa_{2}}\mid\mathtt{R}\in\Sigma,\mathsf{ar}(\mathtt{R})=2,\mathtt{R}\mathtt{\texttt{-}Add}^{I}_{\kappa_{1}\kappa_{2}}(s)\in\mathcal{T}\\}.$

Define $\mathsf{C}_{s}^{i}$ to be the set of all recolor cycles at $s$ for
$i\in\\{0,1\\}$. Set
$\mathsf{Rec}^{i}_{s}=\mathsf{PRec}^{i}_{s}\cup\mathsf{C}_{s}^{i}$. Let
$k_{s}=|\mathsf{Rel}_{s}|$, $k_{s}^{i}=|\mathsf{URel}^{i}_{s}|$,
$\ell_{s}^{i}=|\mathsf{Rec}_{s}^{i}|$, and let
$\mathsf{f}_{s}\colon\mathsf{Rel}_{s}\to\\{0,\ldots,k_{s}-1\\}$ and
$\mathsf{f}_{s}^{i}\colon\mathsf{URel}_{s}^{i}\to\\{0,\ldots,k_{s}^{i}-1\\}$
be bijections. Additionally let
$\mathsf{g}_{s}^{i}\colon\mathsf{Rec}_{s}^{i}\to\\{0,\ldots,\ell_{s}^{i}-1\\}$
be bijections with the following properties: For every
$\mathrm{cyc}\in\mathsf{C}^{i}_{s}$ where
$\mathrm{cyc}=(i,\kappa_{1},\ldots,\kappa_{m})$:

    * –

$\mathsf{g}^{i}_{s}(\mathrm{cyc})=\mathsf{g}^{i}_{s}(\kappa_{1}\mathtt{\texttt{-}ReCol}_{\kappa_{m}})+1$
and
$\mathsf{g}^{i}_{s}(\kappa_{1}\mathtt{\texttt{-}ReCol}_{\kappa_{m}})=\mathsf{g}^{i}_{s}(\kappa_{m}\mathtt{\texttt{-}ReCol}_{\kappa_{m-1}})+1$,

    * –

for every $1\leq k\leq m-2$ we have
$\mathsf{g}^{i}_{s}(\kappa_{k+2}\mathtt{\texttt{-}ReCol}_{\kappa_{k+1}})=\mathsf{g}^{i}_{s}(\kappa_{k+1}\mathtt{\texttt{-}ReCol}_{\kappa_{k}})+1$.

Then set
$\mathsf{suc}^{\mathcal{T}}_{0}(s)=\mathsf{r}^{\mathcal{T}}\\!(s)0^{2|\mathbb{L}_{1}|+k_{s}+k_{s}^{0}+k_{s}^{1}+\ell_{s}^{0}+\ell_{s}^{1}+1+|\mathbb{L}_{1}|}$
and
$\mathsf{suc}^{\mathcal{T}}_{1}(s)=\mathsf{r}^{\mathcal{T}}\\!(s)0^{2|\mathbb{L}_{1}|+k_{s}+k_{s}^{0}+k_{s}^{1}+\ell_{s}^{0}+\ell_{s}^{1}}10^{|\mathbb{L}_{1}|}$.
Then $\mathcal{T}_{\mathrm{cw}}^{s}$ is the union of the following instances
over $\mathrm{Dec}_{\mathrm{cw}}(\mathbb{L}^{*},\mathrm{Cnst},\Sigma)$:

$\displaystyle\mathcal{T}_{\mathrm{pre},0}^{s}$
$\displaystyle=\\{\mathtt{Recolor}_{\kappa\hstretch{0.5}{\to}(\kappa,0)}(\mathsf{r}^{\mathcal{T}}\\!(s)0^{2|\mathbb{L}_{1}|+k_{s}+k_{s}^{0}+k_{s}^{1}+\ell_{s}^{0}+\ell_{s}^{1}+1+j})$
$\displaystyle\mid\kappa\in\mathbb{L}_{1},\mathsf{coen}(\kappa)=j\\}$
$\displaystyle\mathcal{T}_{\mathrm{pre},1}^{s}$
$\displaystyle=\\{\mathtt{Recolor}_{\kappa\hstretch{0.5}{\to}(\kappa,1)}(\mathsf{r}^{\mathcal{T}}\\!(s)0^{2|\mathbb{L}_{1}|+k_{s}+k_{s}^{0}+k_{s}^{1}+\ell_{s}^{0}+\ell_{s}^{1}}10^{j})$
$\displaystyle\mid\kappa\in\mathbb{L}_{1},\mathsf{coen}(\kappa)=j\\}$
$\displaystyle\mathcal{T}_{\mathrm{un}}^{s}$
$\displaystyle=\\{\oplus(\mathsf{r}^{\mathcal{T}}\\!(s)0^{2|\mathbb{L}_{1}|+k_{s}+k_{s}^{0}+k_{s}^{1}+\ell_{s}^{0}+\ell_{s}^{1}})\\}$
$\displaystyle\mathcal{T}_{\mathtt{Add}}^{s}$
$\displaystyle=\\{\mathtt{Add}_{\mathtt{R},(\kappa_{1},i_{1}),(\kappa_{2},i_{2})}(\mathsf{r}^{\mathcal{T}}\\!(s)0^{2|\mathbb{L}_{1}|+k_{s}^{0}+k_{s}^{1}+\ell_{s}^{0}+\ell_{s}^{1}+j})$
$\displaystyle\mid\mathtt{R}\mathtt{\texttt{-}Add}^{I}_{\kappa_{1}\kappa_{2}}\in\mathsf{Rel}_{s},I=\\{i_{1}+1\\},$
$\displaystyle\hskip
12.91663pti_{1}+i_{2}=1,\mathsf{f}_{s}(\mathtt{R}\mathtt{\texttt{-}Add}^{I}_{\kappa_{1}\kappa_{2}})=j\\}$
$\displaystyle\mathcal{T}_{\mathtt{UUAdd},0}^{s}$
$\displaystyle=\\{\mathtt{Add}_{\mathtt{R},(\kappa,0)}(\mathsf{r}^{\mathcal{T}}\\!(s)0^{2|\mathbb{L}_{1}|+k_{s}^{1}+\ell_{s}^{0}+\ell_{s}^{1}+j})$
$\displaystyle\mid\mathsf{ar}(\mathtt{R})=1,\mathtt{R}\mathtt{\texttt{-}Add}_{\kappa}^{0}\in\mathsf{URel}_{s}^{0},\mathsf{f}_{s}^{0}(\mathtt{R}\mathtt{\texttt{-}Add}_{\kappa}^{0})=j\\}$
$\displaystyle\mathcal{T}_{\mathtt{UBAdd},0}^{s}$
$\displaystyle=\\{\mathtt{Add}_{\mathtt{R},(\kappa,0),(\kappa,0)}(\mathsf{r}^{\mathcal{T}}\\!(s)0^{2|\mathbb{L}_{1}|+k_{s}^{1}+\ell_{s}^{0}+\ell_{s}^{1}+j})$
$\displaystyle\mid\mathsf{ar}(\mathtt{R})=2,\mathtt{R}\mathtt{\texttt{-}Add}_{\kappa}^{0}\in\mathsf{URel}_{s}^{0},\mathsf{f}_{s}^{0}(\mathtt{R}\mathtt{\texttt{-}Add}_{\kappa}^{0})=j\\}$
$\displaystyle\mathcal{T}_{\mathtt{UUAdd},1}^{s}$
$\displaystyle=\\{\mathtt{Add}_{\mathtt{R},(\kappa,1)}(\mathsf{r}^{\mathcal{T}}\\!(s)0^{2|\mathbb{L}_{1}|+\ell_{s}^{0}+\ell_{s}^{1}+j})$
$\displaystyle\mid\mathsf{ar}(\mathtt{R})=1,\mathtt{R}\mathtt{\texttt{-}Add}_{\kappa}^{1}\in\mathsf{URel}_{s}^{1},\mathsf{f}_{s}^{1}(\mathtt{R}\mathtt{\texttt{-}Add}_{\kappa}^{1})=j\\}$
$\displaystyle\mathcal{T}_{\mathtt{UBAdd},1}^{s}$
$\displaystyle=\\{\mathtt{Add}_{\mathtt{R},(\kappa,1),(\kappa,1)}(\mathsf{r}^{\mathcal{T}}\\!(s)0^{2|\mathbb{L}_{1}|+\ell_{s}^{0}+\ell_{s}^{1}+j})$
$\displaystyle\mid\mathsf{ar}(\mathtt{R})=2,\mathtt{R}\mathtt{\texttt{-}Add}_{\kappa}^{1}\in\mathsf{URel}_{s}^{1},\mathsf{f}_{s}^{1}(\mathtt{R}\mathtt{\texttt{-}Add}_{\kappa}^{1})=j\\}$
$\displaystyle\mathcal{T}_{\mathtt{Rec},0}^{s}$
$\displaystyle=\\{\mathtt{Recolor}_{(\kappa,0)\hstretch{0.5}{\to}(\lambda,0)}(\mathsf{r}^{\mathcal{T}}\\!(s)0^{2|\mathbb{L}_{1}|+\ell_{s}^{1}+j})$
$\displaystyle\mid\lambda\mathtt{\texttt{-}ReCol}_{\kappa}^{0}\in\mathsf{Rec}_{s}^{0},\mathsf{g}_{s}^{0}(\lambda\mathtt{\texttt{-}ReCol}_{\kappa}^{0})=j$
$\displaystyle\hskip
12.91663pt\forall\mathrm{cyc}\in\mathsf{Rec}_{s}^{0}.\mathrm{cyc}=(0,\kappa_{1},\ldots,\kappa_{m})\rightarrow\kappa\neq\kappa_{1}\\}$
$\displaystyle\mathcal{T}_{\mathtt{Rec},1}^{s}$
$\displaystyle=\\{\mathtt{Recolor}_{(\kappa,1)\hstretch{0.5}{\to}(\lambda,1)}(\mathsf{r}^{\mathcal{T}}\\!(s)0^{2|\mathbb{L}_{1}|+j})$
$\displaystyle\mid\lambda\mathtt{\texttt{-}ReCol}_{\kappa}^{1}\in\mathsf{Rec}_{s}^{1},\mathsf{g}_{s}^{1}(\lambda\mathtt{\texttt{-}ReCol}_{\kappa}^{1})=j,$
$\displaystyle\hskip
12.91663pt\forall\mathrm{cyc}\in\mathsf{Rec}_{s}^{1}.\mathrm{cyc}=(1,\kappa_{1},\ldots,\kappa_{m})\rightarrow\kappa\neq\kappa_{1}\\}$
$\displaystyle\mathcal{T}_{\mathtt{CRecOp},0}^{s}$
$\displaystyle=\\{\mathtt{Recolor}_{(\kappa_{1},0)\hstretch{0.5}{\to}\mu_{\mathrm{cb}}}(\mathsf{r}^{\mathcal{T}}\\!(s)0^{2|\mathbb{L}_{1}|+\ell_{s}^{1}+j})$
$\displaystyle\mid\mathrm{cyc}\in\mathsf{Rec}_{s}^{0},\mathsf{g}_{s}^{0}(\mathrm{cyc})=j,\mathrm{cyc}=(0,\kappa_{1},\ldots,\kappa_{m})\\}$
$\displaystyle\mathcal{T}_{\mathtt{CRecClo},0}^{s}$
$\displaystyle=\\{\mathtt{Recolor}_{\mu_{\mathrm{cb}}\hstretch{0.5}{\to}(\kappa_{2},0)}(\mathsf{r}^{\mathcal{T}}\\!(s)0^{2|\mathbb{L}_{1}|+\ell_{s}^{1}+j})$
$\displaystyle\mid(0,\kappa_{1},\ldots,\kappa_{m})\in\mathsf{Rec}_{s}^{0},\mathsf{g}_{s}^{0}(\kappa_{2}\mathtt{\texttt{-}ReCol}_{\kappa_{1}}^{0})=j\\}$
$\displaystyle\mathcal{T}_{\mathtt{CRecOp},1}^{s}$
$\displaystyle=\\{\mathtt{Recolor}_{(\kappa_{1},1)\hstretch{0.5}{\to}\mu_{\mathrm{cb}}}(\mathsf{r}^{\mathcal{T}}\\!(s)0^{2|\mathbb{L}_{1}|+j})$
$\displaystyle\mid\mathrm{cyc}\in\mathsf{Rec}_{s}^{1},\mathsf{g}_{s}^{1}(\mathrm{cyc})=j,\mathrm{cyc}=(1,\kappa_{1},\ldots,\kappa_{m})\\}$
$\displaystyle\mathcal{T}_{\mathtt{CRecClo},1}^{s}$
$\displaystyle=\\{\mathtt{Recolor}_{\mu_{\mathrm{cb}}\hstretch{0.5}{\to}(\kappa_{2},1)}(\mathsf{r}^{\mathcal{T}}\\!(s)0^{2|\mathbb{L}_{1}|+j})$
$\displaystyle\mid(1,\kappa_{1},\ldots,\kappa_{m})\in\mathsf{Rec}_{s}^{1},\mathsf{g}_{s}^{1}(\kappa_{2}\mathtt{\texttt{-}ReCol}_{\kappa_{1}}^{1})=j\\}$
$\displaystyle\mathcal{T}_{\mathrm{pos},0}^{s}$
$\displaystyle=\\{\mathtt{Recolor}_{(\kappa,0)\hstretch{0.5}{\to}\kappa}(\mathsf{r}^{\mathcal{T}}\\!(s)0^{|\mathbb{L}_{1}|+j})$
$\displaystyle\mid\kappa\in\mathbb{L}_{1},\mathsf{coen}(\kappa)=j\\}$
$\displaystyle\mathcal{T}_{\mathrm{pos},1}^{s}$
$\displaystyle=\\{\mathtt{Recolor}_{(\kappa,1)\hstretch{0.5}{\to}\kappa}(\mathsf{r}^{\mathcal{T}}\\!(s)0^{j})$
$\displaystyle\mid\kappa\in\mathbb{L}_{1},\mathsf{coen}(\kappa)=j\\}.$

Thus we obtain a map that maps every $s\in P\oplus A_{P}$ to an instance
$\mathcal{T}_{\mathrm{cw}}^{s}$. We define
$\mathcal{T}_{\mathrm{cw}}^{\mathrm{aux}}=\bigcup_{s\in P\oplus
A_{P}}\mathcal{T}_{\mathrm{cw}}^{s}$. Finally,

$\mathcal{T}_{\mathrm{cw}}=\mathcal{T}_{\mathrm{bin}}\cup\mathcal{T}_{\mathrm{cw}}^{\mathrm{aux}}\cup\\{\mathtt{Void}(s)\mid\forall\mathtt{Dec}\in\mathrm{Dec}_{\mathrm{cw}}(\mathbb{L}^{*},\mathrm{Cnst},\Sigma).\mathtt{Dec}(s)\notin\mathcal{T}_{\mathrm{cw}}^{\mathrm{aux}}\\}.$

Additionally, we define a map
$h^{\mathcal{T}}\colon\mathsf{dom}(\mathcal{I}^{\mathcal{T}})\to\mathsf{dom}(\mathcal{I}^{\mathcal{T}_{\mathrm{cw}}})$
as follows:

$h^{\mathcal{T}}\\!(e)=\begin{cases}\mathtt{c},&\text{if }e=\mathtt{c}\text{
for some }\mathtt{c}\in\mathrm{Const},\\\
\mathsf{r}^{\mathcal{T}}\\!(e),&\text{otherwise}\end{cases}$

where $\mathcal{I}^{\mathcal{T}_{\mathrm{cw}}}$ is interpreted in the
cliquewidth sense [34, Definition 7]. $\Diamond$

######  Observation 50.

We observe the following:

  1. 1.

$\mathcal{T}_{\mathrm{cw}}$ is a
$(\mathbb{L}_{\mathrm{cw}},\mathrm{Const},\Sigma)$-well-decorated tree (in the
cliquewidth sense [34, Definition 6]).

  2. 2.

We observe that by construction $h^{\mathcal{T}}$ is a bijection.

######  Lemma 51.

Let $\Sigma$ be a binary signature and $\mathcal{T}$ a
$(\mathbb{L},\mathrm{Cnst},\Sigma)$-well-decorated tree. Then for all nodes
$s$ of $\mathcal{T}$ that are ancestors of pseudoleafs (or are itself a
pseudoleaf), $e\in\mathsf{ent}^{\mathcal{T}}\\!(s)$, and
$\kappa\in\mathbb{L}_{1}$ the following are equivalent:

  1. 1.

$e\in\mathsf{col}_{s}^{\mathcal{T}}(\kappa)$

  2. 2.

$\mathsf{col}_{\mathsf{r}^{\mathcal{T}}\\!(s)}^{\mathcal{T}_{\mathrm{cw}}}(h^{\mathcal{T}}\\!(e))=\kappa$
(in the cliquewidth sense [34, Definition 7]).

###### Proof.

Simple induction over the distance of $s$ from $s_{e}=\mathsf{orig}(e)$.

  * •

$s=s_{e}$. Then $e\in\mathsf{col}_{s}^{\mathcal{T}}(\kappa)$ iff
$\kappa=o_{1}$. This is equivalent to $\mathtt{c}(s)\in\mathcal{T}$ holding
for some $\mathtt{c}\in\mathrm{Cnst}{\oplus}\\{\ast\\}$. This is equivalent by
construction to
$\mathtt{c}_{o_{1}}(\mathsf{r}^{\mathcal{T}}\\!(s))\in\mathcal{T}_{\mathrm{cw}}$.
Which is equivalent to
$\mathsf{col}_{\mathsf{r}^{\mathcal{T}}\\!(s)}^{\mathcal{T}_{\mathrm{cw}}}(h^{\mathcal{T}}\\!e)=\kappa$.

  * •

$s$ is a proper ancestor of $s_{e}$ and the assertion holds for every node
$s^{\ast}$ being an ancestor of $s_{e}$ such that $s^{\prime}$ is a proper
ancestor of $s^{\ast}$. Consequently also for the unique $s^{\prime}$ such
that $s^{\prime}=si_{s}$ and $s^{\prime}$ is an ancestor of $s_{e}$. Assume
$e\in\mathsf{col}_{s}^{\mathcal{T}}(\kappa)$.We have two cases to consider:

    * –

$e\in\mathsf{col}_{si_{s}}^{\mathcal{T}}(\kappa)$. Then
$\lambda\mathtt{\texttt{-}ReCol}_{\kappa}^{i_{s}}(s)\notin\mathcal{T}$ for all
$\lambda\in\mathbb{L}_{1}$, $\lambda\neq\kappa$. Hence for all nodes $v$ of
$\mathcal{T}_{cw}$ that are proper ancestors of
$\mathsf{r}^{\mathcal{T}}\\!(si_{s})$ and for whom
$\mathsf{r}^{\mathcal{T}}\\!(s)$ is an ancestor,
$\mathtt{Recolor}_{(\kappa,i_{s})\hstretch{0.5}{\to}(\lambda,i_{s})}(v)\notin\mathcal{T}_{\mathrm{cw}}$
for all $\lambda\neq\kappa$. As
$\mathsf{col}_{\mathsf{r}^{\mathcal{T}}\\!(si_{s})}^{\mathcal{T}_{\mathrm{cw}}}(h^{\mathcal{T}}\\!(e))=\kappa$
by assumption, we conclude
$\mathsf{col}_{\mathsf{r}^{\mathcal{T}}\\!(s)}^{\mathcal{T}_{\mathrm{cw}}}(h^{\mathcal{T}}\\!(e))=\kappa$.
The other direction is completely analogous.

    * –

$e\in\mathsf{col}_{si_{s}}^{\mathcal{T}}(\lambda)$ for
$\lambda\in\mathbb{L}_{1}$, $\lambda\neq\kappa$. Then
$\kappa\mathtt{\texttt{-}ReCol}_{\lambda}^{i_{s}}(s)\in\mathcal{T}$. By
construction there is a node $v$ of $\mathcal{T}_{cw}$ that is a proper
ancestors of $\mathsf{r}^{\mathcal{T}}\\!(si_{s})$ and for whom
$\mathsf{r}^{\mathcal{T}}\\!(s)$ is an ancestor, such that
$\mathtt{Recolor}_{(\lambda,i_{s})\hstretch{0.5}{\to}(\kappa,i_{s})}(v)\in\mathcal{T}_{\mathrm{cw}}$.
As
$\mathsf{col}_{\mathsf{r}^{\mathcal{T}}\\!(si_{s})}^{\mathcal{T}_{\mathrm{cw}}}(h^{\mathcal{T}}\\!(e))=\lambda$
by assumption, we conclude
$\mathsf{col}_{\mathsf{r}^{\mathcal{T}}\\!(s)}^{\mathcal{T}_{\mathrm{cw}}}(h^{\mathcal{T}}\\!(e))=\kappa$.
The other direction is completely analogous.

∎

######  Proposition 29.

Let $\mathcal{I}$ be a countable instance over a binary signature $\Sigma$.
$\mathcal{I}$ has finite cliquewidth iff $\mathcal{I}$ has finite
partitionwidth.

###### Proof.

By Proposition 47 it suffices to prove that, given an instance $\mathcal{I}$
over a binary signature $\Sigma$ with finite partitionwidth, $\mathcal{I}$
also has finite cliquewidth. So let $\Sigma$ be a finite binary signature,
$\mathbb{L}$ finite set of colors (of arity $\leq 2$) and $\mathrm{Const}$ a
finite set of constants. Assume $\mathcal{T}$ to be a
$(\mathbb{L},\mathrm{Cnst},\Sigma)$-well-decorated tree (in the partitionwidth
sense, Definition 16) in normal form such that
$\mathcal{I}=\mathcal{I}^{\mathcal{T}}$. This can be achieved by renaming (if
necessary) of the nulls in $\mathcal{I}$. Let
$\mathbb{L}^{\ast}=\mathbb{L}_{1}\oplus(\mathbb{L}_{1}\times\\{0,1\\})\oplus\\{\mu_{\mathrm{cb}}\\}$
and $\mathcal{T}_{\mathrm{cw}}$ as in Definition 49. If we show
$h^{\mathcal{T}}\colon\mathcal{I}^{\mathcal{T}}\to\mathcal{I}^{\mathcal{T}_{\mathrm{cw}}}$
to be an isomorphism we are done. Since by 50, Item 1 we know
$h^{\mathcal{T}}$ to be bijective, we only prove it to be an isomorphism. In
the following we use all the defined auxillary maps, sets and instances as
denoted in the construction in Definition 49.

Let $\mathtt{R}(\boldsymbol{e})\in\mathcal{I}$. Note that this automatically
implies, that $\varepsilon$ is not a pseudoleaf (in $\mathcal{T}$). We
consider two cases:

  * •

$\boldsymbol{e}=(e,e)$ or $\boldsymbol{e}=e$ for some entity $e$. Then let
$s_{e}=\mathsf{orig}(e)$, $s_{e}^{\prime}\in\\{0,1\\}^{*}$, and
$i_{e}\in\\{0,1\\}$ such that $s_{e}=s^{\prime}_{e}i_{e}$. Since $\mathcal{T}$
is in normal form, we conclude that
$\mathtt{R}\mathtt{\texttt{-}Add}_{o_{\mathsf{ar}(\mathtt{R})}}^{i_{e}}(s_{e}^{\prime})\in\mathcal{T}$.
As $s_{e}$ is a pseudoleaf by definition, there is a unique
$\mathtt{c}\in\mathrm{Cnst}\oplus\\{\ast\\}$ such that
$\mathtt{c}(s)\in\mathcal{T}$. By construction,
$\mathtt{c}_{o_{1}}(\mathsf{r}^{\mathcal{T}}\\!(s))\in\mathcal{T}_{\mathrm{cw}}$.
Additionally,
$\mathtt{Recolor}_{o_{1}\hstretch{0.5}{\to}(o_{1},i_{e})}(v)\in\mathcal{T}^{s_{e}^{\prime}}_{\mathrm{cw}}$
for some node $v\in\\{0,1\\}^{\ast}$ of $\mathcal{T}_{\mathrm{cw}}$ such that

    * –

$\mathsf{r}^{\mathcal{T}}\\!(s^{\prime}_{e})$ is a proper ancestor of $v$, and

    * –

$v$ is a proper ancestor of $\mathsf{r}^{\mathcal{T}}\\!(s)$.

Finally, since
$\mathtt{R}\mathtt{\texttt{-}Add}_{o_{\mathsf{ar}(\mathtt{R})}}^{i_{e}}(s_{e}^{\prime})\in\mathcal{T}$
there is another node $v^{\prime}$ satisfying both

    * –

$\mathsf{r}^{\mathcal{T}}\\!(s^{\prime}_{e})$ is a proper ancestor of
$v^{\prime}$, and

    * –

$v^{\prime}$ is a proper ancestor of $v$

such that either
$\mathtt{Add}_{\mathtt{R},(o_{1},i_{e}),(o_{1},i_{e})}(v^{\prime})\in\mathcal{T}_{\mathrm{cw}}$
or
$\mathtt{Add}_{\mathtt{R},(o_{1},i_{e})}(v^{\prime})\in\mathcal{T}_{\mathrm{cw}}$
depending on whether $\mathsf{ar}(\mathtt{R})=2$ or
$\mathsf{ar}(\mathtt{R})=1$. By construction of $\mathcal{T}_{\mathrm{cw}}$
and $\mathrm{Atoms}_{v^{\prime}}$ [34, Definition 7], we obtain
$\mathtt{R}(h^{\mathcal{T}}\\!(\boldsymbol{e}))\in\mathrm{Atoms}_{v^{\prime}}$
and hence
$\mathtt{R}(h^{\mathcal{T}}\\!(\boldsymbol{e}))\in\mathcal{I}^{\mathcal{T}_{\mathrm{cw}}}$.

  * •

$\boldsymbol{e}\neq(e,\ldots,e)$ for every entity $e$. This implies
immediately that $\mathsf{ar}(\mathtt{R})=2$. Hence
$\boldsymbol{e}=(e_{1},e_{2})$ with $e_{1}\neq e_{2}$. Furthermore, as
$\mathcal{T}$ is in normal form, for
$s_{\boldsymbol{e}}=\mathsf{cca}(\mathsf{orig}(\boldsymbol{e}))$ there are
some $\kappa_{1},\kappa_{2}\in\mathbb{L}$ with
$\mathsf{ar}(\kappa_{1})=\mathsf{ar}(\kappa_{2})=1$ and $I={i^{*}}$ with
$i^{*}\in\\{1,2\\}$ such that

    * –

$\mathtt{R}\mathtt{\texttt{-}Add}^{\\{i^{*}\\}}_{\kappa_{1}\kappa_{2}}(s_{\boldsymbol{e}})\in\mathcal{T}$,

    * –

$e_{i^{*}}\in\mathsf{col}_{s_{\boldsymbol{e}}0}^{\mathcal{T}}(\kappa_{1})$,
and

    * –

$e_{j}\in\mathsf{col}_{s_{\boldsymbol{e}}1}^{\mathcal{T}}(\kappa_{2})$ such
that $\\{i^{*},j\\}=\\{1,2\\}$.

By construction, there are nodes $v,v_{0},v_{1}\in\\{0,1\\}^{\ast}$ from
$\mathcal{T}_{\mathrm{cw}}$ such that

    * –

$v$ is a proper ancestor to $v_{0}$ and $v_{1}$,

    * –

$\mathsf{r}^{\mathcal{T}}\\!(s)$ is a proper ancestor of $v$,

    * –

$v_{0}$ is a proper ancestor $\mathsf{r}^{\mathcal{T}}\\!(s0)$, $v_{1}$ is a
proper ancestor of $\mathsf{r}^{\mathcal{T}}\\!(s1)$,

    * –

if $i^{*}=1$,
$\mathtt{Add}_{\mathtt{R},(\kappa_{1},0),(\kappa_{2},1)}(v)\in\mathcal{T}_{\mathrm{cw}}$,
if $i^{*}=2$,
$\mathtt{Add}_{\mathtt{R},(\kappa_{2},1),(\kappa_{1},0)}(v)\in\mathcal{T}_{\mathrm{cw}}$,
and

    * –

$\mathtt{Recolor}_{\kappa_{1}\hstretch{0.5}{\to}(\kappa_{1},0)}(v_{0}),\mathtt{Recolor}_{\kappa_{2}\hstretch{0.5}{\to}(\kappa_{2},1)}(v_{1})$.

Applying Lemma 51 we obtain
$\mathsf{col}_{\mathsf{r}^{\mathcal{T}}\\!(s_{\boldsymbol{e}}0)}^{\mathcal{T}_{\mathrm{cw}}}(e_{i^{\ast}})=\kappa_{1}$
and
$\mathsf{col}_{\mathsf{r}^{\mathcal{T}}\\!(s_{\boldsymbol{e}}1)}^{\mathcal{T}_{\mathrm{cw}}}(e_{j})=\kappa_{2}$.
Hence by construction
$\mathsf{col}_{v0}^{\mathcal{T}_{\mathrm{cw}}}(h^{\mathcal{T}}\\!(e_{i^{\ast}}))=(\kappa_{1},0)$
and $\mathsf{col}_{v0}^{\mathcal{T}_{\mathrm{cw}}}(h(e_{j}))=(\kappa_{2},1)$.
Consequently
$\mathtt{R}(h^{\mathcal{T}}\\!\boldsymbol{e})\in\mathrm{Atoms}_{v}$ and thus
$\mathtt{R}(h^{\mathcal{T}}\\!(\boldsymbol{e}))\in\mathcal{I}^{\mathcal{T}_{\mathrm{cw}}}$.

Now assume
$\mathtt{R}(h^{\mathcal{T}}\\!(\boldsymbol{e}))\in\mathcal{I}^{\mathcal{T}_{\mathrm{cw}}}$
for $\boldsymbol{e}$ from $\mathsf{dom}(\mathcal{I}^{\mathcal{T}})$. Note that
this captures all the atoms in $\mathcal{I}^{\mathcal{T}_{\mathrm{cw}}}$ as
$h^{\mathcal{T}}$ is a bijection on the sets of entities corresponding to the
instances $\mathcal{I}=\mathcal{I}^{\mathcal{T}}$ and
$\mathcal{I}^{\mathcal{T}_{\mathrm{cw}}}$. We again consider two cases:

  * •

$\boldsymbol{e}=(e,e)$ or $\boldsymbol{e}=e$ for some entity $e$ of
$\mathcal{I}$. Let $s=\mathsf{orig}(e)$ be the node of $\mathcal{T}$
introducing entity $e$. By construction there is a node $v$ in
$\mathcal{T}_{\mathrm{cw}}$ such that $\mathsf{r}^{\mathcal{T}}\\!(s)=v$ and
there is a $\mathtt{c}\in\mathrm{Cnst}{\oplus}\\{\ast\\}$ such that
$\mathtt{c}(s)\in\mathcal{T}$ and
$\mathtt{c}_{o_{1}}(v)\in\mathcal{T}_{\mathrm{cw}}$. Let $s^{\prime}$ be the
unique parent of $s$ in $\mathcal{T}$ and $i_{s}\in\\{0,1\\}$ such that
$s=s^{\prime}i_{s}$. Again by construction, there are nodes
$v_{i_{s}},v^{\prime}$ of $\mathcal{T}_{\mathrm{cw}}$ such that

    * –

$\mathsf{r}^{\mathcal{T}}\\!(s^{\prime})$ is a proper ancestor of
$v^{\prime},v_{i_{s}},v$,

    * –

$v^{\prime}$ is a proper ancestor of $v_{i_{s}}$ and $v$,

    * –

$v_{i_{s}}$ is a proper ancestor of $v$,

    * –

$\mathtt{Recolor}_{o_{1}\hstretch{0.5}{\to}(o_{1},i_{s})}(v_{i_{s}})\in\mathcal{T}_{\mathrm{cw}}$,

    * –

$\mathtt{Add}_{\mathtt{R},(o_{1},i_{s}),(o_{1},i_{s})}$ or
$\mathtt{Add}_{\mathtt{R},(o_{1},i_{s})}$ depending on
$\mathsf{ar}(\mathtt{R})=2$ or $\mathsf{ar}(\mathtt{R})=1$.

By construction we may obtain
$\mathtt{R}\mathtt{\texttt{-}Add}_{o_{2}}^{i_{s}}(s^{\prime})\in\mathcal{T}$
or
$\mathtt{R}\mathtt{\texttt{-}Add}_{o_{1}}^{i_{s}}(s^{\prime})\in\mathcal{T}$
depending on $\mathsf{ar}(\mathtt{R})=2$ or $\mathsf{ar}(\mathtt{R})=1$.
Consequently,
$\mathtt{R}(\boldsymbol{e})\in\mathcal{I}^{\mathcal{T}}=\mathcal{I}$.

  * •

$\boldsymbol{e}\neq(e,\ldots,e)$ for every entity $e$. This implies
immediately that $\mathsf{ar}(\mathtt{R})=2$. Hence
$\boldsymbol{e}=(e_{1},e_{2})$ with $e_{1}\neq e_{2}$. Let
$s_{\boldsymbol{e}}=\mathsf{cca}(\mathsf{orig}(\boldsymbol{e}))$. Since
$\mathtt{R}(h^{\mathcal{T}}\\!(\boldsymbol{e}))\in\mathcal{I}^{\mathcal{T}_{\mathrm{cw}}}$
there is by construction a node $v$ in $\mathcal{T}_{\mathrm{cw}}$ such that
$\mathtt{Add}_{\mathtt{R},(\kappa_{1},i_{1}),(\kappa_{2},i_{2})}(v)\in\mathcal{T}_{\mathrm{cw}}$
with $\\{i_{1},i_{2}\\}=\\{1,2\\}$,
$\mathsf{col}_{v}^{\mathcal{T}_{\mathrm{cw}}}(h^{\mathcal{T}}\\!(e_{1}))=(\kappa_{1},i_{1})$
and
$\mathsf{col}_{v}^{\mathcal{T}_{\mathrm{cw}}}(h^{\mathcal{T}}\\!(e_{2}))=(\kappa_{2},i_{2})$.
Furthermore, $v$ satisfies the following property: $v$ is a proper ancestor to
both $\mathsf{r}^{\mathcal{T}}\\!(s0)$ and $\mathsf{r}^{\mathcal{T}}\\!(s1)$
and $\mathsf{r}^{\mathcal{T}}\\!(s)$ is a proper ancestor to $v$. Also, by
construction we immediately obtain
$\mathsf{col}_{\mathsf{r}^{\mathcal{T}}(s(i_{1}-1))}^{\mathcal{T}_{\mathrm{cw}}}(h^{\mathcal{T}}\\!(e_{1}))=\kappa_{1}$
and
$\mathsf{col}_{\mathsf{r}^{\mathcal{T}}(s(i_{2}-1))}^{\mathcal{T}_{\mathrm{cw}}}(h^{\mathcal{T}}\\!(e_{2}))=\kappa_{2}$.
Again by construction we now that
$\mathtt{R}\mathtt{\texttt{-}Add}^{\\{i_{1}\\}}_{\kappa_{1}\kappa_{2}}(s)\in\mathcal{T}$.
Finally, applying Lemma 51 we obtain
$e_{1}\in\mathsf{col}_{s(i_{1}-1)}^{\mathcal{T}}(\kappa_{1})$ and
$e_{2}\in\mathsf{col}_{s(i_{2}-1)}^{\mathcal{T}}(\kappa_{2})$. Together this
implies $\mathtt{R}(e_{1},e_{2})\in\mathrm{Atoms}_{s}$ and hence
$\mathtt{R}(\boldsymbol{e})\in\mathcal{I}^{\mathcal{T}}=\mathcal{I}$.

This proves that $h^{\mathcal{T}}$ is an isomorphism between
$\mathcal{I}=\mathcal{I}^{\mathcal{T}}$ and
$\mathcal{I}^{\mathcal{T}_{\mathrm{cw}}}$. As
$|\mathbb{L}_{\mathrm{cw}}|=3\cdot|\mathbb{L}_{1}|+1<3\cdot|\mathbb{L}|+1$ we
conclude that since $\mathcal{I}$ has finite partitionwidth, it has also
finite cliquewidth. ∎

###  B-E Proofs for Section IX

######  Lemma 34.

Let $\mathcal{R}$ be a ruleset. If
$\mathcal{R}=\mathcal{R}_{1}\triangleright\cdots\triangleright\mathcal{R}_{n}$,
then for any database $\mathcal{D}$, the following holds:

$\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R})=\mathbf{Ch}_{\infty}(\ldots\mathbf{Ch}_{\infty}(\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{1}),\mathcal{R}_{2})\ldots,\mathcal{R}_{n}).$

###### Proof.

We prove the result by induction on $n$.

Base case. Let $\mathcal{R}=\mathcal{R}_{1}\triangleright\mathcal{R}_{2}$. We
argue two cases: we first argue (i) that
$\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R})\subseteq\mathbf{Ch}_{\infty}(\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{1}),\mathcal{R}_{2})$,
and then that (ii) show that
$\mathbf{Ch}_{\infty}(\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{1}),\mathcal{R}_{2})\subseteq\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R})$.

For case (i), let us suppose that
$\mathtt{R}(\boldsymbol{t})\in\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R})$.
If $\mathtt{R}(\boldsymbol{t})\in\mathcal{D}$, then
$\mathtt{R}(\boldsymbol{t})\in\mathbf{Ch}_{\infty}(\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{1}),\mathcal{R}_{2})$,
so let us assume that there exists an $i$ such that
$\mathtt{R}(\boldsymbol{t})\in\mathbf{Ch}_{i}(\mathcal{D},\mathcal{R})$, but
$\mathtt{R}(\boldsymbol{t})\not\in\mathbf{Ch}_{j}(\mathcal{D},\mathcal{R})$
for $j<i$. It follows that there exists a trigger $(\rho,h)$ of
$\mathbf{Ch}_{i-1}(\mathcal{D},\mathcal{R})$ such that
$\mathtt{R}(\boldsymbol{t})\in\overline{h}(\mathsf{head}(\rho))$. Either
$\rho\in\mathcal{R}_{1}$ or $\rho\in\mathcal{R}_{2}$. If
$\rho\in\mathcal{R}_{1}$, then since no rule of $\mathcal{R}_{1}$ depends on a
rule in $\mathcal{R}_{2}$, it follows that
$\mathtt{R}(\boldsymbol{t})\in\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{1})$,
meaning
$\mathtt{R}(\boldsymbol{t})\in\mathbf{Ch}_{\infty}(\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{1}),\mathcal{R}_{2})$.
If $\rho\in\mathcal{R}_{2}$, then
$\mathtt{R}(\boldsymbol{t})\in\mathbf{Ch}_{\infty}(\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{1}),\mathcal{R}_{2})$,
which completes the proof of case (i).

For case (ii), let us suppose that
$\mathtt{R}(\boldsymbol{t})\in\mathbf{Ch}_{\infty}(\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{1}),\mathcal{R}_{2})$.
If $\mathtt{R}(\boldsymbol{t})\in\mathcal{D}$, then
$\mathtt{R}(\boldsymbol{t})\in\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R})$,
so let us suppose that $\mathtt{R}(\boldsymbol{t})\not\in\mathcal{D}$. Either
$\mathtt{R}(\boldsymbol{t})\in\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{1})$
or
$\mathtt{R}(\boldsymbol{t})\in\mathbf{Ch}_{\infty}(\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{1}),\mathcal{R}_{2})$.
Regardless of the case, one can see that
$\mathtt{R}(\boldsymbol{t})\in\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R})$.

Inductive step. Suppose that
$\mathcal{R}=\mathcal{R}_{1}\triangleright\cdots\triangleright\mathcal{R}_{n}$,
and let $\mathcal{R}^{\prime}=\bigcup_{i\in\\{1,\ldots
n-1\\}}\mathcal{R}_{i}$, from which it follows that
$\mathcal{R}^{\prime}=\mathcal{R}_{1}\triangleright\cdots\triangleright\mathcal{R}_{n-1}$.
By the base case, we know that
$\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R})=\mathbf{Ch}_{\infty}(\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}^{\prime}),\mathcal{R}_{n})$,
and by IH, we know that

$\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}^{\prime})=\mathbf{Ch}_{\infty}(\ldots\mathbf{Ch}_{\infty}(\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{1}),\mathcal{R}_{2})\ldots,\mathcal{R}_{n-1}).$

Therefore,
$\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R})=\mathbf{Ch}_{\infty}(\ldots\mathbf{Ch}_{\infty}(\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{1}),\mathcal{R}_{2})\ldots,\mathcal{R}_{n}).$
∎

###  B-F Proofs for Section X

######  Proposition 37.

Let
$\mathcal{R}=\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}}$
be a ruleset where $\mathcal{R}_{\smash{\mathrm{fr1}}}$ is frontier-one and
$\mathcal{R}_{\smash{\mathrm{bdl}}}$ is $\mathbf{fus}$ datalog. Then
$\mathcal{R}$ is $\mathbf{fps}$ and thus allows for decidable HUSOMSOQ
entailment.

###### Proof.

We define an atom
$\mathtt{R}(\boldsymbol{t})\in\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}})$
to be a _bdl-atom_ iff $\mathtt{R}(\boldsymbol{t})$ was introduced at some
step of the chase by a rule in $\mathcal{R}_{\smash{\mathrm{bdl}}}$. We define

$\mathbf{Ch}_{\smash{\mathrm{fr1}}}(\mathcal{D},\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}})=\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}})\setminus\\{\mathtt{R}(\boldsymbol{t})\
|\ \mathtt{R}(\boldsymbol{t})\text{ is a bdl-atom.}\\}$

It is straightforward to confirm that
$\mathbf{Ch}_{\smash{\mathrm{fr1}}}(\mathcal{D},\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}})$
has finite treewidth, and thus, the instance has finite partitionwidth by
Theorem 28.

Let us now take the ruleset $\mathcal{R}_{\smash{\mathrm{bdl}}}$ and observe
that every rule in $\mathcal{R}_{\smash{\mathrm{bdl}}}$ is a datalog rule of
the form
$\forall\boldsymbol{x}\boldsymbol{y}(\varphi(\boldsymbol{x},\boldsymbol{y})\rightarrow\mathtt{R}_{1}(\boldsymbol{z}_{1})\land\cdots\land\mathtt{R}_{n}(\boldsymbol{z}_{n}))$
with $\boldsymbol{z}_{1},\ldots,\boldsymbol{z}_{n}$ all variables in
$\boldsymbol{y}$. We can therefore re-write each such rule as the following,
equivalent set of single-headed rules:

$\\{\forall\boldsymbol{x}\boldsymbol{y}(\varphi(\boldsymbol{x},\boldsymbol{y})\rightarrow\mathtt{R}_{1}(\boldsymbol{z}_{1})),\ldots,\forall\boldsymbol{x}\boldsymbol{y}(\varphi(\boldsymbol{x},\boldsymbol{y})\rightarrow\mathtt{R}_{n}(\boldsymbol{z}_{n}))\\}$

Based on this fact, we may assume w.l.o.g. that every rule in
$\mathcal{R}_{\smash{\mathrm{bdl}}}$ is a single-headed rule.

Let us now re-write $\mathcal{R}_{\smash{\mathrm{bdl}}}$ relative to itself.
To do this, we first define the re-writing of each rule in
$\mathcal{R}_{\smash{\mathrm{bdl}}}$. For each rule
$\rho=\forall\boldsymbol{x}\boldsymbol{y}(\varphi(\boldsymbol{x},\boldsymbol{y})\rightarrow\mathtt{R}(\boldsymbol{y}))\in\mathcal{R}_{\smash{\mathrm{bdl}}}$,
we define the re-writing of $\rho$ accordingly:

$\mathsf{rew}(\rho):=\\{\psi(\boldsymbol{x},\boldsymbol{y})\rightarrow\mathtt{R}(\boldsymbol{y})\
|\
\exists\psi(\boldsymbol{x},\boldsymbol{y})\in\mathsf{rew}_{\mathcal{R}_{\smash{\mathrm{bdl}}}}(\mathtt{R}(\boldsymbol{y}))\\}$

We then define the re-writing of $\mathcal{R}_{\smash{\mathrm{bdl}}}$ as
follows:
$\mathcal{R}_{\smash{\mathrm{bdl}}}^{\prime}:=\bigcup_{\rho\in\mathcal{R}_{\smash{\mathrm{bdl}}}}\mathsf{rew}(\rho)$.
Since $\mathcal{R}_{\smash{\mathrm{bdl}}}$ is $\mathbf{fus}$, it follows that
$\mathcal{R}_{\smash{\mathrm{bdl}}}^{\prime}$ is finite. Additionally,
$\mathcal{R}_{\smash{\mathrm{bdl}}}^{\prime}$ is a datalog ruleset consisting
solely of single-headed rules by definition, and so, we assume that the
ruleset has the following form:

$\mathcal{R}_{\smash{\mathrm{bdl}}}^{\prime}=\\{\psi_{1}(\boldsymbol{x},\boldsymbol{y})\rightarrow\mathtt{R}_{1}(\boldsymbol{y}),\ldots,\psi_{n}(\boldsymbol{x},\boldsymbol{y})\rightarrow\mathtt{R}_{n}(\boldsymbol{y})\\}$

We now show the following: For any
$\mathtt{R}(\boldsymbol{t})\in\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}})\setminus\mathbf{Ch}_{\smash{\mathrm{fr1}}}(\mathcal{D},\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}})$,
there exists a trigger $(\rho,h)$ in
$\mathbf{Ch}_{\smash{\mathrm{fr1}}}(\mathcal{D},\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}})$
with $\rho\in\mathcal{R}_{\smash{\mathrm{bdl}}}^{\prime}$ such that applying
$(\rho,h)$ adds $\mathtt{R}(\boldsymbol{t})$ to
$\mathbf{Ch}_{\smash{\mathrm{fr1}}}(\mathcal{D},\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}})$.
To see this, observe that since $\mathcal{R}_{\smash{\mathrm{bdl}}}$ is
$\mathbf{fus}$, we know by definition that for any predicate $\mathtt{R}$
occurring in any rule head of $\mathcal{R}_{\smash{\mathrm{bdl}}}$ and any
tuple $\boldsymbol{t}$ of terms in
$\mathbf{Ch}_{\smash{\mathrm{fr1}}}(\mathcal{D},\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}})$,
it holds that
$\mathbf{Ch}_{\infty}(\mathbf{Ch}_{\smash{\mathrm{fr1}}}(\mathcal{D},\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}}),\mathcal{R}_{\smash{\mathrm{bdl}}})\models\mathtt{R}(\boldsymbol{t})$
iff there exists a CQ $\psi(\boldsymbol{x},\boldsymbol{y})$ in
$\mathsf{rew}_{\mathcal{R}}(\mathtt{R}(\boldsymbol{y}))$ such that
$\mathbf{Ch}_{\smash{\mathrm{fr1}}}(\mathcal{D},\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}})\models\exists\boldsymbol{x}\psi(\boldsymbol{x},\boldsymbol{t})$.
It therefore follows that a trigger exists for
$\rho\in\mathcal{R}_{\smash{\mathrm{bdl}}}^{\prime}$ in
$\mathbf{Ch}_{\smash{\mathrm{fr1}}}(\mathcal{D},\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}})$.

Based on the above fact, the following equation holds:

$\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}})=\mathbf{Ch}_{1}(\mathbf{Ch}_{\smash{\mathrm{fr1}}}(\mathcal{D},\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}}),\mathcal{R}_{\smash{\mathrm{bdl}}}^{\prime})$

Recall that $\mathcal{R}_{\smash{\mathrm{bdl}}}^{\prime}$ is of the form
$\\{\psi_{i}(\boldsymbol{x},\boldsymbol{y})\rightarrow\mathtt{R}_{i}(\boldsymbol{y})\
|\ 1\leq i\leq n\\}$. The right hand side of the above equation can be re-
written as a finite sequence of FO-extensions as shown below:666For the
definition of an FO-extension, see Section VI-C.

$\mathbf{Ch}_{1}(\mathbf{Ch}_{\smash{\mathrm{fr1}}}(\mathcal{D},\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}}),\mathcal{R}_{\smash{\mathrm{bdl}}}^{\prime})=(\ldots(\mathbf{Ch}_{\smash{\mathrm{fr1}}}(\mathcal{D},\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}}))^{\mathtt{R}_{1}:=\mathtt{R}_{1}\cup\psi_{1}})\ldots)^{\mathtt{R}_{n}:=\mathtt{R}_{n}\cup\psi_{n}}$

By what was argued above,
$\mathbf{Ch}_{\smash{\mathrm{fr1}}}(\mathcal{D},\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}})$
has finite partitionwidth, and since this property is preserved under FO-
extensions (by Theorem 27), it follows that

$\mathbf{Ch}_{1}(\mathbf{Ch}_{\smash{\mathrm{fr1}}}(\mathcal{D},\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}}),\mathcal{R}_{\smash{\mathrm{bdl}}}^{\prime})$

has finite partitionwidth and hence,
$\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}})$
has finite partitionwidth. Therefore, by Theorem 6,
$\mathcal{R}_{\smash{\mathrm{fr1}}}\cup\mathcal{R}_{\smash{\mathrm{bdl}}}$
allows for decidable HUSOMSOQ entailment. ∎

######  Proposition 52.

Every bounded datalog ruleset is $\mathbf{fods}$.

###### Proof.

Consider a bounded datalog ruleset $\mathcal{R}$ and observe that every rule
in $\mathcal{R}$ is a datalog rule of the form
$\forall\boldsymbol{x}\boldsymbol{y}(\varphi(\boldsymbol{x},\boldsymbol{y})\rightarrow\mathtt{R}_{1}(\boldsymbol{z}_{1})\land\cdots\land\mathtt{R}_{n}(\boldsymbol{z}_{n}))$
with $\boldsymbol{z}_{1},\ldots,\boldsymbol{z}_{n}$ all variables in
$\boldsymbol{y}$. We can therefore re-write each such rule as the following,
equivalent set of single-headed rules:

$\\{\forall\boldsymbol{x}\boldsymbol{y}(\varphi(\boldsymbol{x},\boldsymbol{y})\rightarrow\mathtt{R}_{1}(\boldsymbol{z}_{1})),\ldots,\forall\boldsymbol{x}\boldsymbol{y}(\varphi(\boldsymbol{x},\boldsymbol{y})\rightarrow\mathtt{R}_{n}(\boldsymbol{z}_{n}))\\}$

Based on this fact, we may assume w.l.o.g. that every rule in $\mathcal{R}$ is
a single-headed rule.

We will next re-write $\mathcal{R}$ relative to itself. To do this, we first
define the re-writing of each rule in $\mathcal{R}$. For each rule
$\rho=\forall\boldsymbol{x}\boldsymbol{y}(\varphi(\boldsymbol{x},\boldsymbol{y})\rightarrow\mathtt{R}(\boldsymbol{y}))\in\mathcal{R}$,
we define the re-writing of $\rho$ accordingly:

$\mathsf{rew}(\rho):=\\{\psi(\boldsymbol{x},\boldsymbol{y})\rightarrow\mathtt{R}(\boldsymbol{y})\mid\psi(\boldsymbol{x},\boldsymbol{y})\in\mathsf{rew}_{\mathcal{R}}(\mathtt{R}(\boldsymbol{y}))\\}$

We then define the re-writing of $\mathcal{R}$ as follows:
$\mathcal{R}^{\prime}:=\bigcup_{\rho\in\mathcal{R}}\mathsf{rew}(\rho)$. Since
$\mathcal{R}$ is $\mathbf{fus}$ by assumption, it follows that
$\mathcal{R}^{\prime}$ is finite. Additionally, $\mathcal{R}^{\prime}$ is a
datalog ruleset consisting solely of single-headed rules by definition, and
so, we assume that the ruleset has the following form:

$\mathcal{R}^{\prime}=\\{\psi_{1}(\boldsymbol{x},\boldsymbol{y})\rightarrow\mathtt{R}_{1}(\boldsymbol{y}),\ldots,\psi_{n}(\boldsymbol{x},\boldsymbol{y})\rightarrow\mathtt{R}_{n}(\boldsymbol{y})\\}$

We now show the following: For any $\mathcal{I}$ and any
$\mathtt{R}(\boldsymbol{t})\in\mathbf{Ch}_{\infty}(\mathcal{I},\mathcal{R})\setminus\mathcal{I}$,
there exists a trigger $(\rho,h)$ in $\mathcal{I}$ with
$\rho\in\mathcal{R}^{\prime}$ such that applying $(\rho,h)$ adds
$\mathtt{R}(\boldsymbol{t})$ to $\mathcal{I}$. To see this, observe that since
$\mathcal{R}$ is $\mathbf{fus}$, we know by definition that for any predicate
$\mathtt{R}$ occurring in any rule head of $\mathcal{R}$ and any tuple
$\boldsymbol{t}$ of terms in $\mathcal{I}$, it holds that
$\mathbf{Ch}_{\infty}(\mathcal{I},\mathcal{R})\models\mathtt{R}(\boldsymbol{t})$
iff there exists a CQ
$\exists\boldsymbol{x}.\psi(\boldsymbol{x},\boldsymbol{y})$ in
$\mathsf{rew}_{\mathcal{R}}(\mathtt{R}(\boldsymbol{y}))$ such that
$\mathcal{I}\models\exists\boldsymbol{x}\psi(\boldsymbol{x},\boldsymbol{t})$.
It therefore follows that a trigger exists for the corresponding
$\rho\in\mathcal{R}_{\smash{\mathrm{bdl}}}^{\prime}$ in $\mathcal{I}$.

Based on the above fact, we obtain
$\mathbf{Ch}_{\infty}(\mathcal{I},\mathcal{R})=\mathbf{Ch}_{1}(\mathcal{I},\mathcal{R}^{\prime}).$
Recall that $\mathcal{R}_{\smash{\mathrm{bdl}}}^{\prime}$ is of the form
$\\{\psi_{i}(\boldsymbol{x},\boldsymbol{y})\rightarrow\mathtt{R}_{i}(\boldsymbol{y})\
|\ 1\leq i\leq n\\}$. Yet, the right hand side of the above equation can be
re-written as a finite sequence of FO-extensions as shown below:

$\mathbf{Ch}_{1}(\mathcal{I},\mathcal{R}^{\prime})=(\ldots(\mathcal{I})^{\mathtt{R}_{1}:=\mathtt{R}_{1}\cup\psi_{1}})\ldots)^{\mathtt{R}_{n}:=\mathtt{R}_{n}\cup\psi_{n}},$

which finishes our proof. ∎

######  Theorem 38.

Let $\mathcal{R}=\mathcal{R}_{1}\triangleright\mathcal{R}_{2}$. If
$\mathcal{R}_{1}$ is $\mathbf{fps}$ and $\mathcal{R}_{2}$ is $\mathbf{fus}$,
then the query entailment problem $(\mathcal{D},\mathcal{R})\models q$ for
databases $\mathcal{D}$, and CQs $q$ is decidable.

###### Proof.

Let us suppose that
$\mathcal{R}=\mathcal{R}_{1}\triangleright\mathcal{R}_{2}$, $\mathcal{R}_{1}$
is $\mathbf{fps}$, and $\mathcal{R}_{2}$ is $\mathbf{fus}$. Moreover, let
$\mathcal{D}$ be an arbitrary database. Since
$\mathcal{R}=\mathcal{R}_{1}\triangleright\mathcal{R}_{2}$, we have
$\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R})=\mathbf{Ch}_{\infty}(\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{1}),\mathcal{R}_{2})$.
As $\mathcal{R}_{2}$ is $\mathbf{fus}$, we know that for any tuple
$\boldsymbol{\mathtt{a}}$ of constants from $\mathcal{D}$,
$\mathbf{Ch}_{\infty}(\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{1}),\mathcal{R}_{2})\models
q(\boldsymbol{\mathtt{a}})$ iff
$\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{1})\models\mathsf{rew}_{\mathcal{R}_{2}}(q(\boldsymbol{\mathtt{a}}))$,
where $\mathsf{rew}_{\mathcal{R}_{2}}(q)$ is a rewriting of $q$. By Theorem 6,
we can decide if
$\mathbf{Ch}_{\infty}(\mathcal{D},\mathcal{R}_{1})\models\mathsf{rew}_{\mathcal{R}_{2}}(q)$
as $\mathsf{rew}_{\mathcal{R}_{2}}(q)$ is a UCQ, which is a type of HUSOMSOQ.
Hence, the query entailment problem $(\mathcal{D},\mathcal{R})\models q$ is
decidable. ∎


&= \Pr[\vec x_{\pi^{\vec v}(i)} = \vec v \wedge i \in N^{\vec v}] \cdot p+ \delta\\
&= \frac{1}{q^{2d}} \cdot a(d) \cdot \frac{1}{2} \cdot p + \delta.
\end{aligned}
\end{equation}

Next, we consider joint probabilities of two distinct elements $\vec v^i, \vec u^j \in E^d$.

\begin{equation}
\begin{aligned}
\Pr[\vec v^i, \vec u^j \in A] &= \Pr[\vec v^i, \vec u^j  \in A \mid A \sim \D_1] \cdot \Pr[A \sim \D_1] + \Pr[\vec v^i, \vec u^j  \in A \mid A \sim \D_2] \cdot \Pr[A \sim \D_2]\\
&= \Pr[\vec v^i, \vec u^j  \in A \mid A \sim \D_1] \cdot p + \delta\\
&= \Pr\left[\set{\vec x_{\pi^{\vec v}(i)} = \vec v \wedge i \in N^{\vec v}} \bigwedge \set{\vec x_{\pi^{\vec u}(j)} = \vec u \wedge j \in N^{\vec u}}\right] \cdot p+ \delta\\
&= \Pr\left[\vec x_{\pi^{\vec v}(i)} = \vec v \wedge \vec x_{\pi^{\vec u}(j)} = \vec u\right] \cdot \Pr[i \in N^{\vec v} \wedge j \in N^{\vec u}] \cdot p+ \delta\\
\end{aligned}
\end{equation}

When $\vec v \neq \vec u$, we further compute

\begin{equation*}
\begin{aligned}
\Pr[\vec v^i,\vec u^j \in A]
&= \Pr\left[\vec x_{\pi^{\vec v}(i)} = \vec v \wedge \vec x_{\pi^{\vec u}(j)} = \vec u\right] \cdot \Pr[i \in N^{\vec v} \wedge j \in N^{\vec u}] \cdot p+ \delta\\
&= \Pr\left[\vec x_{\pi^{\vec v}(i)} = \vec v \wedge \vec x_{\pi^{\vec u}(j)} = \vec u \mid \pi^{\vec v}(i) \neq \pi^{\vec u}(j)\right] \cdot \Pr[\pi^{\vec v}(i) \neq \pi^{\vec u}(j)] \cdot \frac{a^2(d)}{4} \cdot p+ \delta\\
&= \frac{1}{q^{4d}} \cdot \frac{d-1}{d} \cdot \frac{p \cdot a^2(d)}{4} + \delta\\
&= \frac{p \cdot a(d)}{4 \cdot q^{4d}}\cdot \frac{d-2}{d-1} + \delta.
\end{aligned}
\end{equation*}

If $\vec v= \vec u$ but $i \neq j$, we compute the rest as

\begin{equation}
\begin{aligned}
\Pr[\vec v^i, \vec v^j \in A]
&= \Pr\left[\vec x_{\pi^{\vec v}(i)} = \vec v \wedge \vec x_{\pi^{\vec u}(j)} = \vec u\right] \cdot \Pr[i \in N^{\vec v} \wedge j \in N^{\vec u}] \cdot p+ \delta\\
&= \frac{1}{q^{4d}} \cdot a(d) \cdot \frac{d/2-1}{2(d-1)} \cdot p + \delta\\
&= \frac{p \cdot a(d)}{4 \cdot q^{4d}} \cdot \frac{d-2}{d-1} + \delta.
\end{aligned}
\end{equation}

Notice that regardless of whether $\vec v = \vec u$ or not, for any distinct elements $\vec v^i$ and $\vec u^j$, their marginal probabilities are always equal to the same quantity of $\frac{p \cdot a(d)}{4 \cdot q^{4d}} \cdot \frac{d-2}{d-1} + \delta$.

In order to ensure the second condition we consider the roots of the following equation:

\begin{align*}
\Pr[\vec v^i \in A] \cdot \Pr[\vec u^j \in A] = \Pr[\vec v^i, \vec u^j \in A]
\iff \left(\frac{p \cdot a(d)}{2 \cdot q^{2d}} + \delta\right)^2 = \frac{p \cdot a(d)}{4 \cdot q^{4d}} \cdot \frac{d-2}{d-1} + \delta
\end{align*}

We rewrite the equation as

\[
\delta^2 - \delta \cdot \left(1-\frac{p \cdot a(d)}{q^{2d}}\right) + \frac{p \cdot a(d)}{4 \cdot q^{4d}}\cdot \left(p\cdot a(d) - \frac{d-2}{d-1}\right) = 0.
\]

For the sake of exposition, we let $g_q(d) = \left(1 - \frac{p\cdot a(d)}{q^{2d}} \right)$ and $h_q(d) = \frac{p \cdot a(d)}{4 \cdot q^{4d}}\cdot \left(p\cdot a(d) - \frac{d-2}{d-1}\right)$. First we verify that both $g_q(d)$ and $h_q(d)$ are positive. Trivially, $g_q(d) >0$ as $\frac{p\cdot a(d)}{q^{2d}} <1$ for $d,q \geq 1$. On the other hand for $q \geq 2$ and $d\geq 5$,

\begin{equation}
p\cdot a(d) - \frac{d-2}{d-1} = \frac{d-2}{d-1} \left( p\cdot \frac{d}{d-1} - 1 \right) \geq 0,
\end{equation}

which implies that $h_q(d)\geq 0$. Now, solving quadratic equation in $\delta$, we get,

\begin{align*}
\delta &= \frac{g_q(d)-\sqrt{g^2_q(d)-4h_q(d)}}{2}
= \frac{4h_q(d)}{2\cdot (g_q(d)+ \sqrt{g^2_q(d)-4h_q(d)})}\leq \frac{h_q(d)}{g_q(d)} = O\left( \frac{1}{q^{4d}}\right)
\end{align*}

This implies that $p + \delta = 1 - \frac{1}{q^{2d}} + O\left( \frac{1}{q^{4d}}\right) \leq 1$.

§ MISSING PROOFS FROM SECTION <REF>

This section is devoted to prove Lemma <ref>. We use the same definition of $a(\tau)=\frac{\tau-2}{(\tau-1)^2}$ for simplicity of the notation. We first observe that the Dist I itself is almost pairwise independent. To see that, we compute the following probabilities.

§.§ Probability Calculations for Dist I

For any $\vec v, \vec u \in \Ftdd$ ($\vec u$ and $\vec v$ can be identical), $i,j \in [\tau]$, $\ell, m \in [\kappa]$

\begin{align*}
&1. \quad   \Pr[w(\vec v^i) = 2^\ell \mid w \sim \D_1] = \frac{a(\tau)}{2} \cdot \frac{d}{2^\ell} \cdot \frac{1}{2^{2d}}\\
&2.  \quad   \Pr[w(\vec v^i) = 2^\ell \land w(\vec u^j) = 2^\ell  \mid w \sim \D_1] = \frac{a^2(\tau)}{4} \cdot \frac{d}{2^\ell} \cdot  \left(\frac{d}{2^\ell} - 1\right) \cdot \frac{1}{2^{4d}},\\
&3.  \quad   \Pr[w(\vec v^i) = 2^\ell \land w(\vec u^j) =  2^m  \mid w \sim \D_1] = \frac{a^2(\tau)}{4} \cdot\frac{d^2}{2^{\ell + m}} \cdot  \frac{1}{2^{4d}}.
\end{align*}

To prove the above proposition, we, note that in doistribution $\D_1$,  $\vec v^i \in \FF_2^{2d} \times [\tau]$ is assigned a value of $2^{\ell}$ if the following three independent events occur:

* The $i$-th copy of vector $\vec v$ is available, $i \in N^{\vec v}$, we denote this event as $\EE_{\text{A}}(\vec v^i)$,

* The permutation $\pi^{\vec v}$ assigns the $i$-th copy of $\vec v$ to level $\ell$, with $\psi(\pi^{\vec v}(i))=\ell$, we denote this event $\EE_{\text{L}}(\vec v^i, \ell)$,

* The random linear map yields vector $\vec v$ at the intended index $\pi^{\vec v}(i)$, i.e., $\vec v = \vec x_{\pi^{\vec v}(i)}$. we denote this event as $\EE_{\text{M}}(\vec v^i)$.

In other words, $\Pr[w(\vec v^i)=2^\ell]=\Pr[\EE_{\text{A}}(\vec v^i) \cap \EE_{\text{L}}(\vec v^i, \ell) \cap \EE_{\text{M}}(\vec v^i)]$. Note that $\EE_{\text{A}}$ is independent of both $\EE_{\text{L}}$ and $\EE_{\text{M}}$, irrespective of their parameters. We conclude the proof in three steps. Initially, we compute the joint distribution of any two events of type $\EE_{\text{A}}$. Following that, we calculate the joint probabilities of any two events of type $\EE_{\text{L}}$. We then combine these probabilities to complete the proof of Proposition <ref>.
We start by the marginal and joint probabilities of event type $\EE_{\text{A}}$.

For two distinct $\vec v^i$ and $\vec u^j$;

\begin{align*}
\Pr[\EE_{\text{A}}(\vec v^i)] &= \frac{\tau}{2} \cdot a(\tau), \qquad \text{and}\\
\Pr[\EE_{\text{A}}(\vec v^i) \land \EE_{\text{A}}(\vec u^j)] &= \begin{cases}
\left(\Pr[\EE_{\text{A}}(\vec v^i)]\right)^2 = \frac{\tau^2 \cdot a^2(\tau)}{4} &\text{when }\vec v \neq \vec u,\\
\frac{\tau(\tau-2)}{(\tau-1)^2} \cdot \frac 1 2 \cdot \frac{\tau/2-1}{\tau-1} = \frac 1 4 \cdot \frac{\tau (\tau-2)^2}{(\tau-1)^3} &\text{when }\vec v=\vec u\text{ and } i\neq j.
\end{cases}
\end{align*}

The marginal probability holds since with probability $\tau \cdot a(\tau)$, $N^{\vec v}$ is non-empty. In that scenario, $i$ appears in $N^{\vec{v}}$ with a probability of $1/2$.

Moving forward, we consider the marginal probabilities. The first case follows from the fact that the two events are independent as $N^{\vec v}$ and $N^{\vec u}$ are sampled independently. The second event occurs when $\{N^{\vec v} \neq \emptyset\}$ and $\{i, j \in N^{\vec v}\}$. Given that $N^{\vec v}$ is a uniformly random subset of $[\tau]$ with a size of $\tau/2$, both $i,j \in A^{\vec v}$ with a probability of $\frac 1 2 \cdot \frac{\tau/2-1}{\tau-1}$.

Following that, we calculate the marginal and joint probabilities of $\vec v^i$ and $\vec u^j$ being assigned to levels $\ell$ and $m$, respectively.

For any two distinct vectors $\vec v^i, \vec u^j$ and levels $\ell, m \in [\kappa]$;

\begin{align*}
\Pr[\EE_{\text{L}}(\vec v^i, \ell)] &= \frac{d}{2^\ell \cdot \tau},\\
\Pr[\EE_{\text{L}}(\vec v^i, \ell) \land \EE_{\text{L}}(\vec u^j, m) \land \pi^{\vec v}(i)\neq\pi^{\vec u}(j)] &= \begin{cases}
\frac {d^2}{2^{\ell+ m} \cdot \tau^2} &\text{ when } \ell \neq m \textbf{ and }\vec u \neq \vec v\\
\frac{d}{2^{\ell + m}} \cdot \frac 1 {\tau(\tau-1)}&\text{ when } \ell \neq m \textbf{ and }\vec u = \vec v \textbf{ and } i\neq j.\\
\frac{d}{2^\ell} \left( \frac{d}{2^\ell} -1 \right) \cdot \frac 1 {\tau^2}&\text{ when } \ell=m \textbf{ and }\vec u \neq \vec v\\
\frac{d}{2^\ell} \left( \frac{d}{2^\ell} -1 \right) \cdot \frac 1 {\tau(\tau-1)}&\text{ when } \ell=m \textbf{ and }\vec u = \vec v \textbf{ and } i\neq j,
\end{cases}
\end{align*}

We start with the marginal probability. Recall that $|\Sigma_\ell|=d/2^\ell$ and so $|\psi^{-1}(\ell)|=d/2^{\ell}$. Since $\pi^{\vec v}(i)$ is a uniformly random permutation, $\Pr[\EE_{\text{L}}(v^i, \ell)] = \Pr[\psi(\pi^{\vec v}(i))=\ell] = \frac{|\Sigma_\ell|}{\tau} = \frac{d}{2^\ell \cdot \tau}$.

Next, we consider the joint probabilities. Firstly, observe that when $\ell \neq m$ and two events $\EE_{\text{L}}(\vec v^i, \ell), \EE_{\text{L}}(\vec u^j, \ell)$ occur, $\psi(\pi^{\vec v}(i)) \neq \psi(\pi^{\vec u}(j))$ and therefore $\pi^{\vec v}(i) \neq \pi^{\vec u}(j)$. As $\EE_{\text{L}}(\vec v^i, \ell)$ and  $\EE_{\text{L}}(\vec u^j, \ell)$ are independent for distinct $\vec v$ and $\vec u$, the first equation is valid. The second holds since one index ($i$) out of $\tau$ should point to level $\ell$ and another ($j$) out of $\tau-1$ should indicate level $m$ in a uniformly random permutation $\pi^\vec v$.

When $\ell=m$, $\pi^{\vec v}(i)$ and $\pi^{\vec u}(j)$ have to be assigned two indices out of $\frac{d}{2^\ell}$ where there are $\frac{d}{2^\ell} \cdot \left(\frac{d}{2^\ell}-1\right)$ alternatives. If $\vec v \neq \vec u$, two indices will be assigned to two distinct indices of $\Sigma_\ell$ with a probability of $\frac{1}{\tau^2}$.
If $\vec u=\vec v$ then this probability will be $\frac{1}{\tau \cdot (\tau-1)}$, as each $\vec v^i$ and $\vec u^j$ are two distinct copies of $\vec v=\vec u$.

Now, we compute the marginal probability of each item in the matroid assigned to a particular probability.

\begin{align*}
\Pr[w(\vec v^j) = 2^\ell] &= \Pr[\EE_{\text{A}}(\vec v^i) \land \EE_{\text{L}}(\vec v^i, \ell) \land \EE_{\text{M}}(\vec v^i)]\\
&= \Pr[\EE_{\text{A}}(\vec v^i)]\cdot \Pr[\EE_{\text{L}}(\vec v^i, \ell] \cdot \Pr[\EE_{\text{M}}(\vec v^i)]\\
&=  \frac 1 2 \cdot \frac{\tau(\tau-2)}{(\tau-1)^2} \cdot \frac{d}{2^\ell \cdot \tau} \cdot \frac{1}{2^{2d}} && (\text{Claim~\ref{claim:event-available} and Claim~\ref{claim:event-level}})\\
&= \frac{a(\tau)}{2} \cdot \frac{d}{2^\ell} \cdot \frac{1}{2^{2d}}.
\end{align*}

Next, we compute the joint probability of two distinct element being assigned to value $2^\ell$.

\begin{align*}
&\Pr[w(\vec v^i) = 2^\ell \land w(\vec u^j) = 2^\ell]\\
&= \Pr[\EE_{\text{A}}(\vec v^i) \land \EE_{\text{A}}(\vec u^j) \land \EE_{\text{L}}(\vec v^i, \ell) \land \EE_{\text{L}}(\vec u^j, \ell) \land \EE_{\text{M}}(\vec v^i) \land \EE_{\text{M}}(\vec u^j) \land \pi^{\vec v}(i)\neq\pi^{\vec u}(j)]\\
&= \Pr[\EE_{\text{A}}(\vec v^i) \land \EE_{\text{A}}(\vec u^j)] \cdot \Pr[\EE_{\text{L}}(\vec v^i, \ell) \land \EE_{\text{L}}(\vec u^j, \ell)\land \pi^{\vec v}(i)\neq\pi^{\vec u}(j)] \cdot \Pr[\EE_{\text{M}}(\vec v^i) \land \EE_{\text{M}}(\vec u^j)]
\end{align*}

The second inequality holds because events $\{\EE_{\text{A}}(\vec v^i) \land \EE_{\text{A}}(\vec u^j)\} , \{\EE_{\text{L}}(\vec v^i, \ell) \land \EE_{\text{L}}(\vec u^j, \ell) \land \pi^{\vec v}(i)\neq\pi^{\vec u}(j)\} , \{\EE_{\text{M}}(\vec v^i) \land \EE_{\text{M}}(\vec u^j)\}$ are mutually independent. Now, we compute the above expression for two different cases:

Case I ($\vec v = \vec u$):In this case, we can express:

\begin{align*}
&\Pr[w(\vec v^i) = 2^\ell \land w(\vec v^j) = 2^\ell]\\
& =  \Pr[\EE_{\text{A}}(\vec v^i) \land \EE_{\text{A}}(\vec v^j)] \cdot \Pr[\EE_{\text{L}}(\vec v^i, \ell) \land \EE_{\text{L}}(\vec v^j, \ell) \land \pi^{\vec v}(i)\neq\pi^{\vec u}(j)] \cdot \Pr[\EE_{\text{M}}(\vec v^i) \land \EE_{\text{M}}(\vec v^j)]\\
&= \frac 1 4 \cdot \frac{\tau(\tau-2)^2}{(\tau-1)^3} \cdot \frac{d}{2^\ell} \left( \frac{d}{2^\ell} -1 \right) \cdot \frac 1 {\tau(\tau-1)}\cdot \frac{1}{2^{4d}}\\
&=\frac{a^2(\tau)}{4} \cdot \frac{d}{2^\ell} \cdot  \left(\frac{d}{2^\ell} - 1\right) \cdot \frac{1}{2^{4d}}.
\end{align*}

Case II ($\vec v \neq \vec u$):In this case, we can express:

\begin{align*}
&\Pr[w(\vec v^i) = 2^\ell \land w(\vec u^j) = 2^\ell ]\\
& =  \Pr[\EE_{\text{A}}(\vec v^i) \land \EE_{\text{A}}(\vec u^j)] \cdot \Pr[\EE_{\text{L}}(\vec v^i, \ell) \land \EE_{\text{L}}(\vec u^j, \ell)) \land \pi^{\vec v}(i)\neq\pi^{\vec u}(j)] \cdot \Pr[\EE_{\text{M}}(\vec v^i) \land \EE_{\text{M}}(\vec u^j]\\
&=  \frac 1 4 \cdot \left( \frac{\tau(\tau-2)}{(\tau-1)^2}\right)^2 \cdot  \frac{d}{2^\ell} \left( \frac{d}{2^\ell} -1 \right) \cdot \frac 1 {\tau^2} \cdot \frac{1}{2^{4d}}\\
&=\frac{a^2(\tau)}{4} \cdot \frac{d}{2^\ell} \cdot  \left(\frac{d}{2^\ell} - 1\right) \cdot \frac{1}{2^{4d}}.
\end{align*}

We finally prove the last equality similar to the previous ones. For any two distinct vectors $\vec v^i , \vec u^j \in \Ftdd \times [\tau]$ and levels $\ell, m \in [\kappa]$;

\begin{align*}
&\Pr[w(\vec v^i) = 2^\ell \land w(\vec u^j) = 2^m ]\\
&= \Pr[\EE_{\text{A}}(\vec v^i) \land \EE_{\text{A}}(\vec u^j) \land \EE_{\text{L}}(\vec v^i, \ell) \land \EE_{\text{L}}(\vec u^j, m) \land \EE_{\text{M}}(\vec v^i) \land \EE_{\text{M}}(\vec u^j) \land \pi^{\vec v}(i)\neq\pi^{\vec u}(j)]\\
&=  \Pr[\EE_{\text{A}}(\vec v^i) \land \EE_{\text{A}}(\vec u^j)] \cdot \Pr[\EE_{\text{L}}(\vec v^i, \ell) \land \EE_{\text{L}}(\vec u^j, m) \land \pi^{\vec v}(i)\neq\pi^{\vec u}(j)] \cdot \Pr[\EE_{\text{M}}(\vec v^i) \land \EE_{\text{M}}(\vec u^j)]\\
&=  \frac{a^2(\tau)}{4} \cdot\frac{d^2}{2^{\ell + m}} \cdot  \frac{1}{2^{4d}}.
\end{align*}

We also emphasize that the last inequality holds for the cases when $\vec v \neq \vec u$, or $\vec v = \vec u$ and $i\neq j$.

Therefore, when Procedure <ref> primarily draws weights from $\D_1$, the outcome is “roughly" pairwise independent. The process involves other distributions with minor probability to guarantee that the final distribution is strictly pairwise independent.

As a result of the previous claim we can notice that $\D_1$ is very close to being pairwise independent. To see that observe:

\begin{align*}
& 1. \quad \Pr[w(\vec v^i) = 2^\ell \land w(\vec u^j) =  2^m  \mid  w\sim \D_1] = \Pr[w(\vec v^i) = 2^\ell \mid  w\sim \D_1] \cdot \Pr[w(\vec u^j) = 2^m \mid  w\sim \D_1]\\
& 2. \quad \big |\Pr[w(\vec v^i) = 2^\ell \land w(\vec u^j) = 2^\ell  \mid  w\sim \D_1]- \Pr[w(\vec v^i) = 2^\ell \mid  w\sim \D_1] \cdot \Pr[w(\vec u^j) = 2^\ell \mid  w\sim \D_1]\big | = \Theta\left( \frac 1 {2^{4d}} \right).
\end{align*}

§.§ Determining Parameters for Dist I and Completing Proof of Lemma <ref>

We now determine the $q$ that makes Procedure <ref> a valid pairwise independent distribution.
We define $q$ as the non-negative root of the equation

\begin{equation} \label{eq:q}
\frac{p}{4} \cdot \frac{d^2 \cdot a^2(\tau)}{2^{4d}} + q = \left(\frac{p}{2} \cdot \frac{d \cdot a(\tau)}{2^{2d}}+\frac{p}{4} \cdot \frac{d \cdot a^2(\tau)}{2^{4d}} + q\right)^2
\end{equation}

and show that Procedure <ref> is a valid distribution.

Let $q$ be the non-negative root of Equation <ref>, then $q = O\left( \frac d {2^{3d}} \right)$.

For simplicity of notation, define $z = \frac{d \cdot a(\tau)}{2 \cdot 2^{2d}}$ and rewrite the Equation <ref> as

\[
p \cdot z^2 + q = \left(p \cdot z + \frac{p}{d} \cdot z^2 + q\right)^2
\]

We expand the quadratic equation and obtain:

\[
q^2 - \left(1-p\cdot z + \frac{p}{d} \cdot z^2\right) \cdot q - \left(p \cdot z^2 - p^2\cdot z^2 + \frac{2\cdot p^2\cdot z^3}{d} + \frac{p^2 z^4}{d^2}\right) = 0
\]

$$b(p,z):= \left(1-p\cdot z + \frac{p}{d} \cdot z^2\right) \qquad\text{ and }\qquad c(p,z):=\left(p \cdot z^2 - p^2\cdot z^2 + \frac{2\cdot p^2\cdot z^3}{d} + \frac{p^2 z^4}{d^2}\right)$$

and rewrite the equation as

$$q^2 - b(p,z) \cdot q - c(p,z)=0.$$

Notice that when $d>10$, we have $0 < c(p,z) \leq O(z^2)$ and $\frac{1}{2} \leq b(p,z) \leq 1$. We solve the quadratic equation and obtain.

\begin{align*}
q &= \frac{b(p,z) - \sqrt{b^2(p,z)-4\cdot c(p,z)}}{2} = \frac{4 \cdot c(p,z)}{2 \cdot (b(p,z + \sqrt{b^2(p,z) - 4\cdot c(p,z)}))}\\
&\leq 4\cdot c(p,z)= O(z^2) = O\left(\frac{d^2}{2^{4d}}\right)\qedhere
\end{align*}

Next, we show that the distribution described in Procedure <ref> is a valid distribution, i.e. $p + \sum_{\ell=1}^\kappa p_\ell + q $, eqvivelently,  $1 -p + \sum_{\ell=1}^\kappa p_\ell + q \geq 0$.

$p + \sum_{\ell=1}^\kappa p_\ell + q \leq 1$.

We verify that $q + \sum_{\ell=1}^\kappa p_\ell \leq \frac{d}{2^{d}} \leq 1-p$ and so distribution is valid. We observe that

\begin{align*}
\sum_{\ell \in [\kappa] }p_\ell + q
&\leq \sum_{\ell \in [\kappa]} \frac{p}{4} \cdot \frac{a^2(\tau) \cdot d}{2^{4d + \ell}} + O\left(\frac{d^2}{2^{4d}}\right)\\
&\leq \frac{p}{4}\cdot\frac{a^2(\tau) \cdot d}{2^{4d + \ell}} \cdot\sum_{\ell \in [\kappa]} \frac{1}{2^\ell} + O\left(\frac{d^2}{2^{4d}}\right)\\
&\leq O\left(\frac{d}{2^{4d}}\right) \cdot \sum_{\ell=1}^{\infty} \frac{1}{2^\ell} + O\left(\frac{d^2}{2^{4d}}\right)\\
&\leq O\left(\frac{d^2}{2^{4d}}\right) = o\left(\frac{d}{2^d}\right).
\end{align*}

Finally, we show that the carefully selected value of $q$ in Equation <ref> yields a pairwise independent value distribution in Procedure <ref>.

Given $p_\ell$ and $q$, let $w$ be the value assignment distributed according to Procedure <ref>. For any two distinct vectors $\vec v^i, \vec u^j \in E^\tau$, random variables $w(\vec v^i)$ and $w(\vec u^j)$ are independent.

We first determine the marginal probability of an arbitrary vector $\vec v^i$ possessing value of $2^\ell$ for each $\ell \in [\kappa]$ as follows

\begin{align*}
\Pr[w(\vec v^i) = 2^\ell]
&= p \cdot \Pr[w(\vec v^i) = 2^{\ell}\mid w\sim \D_1] + p_\ell \cdot \Pr[w(\vec v^i) = 2^{\ell}\mid w\sim \D_2] + q \cdot \Pr[w(\vec v^i) = 2^{\ell}\mid w\sim \D_3]\\
&= \frac{p}{2} \cdot \frac{d \cdot a(\tau)}{2^{2d+\ell}} +
\frac{p}{4} \cdot \frac{a^2(\tau) \cdot d}{2^{4d + \ell}} + \frac{q}{2^\ell}.
\end{align*}

Next, we proceed to calculate the joint value distribution of unique vectors $\vec v^i, \vec u^j \in E^\tau$. Specifically, we initiate by determining their joint probability of possessing values $2^\ell$ and $2^m$, respectively, for different levels of $\ell, m \in [\kappa]$.

\begin{align*}
&\Pr[w(\vec v^i) = 2^\ell\land w(\vec u^j) = 2^{m}]\\
&= p \cdot \Pr[w(\vec v^i) = 2^{\ell} \land w(\vec u^j) = 2^{m}\mid w\sim \D_1] + q \cdot \Pr[w(\vec v^i) = 2^{\ell} \land w(\vec u^j) = 2^{m}\mid w\sim \D_3]\\
&= \frac{p}{4} \cdot \frac{d^2 \cdot a^2(\tau)}{2^{4d + \ell + m}} + \frac{q}{2^{\ell + m}}
\end{align*}

Then, we consider the scenario when both have weight $2^\ell$ simultaneously, for any $\ell \in [\kappa]$ as follows:

\begin{align*}
&\Pr[w(\vec v^i) = 2^\ell\land w(\vec u^j) = 2^{\ell}]\\
&= p \cdot \Pr[w(\vec v^i) = 2^{\ell} \land w(\vec u^j) = 2^{\ell}\mid w\sim \D_1] + p_\ell + q \cdot \Pr[w(\vec v^i) = 2^{\ell} \land w(\vec u^j) = 2^{m}\mid w\sim \D_3]\\
&= p \cdot \frac{a^2(\tau)}{4} \cdot \frac{d}{2^\ell} \cdot  \left(\frac{d}{2^\ell} - 1\right) \cdot \frac{1}{2^{4d}} + \frac{p}{4} \cdot \frac{a^2(\tau) \cdot d}{2^{4d + \ell}} + \frac{q}{2^{2\ell}}\\
&= \frac{p}{4} \cdot \frac{d^2 \cdot a^2(\tau)}{2^{4d+2\ell}} + \frac{q}{2^{2\ell}}.
\end{align*}

Based on the observations about joint and marginal probabilities, we deduce that the weights generated by Procedure <ref> are pairwise independent if

\begin{align*}
&\Pr[w(\vec v^i) = 2^\ell\land w(\vec u^j) = 2^{\ell}] = \Pr[w(\vec v^i) = 2^\ell]\cdot \Pr[ w(\vec u^j) = 2^{\ell}]\\
\iff &
\frac{p}{4} \cdot \frac{d^2 \cdot a^2(\tau)}{2^{4d+2\ell}} + \frac{q}{2^{2\ell}} = \left(\frac{p}{2} \cdot \frac{d \cdot a(\tau)}{2^{2d+\ell}} +
\frac{p}{4} \cdot \frac{d \cdot a^2(\tau)}{2^{4d + \ell}} + \frac{q}{2^\ell}\right)^2\\
\iff &\frac{p}{4} \cdot \frac{d^2 \cdot a^2(\tau)}{2^{4d}} + q = \left(\frac{p}{2} \cdot \frac{d \cdot a(\tau)}{2^{2d}}+\frac{p}{4} \cdot \frac{d \cdot a^2(\tau)}{2^{4d}} + q\right)^2
\end{align*}

\begin{align*}
&\Pr[w(\vec v^i) = 2^\ell\land w(\vec u^j) = 2^{m}] = \Pr[w(\vec v^i) = 2^\ell]\cdot \Pr[ w(\vec u^j) = 2^{m}]\\
\iff &\frac{p}{4} \cdot \frac{d^2 \cdot a^2(\tau)}{2^{4d + \ell + m}} + \frac{q}{2^{\ell + m}} =
\prod_{r \in \set{\ell, m}} \left( \frac{p}{2} \cdot \frac{d \cdot a(\tau)}{2^{2d+r}} + \frac{p}{4} \cdot \frac{d \cdot a^2(\tau)}{2^{4d + r}} + \frac{q}{2^r} \right)\\
\iff &\frac{p}{4} \cdot \frac{d^2 \cdot a^2(\tau)}{2^{4d+\ell+m}} + q = \left(\frac{p}{2} \cdot \frac{d \cdot a(\tau)}{2^{2d}}+\frac{p}{4} \cdot \frac{d \cdot a^2(\tau)}{2^{4d}} + q\right)^2
\end{align*}

So, when $q$ satisfies Equation <ref>, for any $\ell\neq m\in [\kappa]$ we ensure that

\begin{align*}
&\Pr[w(\vec v^i) = 2^\ell\land w(\vec u^j) = 2^{\ell}] = \Pr[w(\vec v^i) = 2^\ell]\cdot \Pr[ w(\vec u^j) = 2^{\ell}] \textbf{ and }\\
&\Pr[w(\vec v^i) = 2^\ell\land w(\vec u^j) = 2^{m}] = \Pr[w(\vec v^i) = 2^\ell]\cdot \Pr[ w(\vec u^j) = 2^{m}].
\end{align*}

Due to symmetry, it follows that, $\Pr[w(\vec v^i) = 2^\ell\land w(\vec u^j) = 0] = \Pr[w(\vec v^i) = 2^\ell]\cdot \Pr[ w(\vec u^j) =0]$ and $\Pr[w(\vec v^i) = 0\land w(\vec u^j) = 0] = \Pr[w(\vec v^i) = 0]\cdot \Pr[ w(\vec u^j) =0]$. This concludes the proof.