\section{Introduction}
\label{sec:intro}

The study of correlation functions of quantum-integrable systems is intrinsically related
to partition functions of vertex models with special boundary conditions. In particular, the
case of domain-wall boundaries is of fundamental importance and this fact was first noticed for the
one-dimensional Heisenberg chain with periodic boundary conditions and the associated six-vertex model
\cite{Korepin_1982}. Among the results of \cite{Korepin_1982} there is a recurrence relation determining the partition function
of the six-vertex model with domain-wall boundary conditions, which was later on solved by Izergin in terms of a
determinant \cite{Izergin_1987}.
Subsequently, a determinant representation for scalar products of Bethe vectors under certain specializations of
the parameters (so called on-shell scalar products) was obtained by Slavnov \cite{Slavnov_1989}.
Those results represented the first steps towards the computation of exact correlation functions of quantum-integrable systems,
 but it is worth remarking that the problem of computing norms of Bethe wave functions was first
considered by Gaudin in the case of the non-linear Schr\"odinger model \cite{Gaudin_book}.
Gaudin also formulated the hypothesis that such norms would be given by certain Jacobian determinants.
This hypothesis was subsequently proved by Korepin \cite{Korepin_book} even for more general models.

Scalar products of Bethe vectors are the building blocks of correlation functions, and having them expressed as
determinants for the Heisenberg chain paved the way for the use of well-established techniques.
For instance, the aforementioned determinant formulae in the thermodynamic limit become
determinants of integral operators, i.e.~Fredholm determinants, allowing the derivation of differential equations describing
correlation functions \cite{Its_1990}. The asymptotic behavior of correlation functions was then derived from the analysis of
the respective differential equations. Interestingly, the language of differential equations seems to be quite appropriate for
the description of correlation functions. A remarkable example of this is provided by the Knizhnik-Zamolodchikov equation describing
multi-point correlation functions of primary fields in conformal field theories \cite{Knizhnik_1984}.

As far as the one-dimensional Bose gas is concerned, the results of \cite{Its_1990} are largely due to the existence of particular determinant
representations for correlation functions. However, the recent works \cite{Belliard1, Belliard2, Belliard3, Belliard4} have raised
doubts on the existence of such determinant representations for models based on higher-rank symmetry algebras.
Nevertheless, it is still important to remark here that several advances in the computation of correlation functions have been obtained
through the algebraic Bethe ansatz in \cite{Kitanine_1999, Kitanine_2000, Kitanine_2002, Kitanine_2005, Terras_2013a, Terras_2013b}
and through Sklyanin's separation of variables in \cite{Niccoli_2013a, Niccoli_2013b}.

Integrable spin chains can also be addressed directly in the thermodynamic limit through the vertex-operator approach
due to the quantum affine symmetry exhibited in that limit \cite{Jimbo_1993, Kedem_1995a}.
Alternatively, one can also consider the $q$-Onsager approach described in \cite{Baseilhac_2013}.
Within the vertex-operator approach the description of correlation functions is done by
means of the quantized Knizhnik-Zamolodchikov equation \cite{Jimbo_1992, Jimbo_1993a, Jimbo_1996}.
The latter is not a differential equation but rather a functional equation describing the matrix coefficients of a product of
intertwining operators for a given affine Lie algebra \cite{Reshetikhin_1992}. Interestingly, the partition function of the six-vertex
model with domain-wall boundaries, which initiated the study of correlation functions for one-dimensional quantum spin chains, can also
be described by a functional equation resembling certain aspects of the Knizhnik-Zamolodchikov equation \cite{Galleas_proc}.
Moreover, the functional equation for that partition function can further be translated into a partial differential equation, as
was shown in \cite{Galleas_2011, Galleas_proc}.

The derivation of such functional equations is based on an algebraic-functional approach initially proposed
for spectral problems in \cite{Galleas_2008} and extended for correlations in the series of works
\cite{Galleas_2010,Galleas_2011,Galleas_2012, Galleas_2013, Galleas_SCP}. In particular, those equations allow for
the derivation of integral representations for partition functions with domain-wall boundaries \cite{Galleas_2012, Galleas_2013}
and scalar products of Bethe vectors \cite{Galleas_SCP}. A fundamental ingredient within this algebraic-functional
approach is the Yang-Baxter algebra, which is a common algebraic structure underlying quantum-integrable
systems. On the other hand, integrable systems with open boundary conditions are governed by the reflection
algebra \cite{Sklyanin_1988} and in the present paper we show that this algebra can also be exploited along the
lines of \cite{Galleas_proc}.

Correlation functions for the Heisenberg chain with open boundary conditions have been studied
in the literature through a variety of approaches \cite{Kitanine_2007, Kitanine_2008, Kedem_1995b}. In particular,
a partition function with domain-wall boundaries has also been defined in that case \cite{Tsuchiya_1998}.
As a matter of fact, the partition function introduced in \cite{Tsuchiya_1998} considers both domain-wall boundaries and
one reflecting end, and it can also be expressed as a determinant along the lines of \cite{Izergin_1987}.
Moreover, this partition function has also found interesting applications in the computation of physical properties of
the $XXZ$ spin chain at finite temperature. For instance, the surface free energy of the $XXZ$ spin chain has been expressed
in \cite{Goehmann_2005} as the expectation value of a product of projection operators.
This expectation value was then demonstrated in \cite{Kozlowski_2012} to be precisely the partition function
of the six-vertex model with one reflecting end and domain-wall boundaries described in \cite{Tsuchiya_1998}.
Here we shall study this partition function through the algebraic-functional method
developed in \cite{Galleas_2012, Galleas_2013}. This approach will not only allow us to find a new representation
for the model's partition function, but it will also unveil a set of partial differential equations satisfied by the latter.

This paper is organized as follows. In \Secref{sec:CONV} we introduce definitions and conventions which
shall be employed throughout this work. In \Secref{sec:AF} we describe the algebraic-functional approach
in terms of the reflection algebra, and use this method to derive functional equations characterizing
the partition function of the six-vertex model with one reflecting end and domain-wall boundaries. The solution of our equation
is then given in \Secref{sec:AF}. We proceed with the analysis of our functional equation in \Secref{sec:PDE}
where we extract a set of partial differential equations satisfied by the model's partition function.
Concluding remarks are discussed in \Secref{sec:conclusion} while proofs and technical details are left
for the Appendices.

\section{Definitions and conventions}
\label{sec:CONV}

The most well studied cases of integrable lattice systems are those defined on a finite interval with periodic boundary conditions,
although more general types of boundaries can also be considered. Among those systems, a prominent class is formed by one-dimensional
spin chains with open ends and particular terms characterizing the reflection at the boundaries.
Those models can also be solved by means of the Bethe ansatz and the first results
on that direction have been obtained in \cite{Gaudin_1971, Alcaraz_1987}. Boundary terms are normally
not expected to modify the infinite-volume properties of physical systems, although
counter\-examples for that common belief have been reported in the literature \cite{Korepin_Justin_2000}.
Nevertheless, even for the cases where infinite-volume properties remain the same, boundary terms can still change the finite-size
corrections of massless systems defined on a strip of width $L$ \cite{Alcaraz_1987}.
The latter is able to provide fundamental information concerning the underlying conformal field theory as shown in \cite{Cardy_1986}.

The study of lattice systems with open boundary conditions gained a large impulse with the formulation of
the Quantum Inverse Scattering Method (QISM) for that class of models \cite{Sklyanin_1988}. The approach developed in \cite{Sklyanin_1988}
is based on Cherednik's condition for factorised scattering with reflection \cite{Cherednik_1984}, although it can also
be regarded in the context of vertex models of Statistical Mechanics \cite{Baxter_book}. The latter is the perspective
to be adopted here, and in what follows we shall briefly describe the ingredients required for the construction of the six-vertex
model with domain walls and one reflecting end as defined in \cite{Tsuchiya_1998}.

\paragraph{The $\mathcal{U}_q [ \widehat{\alg{sl}}(2) ]$ $\mathcal{R}$-matrix.} Integrable vertex models are
characterized by an $\mathcal{R}$-matrix $\mathcal{R}: \; \mathbb{C} \rightarrow \gen{End}( \mathbb{V} \otimes \mathbb{V} )$
satisfying the Yang-Baxter equation, namely
\<
\label{ybe}
\mathcal{R}_{12}(\lambda_1 - \lambda_2) \mathcal{R}_{13}(\lambda_1) \mathcal{R}_{23}(\lambda_2) =  \mathcal{R}_{23}(\lambda_2) \mathcal{R}_{13}(\lambda_1) \mathcal{R}_{12}(\lambda_1 - \lambda_2) \; .
\>
In Eq. (\ref{ybe}) we are using the standard notation $\mathcal{R}_{ij} \in \gen{End}(\mathbb{V}_i \otimes \mathbb{V}_j)$
and $\lambda_i$ denote arbitrary complex parameters. For the six-vertex model we have $\mathbb{V}_i  \coloneqq  \mathbb{V} \cong \mathbb{C}^2$
and
\<
\label{rmat}
\mathcal{R} (\lambda) = \left( \begin{matrix}
a(\lambda) & 0 & 0 & 0 \\
0 & b(\lambda) & c(\lambda) & 0 \\
0 & c(\lambda) & b(\lambda) & 0 \\
0 & 0 & 0 & a(\lambda) \end{matrix} \right)
\>
where $a(\lambda)=\sinh{(\lambda + \gamma)}$, $b(\lambda)=\sinh{(\lambda)}$ and $c(\lambda)=\sinh{(\gamma)}$ with
anisotropy parameter $\gamma \in \mathbb{C}$.

\paragraph{Monodromy matrices.} Let $\mathbb{V}_{0} \cong \mathbb{C}^2$ and
$\mathbb{V}_{\mathcal{Q}}  \coloneqq   (\mathbb{C}^2)^{\otimes L}$ for lattice length $L \in \mathbb{Z}_{> 0}$. Also let
$\lambda$ and $\mu_j$ ($1 \leq j \leq L$) be arbitrary complex parameters. Then we consider operators
$\tau, \bar{\tau} \colon \mathbb{C} \to \gen{End}( \mathbb{V}_{0} \otimes \mathbb{V}_{\mathcal{Q}})$ defined as
the following ordered products:
\<
\label{mono}
\tau (\lambda) \coloneqq \mathop{\overleftarrow\prod}\limits_{1 \le j \le L } \mathcal{R}_{0 j} (\lambda - \mu_j )  \qquad \mbox{and} \qquad
\bar{\tau} (\lambda) \coloneqq \mathop{\overrightarrow\prod}\limits_{1 \le j \le L } \mathcal{R}_{0 j} (\lambda + \mu_j ) \; .
\>
The operators $\tau$ and $\bar{\tau}$ are usually referred to as \emph{monodromy matrices} while
$\mathbb{V}_{0}$ and $\mathbb{V}_{\mathcal{Q}}$ are called \emph{auxiliary} and \emph{quantum spaces} respectively.
Since $\mathbb{V}_{0} \cong \mathbb{C}^2$, the monodromy matrices (\ref{mono}) can be recasted as
\[
\label{abcd}
\tau (\lambda) = \left( \begin{matrix}
A(\lambda) & B(\lambda) \\
C(\lambda) & D(\lambda) \end{matrix} \right) \qquad \mbox{and} \qquad
\bar{\tau}(\lambda) = \left( \begin{matrix}
\bar{A}(\lambda) & \bar{B}(\lambda) \\
\bar{C}(\lambda) & \bar{D}(\lambda) \end{matrix} \right) \; ,
\]
with entries in $\gen{End}(\mathbb{V}_{\mathcal{Q}})$.

\paragraph{Yang-Baxter algebra.} Let $\mathcal{R}$ be given by (\ref{rmat}) and consider $\gen{U} \in \{ \tau , \bar{\tau} \}$.
Then the following quadratic algebra is fulfilled by $\gen{U}$,
\[
\label{yba}
\mathcal{R}_{12} (\lambda_1 - \lambda_2) \gen{U}_1 (\lambda_1) \gen{U}_2 (\lambda_2) = \gen{U}_2 (\lambda_2) \gen{U}_1 (\lambda_1) \mathcal{R}_{12} (\lambda_1 - \lambda_2) \; ,
\]
due to the Yang-Baxter equation (\ref{ybe}). Here we are employing the notation $\gen{Y}_1 \coloneqq \gen{Y} \otimes \gen{id}_2$ and
$\gen{Y}_2 \coloneqq \gen{id}_1 \otimes \gen{Y}$ for any operator $\gen{Y} \in \mbox{End}(\mathbb{V})$, where the symbol $\gen{id}_j$
stands for the identity operator in $\mbox{End}(\mathbb{V}_j)$. The relation (\ref{yba}) is commonly referred to
as \emph{Yang-Baxter algebra} and it describes commutation relations for the entries of the monodromy matrices (\ref{abcd}).

\paragraph{Reflection equation.} Within the framework of the QISM developed in \cite{Sklyanin_1988}, integrable boundary conditions are
characterized by a matrix $\mathcal{K}$ satisfying the so called reflection equation. This equation, which was first proposed
in \cite{Cherednik_1984} in the context of factorised scattering, reads
\<
\label{REQ}
&& \mathcal{R}_{12} (\lambda_1 - \lambda_2) \mathcal{K}_1 (\lambda_1) \mathcal{R}_{12} (\lambda_1 + \lambda_2) \mathcal{K}_2 (\lambda_2) \nonumber \\
&& = \mathcal{K}_2 (\lambda_2) \mathcal{R}_{12} (\lambda_1 + \lambda_2) \mathcal{K}_1 (\lambda_1) \mathcal{R}_{12} (\lambda_1 - \lambda_2) \; .
\>
Here we shall restrict ourselves to a particular solution of (\ref{REQ}) associated to the $\mathcal{R}$-matrix (\ref{rmat}).
This solution is explicitly given by
\[
\label{kmat}
\mathcal{K}(\lambda) = \left( \begin{matrix}
\kappa_{+}(\lambda) & 0 \\
0 & \kappa_{-}(\lambda)  \end{matrix} \right) \; ,
\]
where $\kappa_{\pm}(\lambda) = \sinh{(h \pm \lambda)}$ and $h \in \mathbb{C}$ is an arbitrary parameter
describing the interaction at one of the boundaries.

\begin{remark} Within the context of one-dimensional integrable spin chains, the $\mathcal{K}$-matrix (\ref{kmat}) describes the
reflection only at one of the ends of an open system. If we would want to describe reflection at the opposite end we would also need to
introduce a matrix $\bar{\mathcal{K}}$ satisfying an independent equation isomorphic to (\ref{REQ}). More details on this construction can
be found in \cite{Sklyanin_1988}.
\end{remark}

\paragraph{Reflection algebra.} Let the operator $\mathcal{T} \colon \mathbb{C} \to \gen{End}( \mathbb{V}_{0} \otimes \mathbb{V}_{\mathcal{Q}})$
be defined as
\[
\label{full_mono}
\mathcal{T}(\lambda) \coloneqq \tau(\lambda) \mathcal{K}(\lambda) \bar{\tau}(\lambda) \; .
\]
Then, following \cite{Sklyanin_1988}, one can show that $\mathcal{T}$ satisfies the following
quadratic algebra,
\<
\label{REA}
&& \mathcal{R}_{12} (\lambda_1 - \lambda_2) \mathcal{T}_1 (\lambda_1) \mathcal{R}_{12} (\lambda_1 + \lambda_2) \mathcal{T}_2 (\lambda_2) \nonumber \\
&& = \mathcal{T}_2 (\lambda_2) \mathcal{R}_{12} (\lambda_1 + \lambda_2) \mathcal{T}_1 (\lambda_1) \mathcal{R}_{12} (\lambda_1 - \lambda_2) \; .
\>
The relation (\ref{REA}) will be referred to as \emph{reflection algebra} and it follows from the reflection equation obeyed by the matrix
$\mathcal{K}$ together with properties satisfied by $\tau$ and $\bar{\tau}$. The operator $\mathcal{T}$ is commonly referred to
as \emph{double-row monodromy matrix} and, similarly to (\ref{abcd}), it can be recasted as
\[
\label{ABCD}
\mathcal{T}(\lambda) = \left( \begin{matrix}
\mathcal{A}(\lambda) & \mathcal{B}(\lambda) \\
\mathcal{C}(\lambda) & \mathcal{D}(\lambda) \end{matrix} \right) \; .
\]
In this way (\ref{REA}) encodes commutation relations for the operators $\mathcal{A}, \mathcal{B}, \mathcal{C} , \mathcal{D} \in \mbox{End}(\mathbb{V}_{\mathcal{Q}})$.

\paragraph{Highest/lowest weight vectors.} The vectors $\ket{0}, \ket{\bar{0}} \in \mathbb{V}_{\mathcal{Q}}$
defined as
\[
\label{zero}
\ket{0} \coloneqq \left( \begin{matrix} 1 \\ 0 \end{matrix} \right)^{\otimes L}
\qquad \mbox{and} \qquad
\ket{\bar{0}} \coloneqq \left( \begin{matrix} 0 \\ 1 \end{matrix} \right)^{\otimes L} \;
\]
are respectively $\alg{sl}(2)$ highest- and lowest-weight vectors. Due to the structure of (\ref{rmat})
we can easily compute the action of the entries of (\ref{ABCD}) on the vectors (\ref{zero}).
This computation can be found in \Appref{sec:ZERO}. It turns out that $\mathcal{A}(\lambda) \ket{0} = \Lambda_{\mathcal{A}} (\lambda) \ket{0}$,
$\tilde{\mathcal{D}}(\lambda) \ket{0} = \Lambda_{\tilde{\mathcal{D}}} (\lambda) \ket{0}$ and
$\bra{\bar{0}} \mathcal{A}(\lambda)  = \bar{\Lambda}_{\mathcal{A}} (\lambda) \bra{\bar{0}}$,
where we have defined the operator $\tilde{\mathcal{D}}(\lambda) \coloneqq \mathcal{D}(\lambda)  - \frac{c(2 \lambda)}{a(2 \lambda)} \mathcal{A}(\lambda)$
for later convenience. The functions $\Lambda_{\mathcal{A}}$, $\Lambda_{\tilde{\mathcal{D}}}$ and $\bar{\Lambda}_{\mathcal{A}}$
explicitly read
\begin{eqnarray}
\label{lambda}
\Lambda_{\mathcal{A}} (\lambda) & \coloneqq & b(h + \lambda) \prod_{j=1}^{L} a(\lambda - \mu_j) a(\lambda + \mu_j)  \nonumber \\
\Lambda_{\tilde{\mathcal{D}}} (\lambda) &\coloneqq & - \frac{b(2 \lambda)}{a(2 \lambda)} a(\lambda - h) \prod_{j=1}^{L} b(\lambda - \mu_j) b(\lambda + \mu_j)  \nonumber \\
\bar{\Lambda}_{\mathcal{A}} (\lambda) &\coloneqq & \frac{c(2 \lambda)}{a(2 \lambda)} b(h - \lambda) \prod_{j=1}^{L} a(\lambda - \mu_j) a(\lambda + \mu_j) \nonumber \\
&&+ \frac{b(2 \lambda)}{a(2 \lambda)} a(\lambda + h) \prod_{j=1}^{L} b(\lambda - \mu_j) b(\lambda + \mu_j) \; .
\end{eqnarray}

\paragraph{Partition function.} Following the work \cite{Tsuchiya_1998}, the partition function of the six-vertex
model with one reflecting end and domain-wall boundaries is given by
\[
\label{PF}
\mathcal{Z}(\lambda_1 , \lambda_2 , \dots , \lambda_L) = \bra{\bar{0}} \mathop{\overrightarrow\prod}\limits_{1 \le j \le L } \mathcal{B}(\lambda_j) \ket{0} \; .
\]
This partition function is a multivariate function depending on $L$ spectral parameters $\lambda_j$, $L$ inhomogeneity parameters
$\mu_j$, the anisotropy parameter $\gamma$ and the boundary parameter $h$.
In \Secref{sec:AF} we shall describe how the reflection algebra (\ref{REA}) can be exploited in order to derive functional equations determining the partition function (\ref{PF}).

\paragraph{Diagrammatic representation.} The lattice system described by the partition function (\ref{PF}) can be more intuitively
depicted in terms of diagrams representing  the action of the Yang-Baxter and reflection algebras elements. For that it is
convenient to write
$\mathcal{R} = \mathcal{R}_{\alpha \beta}^{\alpha' \beta'} \; e_{\alpha \alpha'} \otimes e_{\beta  \beta'}$,
$\mathcal{K} = \mathcal{K}_{\alpha}^{\alpha'} \; e_{\alpha \alpha'}$ and
$\mathcal{T} = \mathcal{T}_{\alpha}^{\alpha'} \; e_{\alpha \alpha'}$, where summation over repeated indices is assumed.
Here $\alpha , \alpha' , \beta , \beta' \in \{ 1 , 2 \}$ label the basis vectors of $\mathbb{V} \cong \mathbb{C}^2$,
while $e_{\alpha \beta}$ is the matrix with entries $(e_{\alpha \beta})_{ij} = \delta_{\alpha  i} \delta_{\beta  j}$.
The diagrammatic representation of $\mathcal{R}$ and $\mathcal{K}$ is given in \Figref{fig:RandK} while $\mathcal{T}$ is depicted in \Figref{fig:mono}.
Using these conventions the partition function (\ref{PF}) is illustrated in \Figref{fig:partition} with external indices assuming the
domain-wall configurations $\alpha_j , \beta_j = 1$ and $\alpha_j' , \beta_j' = 2$ for all $j$.
\begin{figure}
\begin{center}
\begin{tikzpicture}[font=\scriptsize,thick]
	\draw (-1.5,1) node[font=\normalsize]{$\mathcal{R}^{\alpha'\beta'}_{\alpha\beta} \ = $};
	\draw (0,1) node[left]{$\alpha$} -- (2,1) node[right]{$\alpha'$};
	\draw (1,0) node[below]{$\beta$} -- (1,2) node[above]{$\beta'$};

\begin{scope}[xshift=8.5cm, yshift=1cm]
	\draw (-1.2,0) node[font=\normalsize]{$\mathcal{K}^{\alpha'}_{\alpha} \ = $};
	\draw[rounded corners=6pt] (0,0) -- (-35:1.2) node[right]{$\alpha$};
	\draw[rounded corners=6pt] (0,0) -- (35:1.2) node[right]{$\alpha'$};
	\fill[preaction={fill,white},pattern=north east lines, pattern color=gray] (0,-1) rectangle (-.15,1) ; \draw (0,-1) -- (0,1);
\end{scope}
\end{tikzpicture}
\end{center}
\caption{Diagrammatic representation of the $\mathcal{R}$- and $\mathcal{K}$-matrices.}
\label{fig:RandK}
\end{figure}

\begin{figure}
\begin{center}
\begin{tikzpicture}[font=\scriptsize,thick]
	\draw (-1.2,1.25) node[font=\normalsize]{$\mathcal{T}^{\alpha'}_{\alpha} \ = $};
	\draw[rounded corners=6pt] (0,1.25) -- (1,1.25-.35) -- (5.5,1.25-.35) node[right]{$\alpha$};
	\draw[rounded corners=6pt] (0,1.25) -- (1,1.25+.35) -- (5.5,1.25+.35) node[right]{$\alpha'$};
	\draw (1+.5,0) node[below]{$\beta_1$} -- (1+.5,2.5) node[above]{$\beta_1'$};
	\draw (2+.5,0) node[below]{$\beta_2$} -- (2+.5,2.5) node[above]{$\beta_2'$};
	\draw (3+.5,0) node[below,xshift=1pt]{$\cdots$} -- (3+.5,2.5) node[above,xshift=1pt]{$\cdots$};
	\draw (4+.5,0) node[below]{$\beta_L$} -- (4+.5,2.5) node[above]{$\beta_L'$};
	\fill[preaction={fill,white},pattern=north east lines, pattern color=gray] (0,0) rectangle (-.15,2.5) ; \draw (0,0) -- (0,2.5);
\end{tikzpicture}
\end{center}
\caption{The double-row monodromy matrix $\mathcal{T}$ depicted diagrammatically.}
\label{fig:mono}
\end{figure}

\begin{figure}
\begin{center}
\begin{tikzpicture}[font=\scriptsize,thick]
	\draw[rounded corners=6pt] (0,1.25) -- (1,1.25-.35) -- (5.5,1.25-.35) node[right]{$\alpha_L$};
	\draw[rounded corners=6pt] (0,1.25) -- (1,1.25+.35) -- (5.5,1.25+.35) node[right]{$\alpha_L'$};
	\draw[rounded corners=6pt] (0,2.75) -- (1,2.75-.35) -- (5.5,2.75-.35);
	\draw[rounded corners=6pt] (0,2.75) -- (1,2.75+.35) -- (5.5,2.75+.35);
	\draw (5.5,2.75) node[right,yshift=3pt]{$\:\vdots$};
	\draw[rounded corners=6pt] (0,4.25) -- (1,4.25-.35) -- (5.5,4.25-.35) node[right]{$\alpha_2$};
	\draw[rounded corners=6pt] (0,4.25) -- (1,4.25+.35) -- (5.5,4.25+.35) node[right]{$\alpha_2'$};
	\draw[rounded corners=6pt] (0,5.75) -- (1,5.75-.35) -- (5.5,5.75-.35) node[right]{$\alpha_1$};
	\draw[rounded corners=6pt] (0,5.75) -- (1,5.75+.35) -- (5.5,5.75+.35) node[right]{$\alpha_1'$};
	\draw (1+.5,0) node[below]{$\beta_1$} -- (1+.5,7) node[above]{$\beta_1'$};
	\draw (2+.5,0) node[below]{$\beta_2$} -- (2+.5,7) node[above]{$\beta_2'$};
	\draw (3+.5,0) node[below,xshift=1pt]{$\cdots$} -- (3+.5,7) node[above,xshift=1pt]{$\cdots$};
	\draw (4+.5,0) node[below]{$\beta_L$} -- (4+.5,7) node[above]{$\beta_L'$};
	\fill[preaction={fill,white},pattern=north east lines, pattern color=gray] (0,0) rectangle (-.15,7) ; \draw (0,0) -- (0,7);
\end{tikzpicture}
\end{center}
\caption{Representation of the partition function of the six-vertex model with one reflecting end and domain-wall boundaries.
In this work we have $\alpha_j , \beta_j = 1$ and $\alpha_j' , \beta_j' = 2$.}
\label{fig:partition}
\end{figure}

\section{Algebraic-functional approach}
\label{sec:AF}

In the works \cite{Galleas_2008, Galleas_2010, Galleas_2011, Galleas_2012, Galleas_2013, Galleas_SCP, Galleas_proc}
we have described a mechanism yielding functional equations satisfied by quantities of physical interest
as a direct consequence of the Yang-Baxter algebra. This approach has been employed for the determination of
spectra \cite{Galleas_2008, Galleas_2013} and partition functions \cite{Galleas_2012, Galleas_2013}
of integrable vertex models. One issue arising within this method is that the algebraic relations we are considering
might not suffice to determine the desired quantities.
Furthermore, it would be desirable to have the simplest possible equations such that finding its solutions
can be achieved without much effort. Up to the present moment, we have only considered the Yang-Baxter algebra and its dynamical
counterpart as a source of functional relations \cite{Galleas_proc} and here we aim to show that
the reflection algebra (\ref{REA}) can also be exploited along the same lines. For this we need to introduce
the following definitions.

\begin{mydef} \label{pidef}
Let $\mathcal{M}(\lambda) \coloneqq \{ \mathcal{A}, \mathcal{B} , \mathcal{C} , \mathcal{D} \}(\lambda)$
and define $\mathcal{W}_n \coloneqq \mathcal{M}(\lambda_1) \times \mathcal{M}(\lambda_2) \times \dots \times \mathcal{M}(\lambda_n)$
with $n$-tuples $(\chi_1 , \dots , \chi_n)$ understood as $\mathop{\overrightarrow\prod}\limits_{1 \le j \le n } \chi_j$.
Also, let $\mathbb{C}[ \lambda_1^{\pm 1} , \lambda_2^{\pm 1} , \dots , \lambda_n^{\pm 1} ]$ be the ring of
meromorphic functions in the variables $\lambda_1, \dots , \lambda_n$ and define
$\tilde{\mathcal{W}}_n \coloneqq \mathbb{C}[ \lambda_1^{\pm 1} , \dots , \lambda_n^{\pm 1} ] \otimes \gen{span}_{\mathbb{C}} ( \mathcal{W}_n )$.
\end{mydef}

To obtain functional relations from the reflection algebra we also need to introduce an appropriate linear map
\[
\label{pin}
\gen{\pi}_n \colon  \tilde{\mathcal{W}}_n \to \mathbb{C}[ \lambda_1^{\pm 1} , \lambda_2^{\pm 1} , \dots , \lambda_n^{\pm 1} ] \; .
\]
A suitable realization of (\ref{pin}) will be given shortly.

\paragraph{Reflection relation of degree $n$.} The reflection algebra (\ref{REA}) encodes a set of sixteen commutation
relations governing the elements of (\ref{ABCD}). It is clear from (\ref{REA}) that those commutation
rules are quadratic and here they are referred to as reflection relations of degree two. The repeated use
of (\ref{REA}) then yields relations in $\tilde{\mathcal{W}}_n$ which shall be referred to as reflection relations
of degree $n$.

\subsection{Functional equations}
\label{sec:FZ}

In Definition \ref{pidef} we have introduced a map $\gen{\pi}_n$ assigning multivariate complex functions
to the elements of the set $\mathcal{W}_{n}$. Here our goal is to evaluate the partition function (\ref{PF}), and this
can be achieved from the study of suitable functional equations derived through the application of the map (\ref{pin})
on reflection relations of higher degree.
This procedure will require the following ingredients: a suitable realization of the map $\gen{\pi}_n$ and a convenient
reflection-algebra relation. As a matter of fact, different functional relations can be derived for the partition function
$\mathcal{Z}$ by changing these ingredients.

\paragraph{Realization of $\gen{\pi}_n$.} The operatorial formulation of the partition function $\mathcal{Z}$ as
given by (\ref{PF}) suggests that a suitable realization of $\gen{\pi}_n$ is given by the following scalar product:
\[
\label{pir}
\gen{\pi}_n (\mathcal{F}) \coloneqq \bra{\bar{0}} \mathcal{F} \ket{0} \; ,
\]
for $\mathcal{F} \in \tilde{\mathcal{W}}_n$ and vectors $\ket{0}, \ket{\bar{0}} \in \mathbb{V}_{\mathcal{Q}}$ defined in (\ref{zero}).

\paragraph{Reflection-algebra relation.} Next we look for appropriate reflection relations of higher degree from which we can find functional relations
satisfied by the partition function $\mathcal{Z}$. In order to build such higher-degree relations we start
from the following fundamental commutation rules contained in (\ref{REA}):
\<
\label{ADB}
\mathcal{A}(\lambda_1) \mathcal{B}(\lambda_2) &=& \frac{a(\lambda_2 - \lambda_1)}{b(\lambda_2 - \lambda_1)} \frac{b(\lambda_2 + \lambda_1)}{a(\lambda_2 + \lambda_1)} \mathcal{B}(\lambda_2) \mathcal{A}(\lambda_1) - \frac{b(2 \lambda_2)}{a(2 \lambda_2)} \frac{c(\lambda_2 - \lambda_1)}{b(\lambda_2 - \lambda_1)} \mathcal{B}(\lambda_1) \mathcal{A}(\lambda_2) \nonumber \\
&&- \frac{c(\lambda_2 + \lambda_1)}{a(\lambda_2 + \lambda_1)} \mathcal{B}(\lambda_1) \tilde{\mathcal{D}}(\lambda_2) \nonumber \\
\tilde{\mathcal{D}}(\lambda_1) \mathcal{B}(\lambda_2) &=& \frac{a(\lambda_2 + \lambda_1 + \gamma)}{b(\lambda_2 + \lambda_1 + \gamma)} \frac{a(\lambda_1 - \lambda_2)}{b(\lambda_1 - \lambda_2)} \mathcal{B}(\lambda_2) \tilde{\mathcal{D}}(\lambda_1) - \frac{a(2 \lambda_1 + \gamma)}{b(2 \lambda_1 + \gamma)} \frac{c(\lambda_1 - \lambda_2)}{b(\lambda_1 - \lambda_2)} \mathcal{B}(\lambda_1) \tilde{\mathcal{D}}(\lambda_2) \nonumber \\
&&+ \frac{b(2 \lambda_2)}{a(2 \lambda_2)} \frac{a(2 \lambda_1 + \gamma)}{b(2 \lambda_1 + \gamma)} \frac{c(\lambda_2 + \lambda_1)}{a(\lambda_2 + \lambda_1)} \mathcal{B}(\lambda_1) \mathcal{A}(\lambda_2) \nonumber \\
\mathcal{B}(\lambda_1) \mathcal{B}(\lambda_2) &=& \mathcal{B}(\lambda_2) \mathcal{B}(\lambda_1) \; .
\>
Note that the above relation is given in terms of the operator $\tilde{\mathcal{D}}(\lambda) = \mathcal{D}(\lambda)  - \frac{c(2 \lambda)}{a(2 \lambda)} \mathcal{A}(\lambda)$.

Next we describe a suitable functional relation satisfied by (\ref{PF}). Although the partition function $\mathcal{Z}$ is a multivariate function
depending on $L$ spectral parameters $\lambda_i$, in addition to parameters $\mu_i$, $h$ and $\gamma$, here we shall obtain a functional equation
determining $\mathcal{Z}$ where only $\lambda_i$ play the role of variables.

\begin{theorem} \label{theo_fun}
The partition function of the six-vertex model with one reflecting end and domain-wall boundaries obeys the
functional equation
\[
\label{TPA}
M_0 \; \mathcal{Z}(\lambda_1 , \dots , \lambda_L) + \sum_{i=1}^L M_i \; \mathcal{Z}(\lambda_0, \lambda_1 , \dots , \lambda_{i-1} , \lambda_{i+1} , \dots , \lambda_L ) = 0 \; ,
\]
with coefficients $M_0$ and $M_i$ given by
\<
\label{M0MI}
M_0 &\coloneqq & \bar{\Lambda}_{\mathcal{A}} (\lambda_0) - \Lambda_{\mathcal{A}} (\lambda_0) \prod_{j=1}^{L} \frac{a(\lambda_j - \lambda_0)}{b(\lambda_j - \lambda_0)} \frac{b(\lambda_j + \lambda_0)}{a(\lambda_j + \lambda_0)} \nonumber \\
M_i &\coloneqq & \frac{b(2 \lambda_i)}{a(2 \lambda_i)} \frac{c(\lambda_i - \lambda_0)}{b(\lambda_i - \lambda_0)} \Lambda_{\mathcal{A}} (\lambda_i) \prod_{\substack{j=1 \\j \neq i}}^{L} \frac{a(\lambda_j - \lambda_i)}{b(\lambda_j - \lambda_i)} \frac{b(\lambda_j + \lambda_i)}{a(\lambda_j + \lambda_i)} \nonumber \\
&& + \frac{c(\lambda_i + \lambda_0)}{a(\lambda_i + \lambda_0)} \Lambda_{\tilde{\mathcal{D}}} (\lambda_i) \prod_{\substack{j=1 \\j \neq i}}^{L} \frac{a(\lambda_i - \lambda_j)}{b(\lambda_i - \lambda_j)} \frac{a(\lambda_i + \lambda_j + \gamma)}{b(\lambda_i + \lambda_j + \gamma)} \; .
\>
The functions $\Lambda_{\mathcal{A}}$, $\Lambda_{\tilde{\mathcal{D}}}$ and $\bar{\Lambda}_{\mathcal{A}}$ were defined in (\ref{lambda}).
\end{theorem}
\begin{proof}
Consider the following element of $\mathcal{W}_{n+1}$,
\[
\label{ABBi}
\mathcal{A}(\lambda_0) \mathop{\overrightarrow\prod}\limits_{1 \le j \le n } \mathcal{B}(\lambda_j) \; ,
\]
under the light of the reflection algebra (\ref{REA}). The repeated use of (\ref{ADB}) yields the following
reflection relation of order $n+1$,
\<
\label{ABB}
\mathcal{A}(\lambda_0) \mathop{\overrightarrow\prod}\limits_{1 \le j \le n } \mathcal{B}(\lambda_j) &=& \prod_{j=1}^{n} \frac{a(\lambda_j - \lambda_0)}{b(\lambda_j - \lambda_0)} \frac{b(\lambda_j + \lambda_0)}{a(\lambda_j + \lambda_0)} \mathop{\overrightarrow\prod}\limits_{1 \le j \le n } \mathcal{B}(\lambda_j) \mathcal{A}(\lambda_0)  \nonumber \\
&& - \sum_{i=1}^{n} \frac{b(2 \lambda_i)}{a(2 \lambda_i)} \frac{c(\lambda_i - \lambda_0)}{b(\lambda_i - \lambda_0)}  \prod_{\substack{j=1 \\ j \neq i}}^{n} \frac{a(\lambda_j - \lambda_i)}{b(\lambda_j - \lambda_i)} \frac{b(\lambda_j + \lambda_i)}{a(\lambda_j + \lambda_i)} \mathop{\overrightarrow\prod}\limits_{\substack{0 \le j \le n \\ j \neq i}} \mathcal{B}(\lambda_j) \mathcal{A}(\lambda_i) \nonumber \\
&& - \sum_{i=1}^{n} \frac{c(\lambda_i + \lambda_0)}{a(\lambda_i + \lambda_0)} \prod_{\substack{j=1 \\ j \neq i}}^{n} \frac{a(\lambda_i - \lambda_j)}{b(\lambda_i - \lambda_j)} \frac{a(\lambda_i + \lambda_j + \gamma)}{b(\lambda_i + \lambda_j + \gamma)} \mathop{\overrightarrow\prod}\limits_{\substack{0 \le j \le n \\ j \neq i}} \mathcal{B}(\lambda_j) \tilde{\mathcal{D}}(\lambda_i) \; . \nonumber \\
\>
Next we set $n=L$ and apply the map $\gen{\pi}_{L+1}$ given by (\ref{pir}) to (\ref{ABB}).
The left-hand side of (\ref{ABB}) then yields the term $\gen{\pi}_{L+1} (\mathcal{A}(\lambda_0) \mathop{\overrightarrow\prod}\limits_{1 \le j \le L } \mathcal{B}(\lambda_j))$ while the right-hand side
produces terms of the form $\gen{\pi}_{L+1} ( \mathop{\overrightarrow\prod}\limits_{1 \le j \le L } \mathcal{B}(\nu_j) \mathcal{A}(\nu) )$
and $\gen{\pi}_{L+1} ( \mathop{\overrightarrow\prod}\limits_{1 \le j \le L } \mathcal{B}(\nu_j) \tilde{\mathcal{D}}(\nu) )$.
Note that $\gen{\pi}_{L+1}$ reduces to $\gen{\pi}_{L}$ due to the $\alg{sl}(2)$ highest/lowest weight properties
exhibited by the realization (\ref{pir}). More precisely we have:
\<
\label{red}
\gen{\pi}_{L+1} (\mathcal{A}(\lambda_0) \mathop{\overrightarrow\prod}\limits_{1 \le j \le L } \mathcal{B}(\lambda_j)) &=& \bar{\Lambda}_{\mathcal{A}}(\lambda_0) \gen{\pi}_{L} (\mathop{\overrightarrow\prod}\limits_{1 \le j \le L } \mathcal{B}(\lambda_j)) \; , \nonumber  \\
\gen{\pi}_{L+1} ( \mathop{\overrightarrow\prod}\limits_{1 \le j \le L } \mathcal{B}(\nu_j) \mathcal{A}(\nu) ) &=& \Lambda_{\mathcal{A}} (\nu) \gen{\pi}_{L} ( \mathop{\overrightarrow\prod}\limits_{1 \le j \le L } \mathcal{B}(\nu_j) ) \; , \nonumber \\
\gen{\pi}_{L+1} ( \mathop{\overrightarrow\prod}\limits_{1 \le j \le L } \mathcal{B}(\nu_j) \tilde{\mathcal{D}}(\nu) ) &=& \Lambda_{\tilde{\mathcal{D}}} (\nu) \gen{\pi}_{L} ( \mathop{\overrightarrow\prod}\limits_{1 \le j \le L } \mathcal{B}(\nu_j) ) \; .
\>
Now we can identify the partition function $\mathcal{Z} (\lambda_1 , \dots , \lambda_L) = \gen{\pi}_{L} (\mathop{\overrightarrow\prod}\limits_{1 \le j \le L } \mathcal{B}(\lambda_j))$
on the right-hand side of (\ref{red}). Thus the relations (\ref{ABB}) and (\ref{red}) under the above mentioned conditions result in the functional equation (\ref{TPA}).
This proves Theorem \ref{theo_fun}.
\end{proof}

\begin{remark} \label{multi}
The functional equation (\ref{TPA}) is invariant under the permutation of variables $\lambda_i \leftrightarrow \lambda_j$
for $i,j \in \{1,2, \dots , L \}$. This conclusion follows directly from Lemma \ref{symm_lemma} which will be stated below.
However, the permutation $\lambda_0 \leftrightarrow \lambda_j$ yields a different functional equation for $\mathcal{Z}$.
The resulting equation exhibits the same structure as (\ref{TPA}), with modified coefficients though. In this way (\ref{TPA})
actually encodes a set of $L+1$ equations.
\end{remark}

\subsection{The partition function $\mathcal{Z}$}
\label{sec:sol}

This section is devoted to the determination of the partition function (\ref{PF})
as a particular solution of the functional equation (\ref{TPA}). A priori we do not have any
guarantee that (\ref{TPA}) is enough for that but direct inspection reveals that this is indeed
the case for small values of the lattice length $L$.

The general strategy for solving (\ref{TPA}) will follow the same steps described in \cite{Galleas_2013}.
This is anticipated since the structure of (\ref{TPA}) resembles that of the functional equation derived in
\cite{Galleas_2013} for the partition function of the elliptic SOS model with domain-wall boundaries.
However, here we shall need to exploit some further properties of (\ref{TPA}) which were not required in
\cite{Galleas_2013}. In order to clarify our methodology let us first stress some characteristics of our functional equation.
Firstly, Eq. (\ref{TPA}) is an equation for a complex multivariate function $\mathcal{Z}$ formed by a linear combination of terms containing
$\mathcal{Z}(\lambda_1 , \lambda_2 , \dots , \lambda_L)$ with one of the variables $\lambda_i$ replaced by the variable $\lambda_0$.
Thus (\ref{TPA}) runs over the set of variables $\{ \lambda_0 , \lambda_1 , \dots ,\lambda_L \}$.
In addition to that, our equation is homogeneous in the sense that if $\mathcal{Z}$ is a solution then
$\omega \mathcal{Z}$ also solves (\ref{TPA}) for any $\omega \in \mathbb{C}$ independent of the variables $\lambda_i$.
This property anticipates that we shall need to evaluate the partition function (\ref{PF}) for a particular value of its variables
in order to having the desired solution completely fixed. Moreover, due to the linearity of Eq. (\ref{TPA}), we need to address the question
of uniqueness of the solution. The partition function (\ref{PF}) consists of a particular polynomial solution and the uniqueness within such class
of solutions was proved in \cite{Galleas_2012} under very general conditions.

Considering the above discussion the following lemmas will assist us through the determination of the partition function $\mathcal{Z}$.

\begin{lemma}[Polynomial structure] \label{pol_lemma}
The partition function $\mathcal{Z}$ defined in (\ref{PF}) is of the form $\mathcal{Z}(\lambda_1, \dots , \lambda_L) = \bar{\mathcal{Z}}(x_1 , \dots , x_L) \prod_{i=1}^{L} x_i^{-L}$, where
$x_i \coloneqq e^{2 \lambda_i}$ and $\bar{\mathcal{Z}}(x_1 , \dots , x_L)$ is a polynomial of degree $2L$ in each of its variables.
\end{lemma}
\begin{proof}
The proof is obtained by induction and can be found in \Appref{sec:pol}.
\end{proof}

\begin{lemma} \label{symm_lemma}
Analytic solutions of (\ref{TPA}) are symmetric functions. More precisely, they satisfy the
property $\mathcal{Z} (\dots, \lambda_i , \dots , \lambda_j , \dots) = \mathcal{Z} (\dots, \lambda_j , \dots , \lambda_i , \dots)$.
\end{lemma}
\begin{proof}
This property follows from the structure of poles appearing in (\ref{M0MI}). See \Appref{sec:symm} for details.
\end{proof}

\begin{lemma}[Special zeroes] \label{zeroes_lemma}
For $L\geq 2$ the partition function $\mathcal{Z}$ vanishes for the specialization of variables $\lambda_1 = \mu_1 - \gamma$
and $\lambda_2 = \mu_1$. The same holds for the specialization $\lambda_1 = \mu_1 - \gamma$ and $\lambda_2 = -\mu_1 - \gamma$.
\end{lemma}
\begin{proof}
The proof follows from the inspection of (\ref{TPA}) under these specializations of variables, taking into account Remark \ref{multi}.
See \Appref{sec:zeroes} for details.
\end{proof}

\begin{lemma}[Asymptotic behavior] \label{asymp_lemma}
In the limit where all variables $x_i \rightarrow \infty$, the function $\bar{\mathcal{Z}}$ behaves as
\[
\label{asymp_form}
\bar{\mathcal{Z}} \sim \frac{q^{\frac{L(L-1)}{2}}}{2^{L(2L+1)}} (q - q^{-1})^L [L!]_{q^2} \prod_{i=1}^{L} (t y_i^{-\frac{1}{2}} - t^{-1} y_i^{\frac{1}{2}}) x_i^{2 L} \; ,
\]
where $q \coloneqq e^{\gamma}$, $t \coloneqq e^{h}$, $y_i \coloneqq e^{2 \mu_i}$ and $[n!]_{q^2} \coloneqq 1 (1 + q^2) (1 + q^2 + q^4) \dots (1 + q^2 + \dots + q^{2(n-1)})$ is the $q$-factorial function.
\end{lemma}
\begin{proof}
As $x_i \rightarrow \infty$ the generators (\ref{ABCD}) tend to the generators of the $\mathcal{U}_q [\alg{sl}(2)]$ algebra.
The properties of the latter can be employed to demonstrate (\ref{asymp_form}) as is shown in \Appref{sec:asymp}.
\end{proof}

\begin{remark} \label{add1}
Due to Lemma \ref{symm_lemma}, Eq. (\ref{TPA}) can also be written in a more compact form using the notation $\mathcal{Z}(\lambda_1 , \dots , \lambda_L) = \mathcal{Z}( X^{1,L} )$
and $\mathcal{Z}(\lambda_0, \lambda_1 , \dots , \lambda_{i-1} , \lambda_{i+1} , \dots , \lambda_L ) = \mathcal{Z}( X^{0,L}_i )$ where
$X^{i,j}  \coloneqq  \{ \lambda_k \; : \; i \leq k \leq j \}$ and $X^{i,j}_l \coloneqq X^{i,j} \setminus \{ \lambda_l \}$.
\end{remark}

\subsubsection{Multiple integral representation}
\label{sec:solA}

The resolution of (\ref{TPA}) will follow a sequence of systematic steps based on Lemmas \ref{pol_lemma} to \ref{asymp_lemma}.
The general procedure consists in finding suitable specializations of the variables $\lambda_0$ and $\lambda_L$ allowing us to
invoke the above lemmas. The desired solution of (\ref{TPA}) is given by the following theorem.

\begin{theorem} \label{SOLa}
The partition function of the six-vertex model with one reflecting end and domain-wall boundaries (\ref{PF})
can be written as
\<
\label{theorA}
\mathcal{Z} (X^{1,L}) &=& c^L \oint \dots \oint \prod_{i=1}^{L} \frac{\mathrm{d} w_i}{ 2 \pi \mathrm{i}} \frac{\prod_{1 \leq i < j \leq L} a(\mu_i + w_j) b(\mu_i - w_j) b(w_i - w_j)^2}{\prod_{i,j=1}^{L} b(w_i - \lambda_j)} \nonumber \\
&& \qquad \qquad \quad \times \; \prod_{i=1}^{L} \frac{b(2 w_i)}{a(2 w_i)} \frac{b(h - \mu_i)}{b(h + \mu_i)} \Theta_i  \; , \nonumber
\>
where
\<
\label{Theta_theor}
\Theta_i &\coloneqq &  \frac{b(w_i + h)}{a(w_i - \mu_i)} \prod_{j=i}^L a(w_i - \mu_j) a(w_i + \mu_j) \prod_{k=i+1}^L \frac{a(w_k - w_i)}{b(w_k - w_i)} \frac{b(w_k + w_i)}{a(w_k + w_i)}   \nonumber \\
&& - \; \frac{a(w_i - h)}{b(w_i + \mu_i)} \prod_{j=i}^L b(w_i - \mu_j) b(w_i + \mu_j) \prod_{k=i+1}^L \frac{a(w_i - w_k)}{b(w_i - w_k)} \frac{a(w_i + w_k + \gamma)}{b(w_i + w_k + \gamma)} \; . \nonumber \\
\>
\end{theorem}
\begin{proof} The proof of Theorem \ref{SOLa} follows from the resolution of (\ref{TPA})
taking into account certain properties of (\ref{PF}). The procedure consists of three steps.

\textit{Step $1$.} We first set $\lambda_0 = \mu_1 - \gamma$ in Eq. (\ref{TPA}). Under this specialization
the coefficient $M_0$ is reduced to a single product. This specialization also produces terms of the form
$\mathcal{Z} ( \bar{X}^{2,L} )$ where $\bar{X}^{i,j} \coloneqq \{ \mu_1 - \gamma  \} \cup X^{i,j}$.
Now due to Lemmas \ref{pol_lemma} to \ref{zeroes_lemma} we can write
\[
\mathcal{Z} ( \bar{X}^{2,L} ) = \prod_{j=2}^{L} b(\lambda_j - \mu_1) a(\lambda_j + \mu_1) \; \mathcal{V}(X^{2,L}) \; ,
\]
where $\mathcal{V}$ is a polynomial of degree $2(L-1)$ in each variable $x_i$ up to an overall exponential factor.
Thus this particular specialization yields the expression
\[
\label{ZV}
\mathcal{Z} ( X^{1,L} ) = \kappa^{-1} \sum_{i=1}^L \frac{b(2 \lambda_i)}{a(2 \lambda_i)} \prod_{\substack{j=1 \\ j \neq i}}^{L} b(\lambda_j - \mu_1) a(\lambda_j + \mu_1) \; m_i \; \mathcal{V} (X^{1,L}_i) \; ,
\]
with coefficients $\kappa$ and $m_i$ given by
\<
\label{kami}
\kappa &\coloneqq & b(h + \mu_1) b(2 \mu_1 - 2 \gamma) \prod_{j=2}^{L} b(\mu_1 - \mu_j - \gamma) b(\mu_1 + \mu_j - \gamma) \nonumber \\
m_i &\coloneqq &  \frac{b(\lambda_i + h)}{a(\lambda_i - \mu_1)} \prod_{j=1}^L a(\lambda_i - \mu_j) a(\lambda_i + \mu_j) \prod_{\substack{k=1 \\ k \neq i}}^L \frac{a(\lambda_k - \lambda_i)}{b(\lambda_k - \lambda_i)} \frac{b(\lambda_k + \lambda_i)}{a(\lambda_k + \lambda_i)}   \nonumber \\
&& - \; \frac{a(\lambda_i - h)}{b(\lambda_i + \mu_1)} \prod_{j=1}^L b(\lambda_i - \mu_j) b(\lambda_i + \mu_j) \prod_{\substack{k=1 \\ k \neq i}}^L \frac{a(\lambda_i - \lambda_k)}{b(\lambda_i - \lambda_k)} \frac{a(\lambda_i + \lambda_k + \gamma)}{b(\lambda_i + \lambda_k + \gamma)} \; . \nonumber \\
\>

\textit{Step $2$.} We substitute formula (\ref{ZV}) back into the original equation (\ref{TPA}). By doing so
we are left with an equation involving only functions $\mathcal{V}$. Next we set $\lambda_L = \mu_1$ in the resulting
equation which then further simplifies to
\[
\label{TPAr}
\tilde{M}_0 \mathcal{V}(X^{1,L-1}) + \sum_{i=1}^{L-1} \tilde{M}_i \; \mathcal{V}(X^{0,L-1}_i) = 0 \; .
\]
The explicit form of the coefficients $\tilde{M}_0$ and $\tilde{M}_i$ is not enlightening but it is worth remarking
that for $L=2$ we find that (\ref{TPAr}) corresponds to (\ref{TPA}) with $L=1$ and $\mu_1$ replaced by $\mu_2$.
This fact suggests that (\ref{TPAr}) should coincide with (\ref{TPA}) after replacing $L$ by $L-1$ and
$\mu_i$ by $\mu_{i+1}$. Unfortunately this is not the case for general values of $L$ and we actually find that
(\ref{TPAr}) consists of a linear combination of (\ref{TPA}) along the lines of Remark \ref{multi}.
Nevertheless, this still ensures that $\mathcal{V}$ is essentially our partition function
under the maps $L \mapsto L-1$ and $\mu_i \mapsto \mu_{i+1}$ since polynomial solutions are unique.

\textit{Step $3$.} The results of Step $2$ allows us to obtain an explicit representation for our
partition function from the relation (\ref{ZV}) in a recursive manner. In fact, formula (\ref{ZV}) suggests
the following ansatz for $\mathcal{Z}$
\[
\label{int}
\mathcal{Z} (X^{1,L}) = \oint \dots \oint \prod_{i=1}^{L} \frac{\mathrm{d} w_i}{ 2 \pi \mathrm{i}} \frac{H(w_1, \dots , w_L)}{\prod_{i,j=1}^{L} b(w_i - \lambda_j)} \; ,
\]
where $H$ is a function yet to be determined. In particular, here we also assume that the integration contours in (\ref{int})
enclose all the poles at $w_i = \lambda_j$ and that $H$ contains no poles inside those integration contours.
Then we consider the mechanism described in \cite{Galleas_SCP} to find the following relation determining the function $H$,
\<
\label{HH}
&& H(w_1 , \dots , w_L) = \nonumber \\
&& \frac{\bar{H}(w_2 , \dots , w_L)}{b(h + \mu_1)} \frac{b(2 w_1)}{a(2 w_1)} \prod_{j=2}^{L} b(w_1 - w_j)^2 b(\mu_1 - w_j) a(\mu_1 + w_j)  \nonumber \\
&& \times \left[ b(2 \mu_1 - 2 \gamma) \prod_{j=2}^{L} b(\mu_1 - \mu_j - \gamma) b(\mu_1 + \mu_j - \gamma) \right]^{-1} \nonumber \\
&& \times \left\{  \frac{b(w_1 + h)}{a(w_1 - \mu_1)} \prod_{j=1}^L a(w_1 - \mu_j) a(w_1 + \mu_j) \prod_{k=2}^L \frac{a(w_k - w_1)}{b(w_k - w_1)} \frac{b(w_k + w_1)}{a(w_k + w_1)} \right.  \nonumber \\
&& \quad \quad - \left. \frac{a(w_1 - h)}{b(w_1 + \mu_1)} \prod_{j=1}^L b(w_1 - \mu_j) b(w_1 + \mu_j) \prod_{k=2}^L \frac{a(w_1 - w_k)}{b(w_1 - w_k)} \frac{a(w_1 + w_k + \gamma)}{b(w_1 + w_k + \gamma)} \right\} \; . \nonumber \\
\>
The function $\bar{H}$ in (\ref{HH}) corresponds to $H$ under the maps $L \mapsto L-1$, $\mu_i \mapsto \mu_{i+1}$
up to an overall constant factor. In this way the relation (\ref{HH}) can be iterated once we know the
function $H(w_1)$. This function can be directly read from the solution of (\ref{TPA}) for $L=1$ which can be found
in \Appref{sec:L1}. Thus the iteration of (\ref{HH}) yields the following expression for the function $H$,
\<
\label{Hgen}
H(w_1 , \dots , w_L) = c^L \; \prod_{i=1}^{L} \frac{b(2 w_i)}{a(2 w_i)} \frac{b(h - \mu_i)}{b(h + \mu_i)} \Theta_i \; \prod_{1 \leq i < j \leq L} a(\mu_i + w_j) b(\mu_i - w_j) b(w_i - w_j)^2 \; , \nonumber \\
\>
where $\Theta_i$ is given by (\ref{Theta_theor}). Formula (\ref{Hgen}) already takes into account the asymptotic behavior
stated in Lemma \ref{asymp_lemma} and this completes the proof of Theorem \ref{SOLa}.
\end{proof}

\subsection{Partial differential equations}
\label{sec:PDE}

In \Secref{sec:FZ} we have derived a functional equation governing the partition function (\ref{PF})
as a direct consequence of the reflection algebra (\ref{REA}) and the highest/lowest weight property of the
vectors $\ket{0}$ and $\ket{\bar{0}}$. Some properties of our functional equation have already been discussed in
\Secref{sec:sol} and here we intend to demonstrate some further properties.
More precisely, in this section we shall unveil a set of linear partial differential equations underlying (\ref{TPA}).
This type of hidden structure was first presented in \cite{Galleas_2011} for a similar type of equation and subsequently developed
in \cite{Galleas_proc, Galleas_2014}. The first step towards that description is to recast (\ref{TPA}) in an operatorial form.
This can be achieved with the help of the operator $D_{i}^{\alpha}$ defined as follows.

\begin{mydef} \label{dia_def}
Let $n \in \mathbb{Z}_{> 0}$ and $\alpha \in \mathbb{Z} \backslash \{1,2, \dots, n \}$. As before we write $\mathbb{C}[z_1^{\pm 1}, \dots , z_n^{\pm 1}]$ for
the space of meromorphic functions on $\mathbb{C}^n$. Now consider the following operator $D_{i}^{\alpha} \colon \mathbb{C}[z_1^{\pm 1}, \dots , z_i^{\pm 1} , \dots , z_n^{\pm 1}] \to \mathbb{C}[z_1^{\pm 1}, \dots , z_{\alpha}^{\pm 1} , \dots , z_n^{\pm 1}]$
defined by
\[
\label{Dia}
( D_{i}^{\alpha} f )(z_1, \dots , z_i , \dots , z_n) \coloneqq f(z_1, \dots , z_{\alpha} , \dots , z_n) \; .
\]
\end{mydef}
Definition \ref{dia_def} is clearly motivated by the structure of (\ref{TPA}) and it allows one
to rewrite Eq. (\ref{TPA}) as $\mathfrak{L}(\lambda_0) \mathcal{Z}(X^{1,L}) = 0$ where
\[
\label{Lop}
\mathfrak{L}(\lambda_0) \coloneqq M_0 + \sum_{i=1}^L M_i \; D_i^{0} \; .
\]
In (\ref{Lop}) we have made the dependence of $\mathfrak{L}$ on $\lambda_0$ explicit to stress
that this reformulation concentrates the whole dependence of our functional equation on $\lambda_0$
in the operator $\mathfrak{L}$. In particular, this property will allow us to extract a set of
partial differential equations from (\ref{TPA}) due to the fact that there exists
a differential realization of (\ref{Dia}) when we restrict the action of the operator $D_i^{\alpha}$
to a particular function space. In order to describe this differential realization we first need
to introduce some extra definitions and conventions.

\begin{mydef} \label{fun_space}
Let $\mathbb{K}[z_1 , \dots , z_n]$ denote the multivariate polynomial ring in the variables $z_1, \dots , z_n$ with coefficients in an
arbitrary field $\mathbb{K}$. We will also use the abbreviation $\mathbb{K}[z] \coloneqq \mathbb{K}[z_1 , \dots , z_n]$. Using this shorthand notation, we define
$\mathbb{K}_m [z] \subseteq \mathbb{K}[z]$ to be the subspace of $\mathbb{K}[z]$ formed by polynomials of degree $m$ in each variable $z_i$.
\end{mydef}

\begin{lemma} \label{diff}
The differential operator
\[
\label{Dia_diff}
D_i^{\alpha} = \sum_{k=0}^m \frac{(z_{\alpha} - z_i)^k}{k!} \frac{\partial^k }{\partial z_i^k}
\]
is a realization of (\ref{Dia}) on the space $\mathbb{K}_m [z]$.
\end{lemma}
\begin{proof}
The proof follows from the series expansion of functions in $\mathbb{K}_m [z]$. The details of this
analysis can be found in \cite{Galleas_2011, Galleas_proc}.
\end{proof}

The realization (\ref{Dia_diff}) can not be directly substituted in (\ref{Lop}) since the function
$\mathcal{Z}$ we are interested in does not belong to $\mathbb{K}_m [z]$. However, as far as the
function $\bar{\mathcal{Z}}$ defined in Lemma \ref{pol_lemma} is concerned, we have that
$\bar{\mathcal{Z}}(x_1 , \dots , x_L) \in \mathbb{K}_{2L} [x_1 , \dots , x_L]$ with
$\mathbb{K} = \mathbb{C}[y_1^{\pm 1}, \dots , y_L^{\pm 1}, q^{\pm 1} , t^{\pm 1}]$
and thus (\ref{Dia_diff}) can be employed. Here we use the notation of Lemma \ref{asymp_lemma}
where, in particular,  $x_j = e^{2 \lambda_j}$. We then define the rescaled coefficients
\[
\label{Mbar}
\bar{M}_0 \coloneqq M_0 \prod_{j=1}^{L} x_j^{-L} \qquad \mbox{and} \qquad \bar{M}_i \coloneqq M_i \prod_{\substack{j=0 \\ j \neq i}}^{L} x_j^{-L} \; .
\]
In this way Eq. (\ref{TPA}) reads $\bar{\mathfrak{L}}(x_0) \bar{\mathcal{Z}}(X^{1,L}) = 0$ where
\[
\label{bLop}
\bar{\mathfrak{L}}(x_0) \coloneqq \bar{M}_0 + \sum_{i=1}^L \bar{M}_i \; D_i^{0} \; ,
\]
and $X^{i,j} = \{ x_k \; : \; i \leq k \leq j \}$ as in Remark \ref{add1}.

Now we can substitute (\ref{Dia_diff}) in (\ref{bLop}), and the next step of our analysis
is to look at the analytical properties of $\bar{\mathfrak{L}}(x_0)$ as function of $x_0$
or equivalently $\lambda_0$. The explicit expressions for the coefficients $\bar{M}_0$ and $\bar{M}_i$
are obtained from (\ref{M0MI}) and we can readily see that $\bar{\mathfrak{L}}$ contains simple poles
at the zeroes of $a(2 \lambda_0)$, $b(\lambda_0 - \lambda_i)$ and $a(\lambda_0 + \lambda_i)$.
The residues of $\bar{\mathfrak{L}}$ at the poles $a(2 \lambda_0)=0$ and $b(\lambda_0 - \lambda_i) = 0$ vanish but
the same is not true for the poles at $a(\lambda_0 + \lambda_i)=0$. Thus (\ref{bLop}) is of the form
\[
\label{LopR}
\bar{\mathfrak{L}}(x_0) = \frac{x_0^{-\frac{(L+1)}{2}}}{\prod_{j=1}^L a(\lambda_0 + \lambda_j)} \bar{\mathfrak{L}}_R (x_0) \; ,
\]
where $\bar{\mathfrak{L}}_R (x_0)$ has no poles for $x_0 \in \mathbb{C} \backslash \{0 \}$. Moreover, the direct inspection
of $\bar{\mathfrak{L}}_R$ reveals that it is indeed a polynomial of the form
\[
\label{LopR_pol}
\bar{\mathfrak{L}}_R (x_0) = \sum_{k=0}^{2L} x_0^k \; \gen{\Omega}_k  \; ,
\]
with differential-operator valued coefficients $\gen{\Omega}_k$. Now since $\bar{\mathfrak{L}}_R (x_0)$
is a polynomial, the equation $\bar{\mathfrak{L}}_R (x_0) \bar{\mathcal{Z}}(X^{1,L}) = 0$ must be satisfied by each power
of $x_0$ separately. In this way we are left with a total of $2L+1$ partial differential equations formally reading
\[
\label{omg_k}
\gen{\Omega}_k \; \bar{\mathcal{Z}}(X^{1,L}) = 0 \qquad \qquad 0 \leq k \leq 2L \; .
\]

\paragraph{The operator $\gen{\Omega}_{2 L}$.} Due to (\ref{Dia_diff}) and the fact that
$\bar{\mathcal{Z}}(X^{1,L}) \in \mathbb{K}_{2L} [x_1 , \dots , x_L]$, the
differential operators $\gen{\Omega}_k$ are linear and contain partial derivatives with respect
to the variables $x_i$ of order ranging from $1$ to $2L$. Although the explicit form of the operators
$\gen{\Omega}_k$ for a given value of $L$ can be computed from (\ref{bLop}), (\ref{LopR}) and (\ref{LopR_pol}),
they mostly lead to cumbersome expressions which are not very enlightening. Fortunately, the situation for
the leading term operator $\gen{\Omega}_{2 L}$ is more interesting and we find the following compact expression,
\[
\label{O2L}
\gen{\Omega}_{2L} = \mathcal{U} + \sum_{i=1}^L \mathcal{Y}_i \; \frac{\partial^{2L}}{\partial x_i^{2L}} \; .
\]
The functions $\mathcal{U}$ and $\mathcal{Y}_i$ in (\ref{O2L}) explicitly read,
\<
\label{UY}
\mathcal{U} &\coloneqq & t^{-1} (1 - q^{2L}) + t \sum_{i=1}^L \left[ x_i q^2 + x_i^{-1} - (y_i + y_i^{-1})  \right] \nonumber \\
\mathcal{Y}_i &\coloneqq & - \frac{1}{(2L)!} \frac{\bar{a}_1 (x_i , x_i)}{\bar{a}_q (x_i , x_i)} \nonumber \\
&& \times \left\{ q \bar{a}_t (x_i , 1) \prod_{j=1}^L \bar{a}_q (x_i , y_j^{-1}) \bar{a}_q (x_i , y_j) \prod_{\substack{j=1 \\ j \neq i}}^{L} \frac{\bar{a}_q (x_j , x_i^{-1})}{\bar{a}_1 (x_j , x_i^{-1})} \frac{\bar{a}_1 (x_j , x_i)}{\bar{a}_q (x_j , x_i)}  \right. \nonumber \\
&& \left. \qquad + \;  \bar{a}_{q/t} (1, x_i) \prod_{j=1}^L \bar{a}_1 (x_i , y_j^{-1}) \bar{a}_1 (x_i , y_j) \prod_{\substack{j=1 \\ j \neq i}}^{L} \frac{\bar{a}_q (x_i , x_j^{-1})}{\bar{a}_1 (x_i , x_j^{-1})} \frac{\bar{a}_{q^2} (x_i , x_j)}{\bar{a}_q (x_i , x_j)} \right\} \; ,  \nonumber \\
\>
where $\bar{a}_{\omega} (x,y) \coloneqq x \omega - y^{-1} \omega^{-1}$.

Some comments are appropriate at this stage. To start with, the direct inspection of (\ref{O2L}) for small values of the
lattice length $L$ reveals that our partial differential equation is fully able to determine the desired polynomial
solution up to an overall constant factor that is fixed by Lemma \ref{asymp_lemma}.
Moreover, the structure of (\ref{O2L}) resembles that of a quantum many-body hamiltonian with higher derivatives and we can regard the partition function $\bar{\mathcal{Z}}$ as the null-eigenvalue
wave-function associated to $\gen{\Omega}_{2L}$. It is worth remarking here that a similar structure appeared previously
for the standard six-vertex model with domain-wall boundaries in \cite{Galleas_proc}. In particular, the structure
of $\gen{\Omega}_{2L}$ is also shared by higher conserved quantities of the six-vertex model as demonstrated in \cite{Galleas_2014}.
To conclude we remark that although (\ref{O2L}) results in a differential equation of order $2L$, it can still be recasted
as a system of first-order equations using the reduction of order procedure. This analysis is explicitly performed
in \Appref{sec:RED}.

\section{Concluding remarks}
\label{sec:conclusion}

This work is mainly concerned with the interplay between functional equations and the reflection
algebra in the framework developed in \cite{Galleas_2010, Galleas_SCP, Galleas_proc}. More precisely, here
we have investigated the partition function of the six-vertex model with one reflecting end and domain-wall
boundaries through this algebraic-functional approach. This methodology has been previously
considered for the  dynamical counterpart of the Yang-Baxter algebra in \cite{Galleas_2011, Galleas_2012},
and here we demonstrate the feasibility of the reflection algebra for that approach.
From this analysis we obtain functional relations satisfied by the partition function of the six-vertex
model with both domain-wall and reflecting boundaries.
Interestingly, the equation presented here exhibits the same structure as the one obtained in \cite{Galleas_2012, Galleas_proc}
for a partition function with simpler boundary conditions. Although \cite{Galleas_2012, Galleas_proc} and our present work
consider domain-wall boundary conditions, here we have also included a reflecting end, which makes this algebraic-functional analysis
significantly more involved. However, the difference between the functional equations in those works and the present one is restricted
to the explicit form of their coefficients.

The starting point for the derivation of (\ref{TPA}) is the element (\ref{ABBi}) and the corresponding
reflection relation of higher degree (\ref{ABB}). This choice is arbitrary and we would have obtained a different equation
if we had started with a different element of $\mathcal{W}_n$.
For instance, the element $\tilde{\mathcal{D}}(\lambda_0) \mathop{\overrightarrow\prod}\limits_{1 \le j \le n } \mathcal{B}(\lambda_j)$
would have resulted in an equally simple functional equation. Here we have restricted our attention to the analysis of (\ref{TPA}) since this equation
is already enough to determine the partition function.

The solution of our equation is presented in \Secref{sec:sol} and is given in terms of a multiple-contour integral over
$L$ auxiliary variables. In contrast to the determinant representation obtained in \cite{Tsuchiya_1998}, our integral
formula offers the possibility of studying the homogeneous limit $\lambda_i \rightarrow \lambda$ and $\mu_i \rightarrow \mu$
straightforwardly. This feature seems to be of relevance for the analysis of the surface free energy of the $XXZ$ model
as discussed in \cite{Kozlowski_2012}. It is also important to remark here that the multiple integral formula given in
Theorem \ref{SOLa} can also be shown to satisfy the recurrence relations derived in \cite{Tsuchiya_1998}. Those recurrence
relations, in addition to extra properties, are able to uniquely characterize the model partition function
and thus can also be used to prove Theorem \ref{SOLa}. However, finding an explicit representation would still demand a very non-trivial
guess which is not required in our framework. In this sense the approach described here also offers a systematic
way of building explicit representations.

The structure of our functional equation is further studied in \Secref{sec:PDE} and we find interesting
properties which are not apparent at first sight. For instance, we shown that our equation actually
encodes a set of linear partial differential equations. Any single equation from this set is already able to determine
the model's partition function, and thus this set is simultaneously integrated. It is worth remarking here that this
property is a common feature exhibited by integrable hierarchies of differential equations.
In this work we have not analyzed the integrability of our partial differential equations in the classical sense,
but that direction certainly deserves further investigation. Our construction yields a total of $2L+1$ equations, involving among others
the differential operator (\ref{O2L}), whose structure resembles that of a quantum many-body hamiltonian with higher-order derivatives.
Although the order of the corresponding differential equation depends on $L$, this equation can still be reformulated as a system of first-order
equations due to its linearity.

To conclude we remark here that partition functions with domain-wall boundaries and reflecting ends can also be formulated
for Solid-on-Solid models as described in \cite{Filali_2010, Filali_2011}. In that case the governing algebra
is a dynamical version of the reflection algebra and it would be interesting to investigate if our
approach can be extended to those cases.

\section{Acknowledgements}
\label{sec:ack}
This work is supported by the Netherlands Organization for Scientific Research (NWO) under the VICI grant 680-47-602
and by the ERC Advanced grant research programme No. 246974, {\it ``Supersymmetry: a window to non-perturbative physics"}.
The authors also thank the D-ITP consortium, a program of the Netherlands Organization for Scientific Research (NWO) funded by
the Dutch Ministry of Education, Culture and Science (OCW).


\section{Introduction} Across many contexts in mathematics one encounters extension problems
of the following sort: given a set $S$ of partially-defined automorphisms of an object $X$,
one seeks an object $Y\supset X$ and a set of automorphisms $\hat S$
of $Y$ such that each $s\in S$ has an extension $\hat s\in\hat S$.
In the category of finite sets, this problem is trivial because any partial permutation of a set can be extended to a permutation of that set. Less trivially,
Hrushovski \cite{hrushovski} showed
that extensions always exist in the category of finite graphs.
But if one requires extensions to respect (partially defined) compositions in $S$, such existence problems become more subtle.
In 2004
Peter Cameron \cite{cameron_extending_2004} conjectured that there does not exist an algorithm that can solve the following extension problem.

\begin{problem}\label{prob}
{\bf{Given}} partial permutations $p_1, ..., p_m$ of a finite set $X$ (that is, bijections between subsets
of $X$) such that
\begin{enumerate}
\item
$p_1={\rm{id}}_X$, and
\item
for all $i,j$ with ${\rm{dom}}(p_i)\cap {\rm{ran}}(P_j)\neq \emptyset$,
there is at most one $k$ such that $p_k$ extends $p_i\cdot p_j$
\end{enumerate}
{\bf{decide}} whether or not there exists a finite set $Y$ containing $X$, and permutations $f_i$ of $Y$ extending
$p_i$ for $i=1,...,m$, such that if $p_k$ extends $p_i\cdot p_j$ then $f_i \circ f_j = f_k$.
\end{problem}

We shall prove that this problem is algorithmically unsolvable by relating it to our
recent work on the triviality problem for finitely presented profinite groups \cite{BWprotrivial}. Cameron himself recognised
the link between these problems and his articulation of it provided impetus for our work in  \cite{BWprotrivial}.

In the final section of this paper we shall explain how our main construction
also can be adapted to prove a similar undecidability result for rigid pseudogroups.

\section{Partial Permutations and Permutoids}

To enhance the clarity of our arguments, we abstract and name the objects that are the subject
of Problem \ref{prob} --- {\em{permutoids}} --- and define certain morphisms between them.

A {\em partial permutation} of a set $X$ is a bijection between two
non-empty subsets of $X$. We denote the
domain and range of a partial permutation $p$  by ${\rm{dom}}(p)$ and ${\rm{ran}}(p)$ respectively.
By definition, $q$ {\em{extends}} $p$ if ${\rm{dom}}(p) \subset {\rm{dom}}(q)$  and $q(x) = p(x)$ for all
$x\in{\rm{dom}}(p)$.
The composition $p\cdot q$ of two partial permutations $p,q$ on $X$ is
defined if ${\rm{ran}}(p)\cap{\rm{dom}}(q)$ is non-empty:
$p\cdot q (x) = p(q(x))$ for $x\in p^{-1}({\rm{ran}}(p)\cap{\rm{dom}}(q))$.

\begin{definition}\label{defP} A {\em{permutoid}} $(\Pi; X)$
is a set $\Pi$
of partial permutations of a set $X$ such that
\begin{enumerate}
\item $\Pi$ contains $1_X$, the identity map of $X$;
\item  for all $p,q\in\Pi$ there exists at most one $r\in\Pi$ such that $r$ extends $p\cdot q$ (if the composition exists).
\end{enumerate}
The permutoid is {\em{finite}} if $X$ is finite, and \emph{trivial} if $\Pi=\{1_X\}$.

A {\em{morphism}} of permutoids $(\Pi; X) \overset{(\phi,\Phi)}\to (\Pi'; X')$ is a pair of maps
$\phi:\Pi\to\Pi'$ and $\Phi:X\to X'$ so that:
\begin{enumerate}
\item $\phi(1_X)=1_{X'}$;
\item $\Phi({\rm{dom}}(p))\subseteq {\rm{dom}} \phi(p)$
and $\phi(p)(\Phi(x)) = \Phi(p(x))$  for all $p\in \Pi$ and $x\in{\rm{dom}}(p)$;
\item if $r$ extends $p\cdot q$, with $p,q,r\in\Pi$, then $\phi(r)$ extends $\phi(p)\cdot\phi(q)$.
\end{enumerate}

The morphism $(\phi,\Phi)$ is an {\em{isomorphism}} if $\Phi$ and $\phi$ are bijections
and $\phi(p) = \Phi\circ p \circ \Phi^{-1}$ for all $p\in\Pi$.

The morphism $(\phi,\Phi)$ is a {\em{quotient map}} if $\Phi$ and $\phi$ are surjections.

The morphism $(\phi,\Phi)$ is an {\em{extension}} if $\Phi$ is injective.

An extension $(\Pi; X) \overset{(\phi,\Phi)}\to (\Pi'; X')$ is {\em{complete}} if $\Pi'\subset {\rm{Perm}}(X')$; in other words ${\rm{dom}}(p')={\rm{ran}}(p')=X'$ for all $p'\in\Pi'$.

If a finite permutoid $(\Pi; X)$ admits a finite complete extension, then
$(\Pi; X)$ is said to be {\em{developable}} and $(\Pi'; X')$ is called a
development.
\end{definition}

\begin{remarks}
(1) Cameron's Conjecture asserts that
there is no algorithm that can determine the developability
of a finite permutoid.
\smallskip

(2) If $(\Pi; X) \overset{(\phi,\Phi)}\to (\Pi'; X')$ is an extension, then
 $\phi$ will fail to be injective precisely when $\Pi$ contains two distinct
restrictions of some $p\in\Pi'$. For example, if $\Phi$ is the identity
map on $X$ and $p$ is a permutation with at least two points $x_1,x_2$ in its support,
then we obtain an extension  $(\Pi; X) \overset{(\phi,{\rm{id}})}\to (\Pi'; X)$
 by defining $p_i=p|_{x_i},\ \Pi=\{{\rm{id}}, p_1, p_2\},\ \Pi'=\{{\rm{id}}, p\}$ and $\phi(p_i)=p$.
\end{remarks}

\begin{definition} The {\em{universal group}} of a permutoid $(\Pi;X)$ is
$$
\Gamma(\Pi;X) := \< \Pi \mid pq=r \text{ if $r$ extends $p\cdot q$ }\>.
$$
\end{definition}

\begin{lemma}\label{l:quot}
\begin{enumerate}
\item If $(\Pi; X) \overset{(\phi,\Phi)}\to (\Pi'; X')$ is a quotient morphism, then
$p\mapsto \phi(p)$ defines an epimorphism of groups
$$
\phi_*  : \Gamma(\Pi;X)\to \Gamma(\Pi';X').
$$
\item
If $\Pi\subseteq{\rm{Perm}}(X)$ then there is an epimorphism
$ \Gamma(\Pi;X)\to \<\Pi\> \le {\rm{Perm}}(X)$.
\item
If a non-trivial finite permutoid $(\Pi; X)$ is developable,
 then $\Gamma(\Pi;X)$ has a non-trivial finite quotient.
\end{enumerate}
\end{lemma}

\begin{proof} Parts (1) and (2) are immediate from the definitions. For (3), note
that if $p,q\in \Pi$ are distinct, then $q$ cannot
be a restriction of $p$ for otherwise $q$ and $p$ would both be extensions of
$p\cdot {\rm{id}}_X$, contradicting Definition \ref{defP}(2). It follows that any extension
of a non-trivial permutoid is non-trivial, and hence so is its universal
group.
\end{proof}

\section{Cameron permutoids}

A {\em marked group} is a pair $(G,A)$ where $G$
is a group and $A$ is a generating set. Let $\rho$ be a positive integer.
Let $B_\rho \subset G$ be the set of elements that can be expressed as a word of length
at most $\rho$ in the generators and their inverses, and define $B_{2\rho}$ similarly.
Define $p_1$ to be the identity map on $B_{2\rho}$, and
for each $b\in B_\rho\smallsetminus\{1\}$ define  $p_b: B_\rho\to B_{2\rho}$ to be the restriction of left multiplication by $b$; that
is, $p_b(x) = bx$. Let  $\Pi_\rho=\{p_b \mid b\in B_\rho\}$.

\begin{lemma}\label{l:BisP}
The pair $(\Pi_\rho; B_{2\rho})$ is a permutoid. If $A$ is finite then this permutoid is finite.
\end{lemma}

\begin{proof} Each element $g\in G$ is uniquely determined by its action by left multiplication
on any point $x\in G$. Thus, for all $b,b'\in  B_\rho$,
if $bb'$ lies in $ B_\rho$ then $p_{bb'}$ is the unique element of $\Pi_\rho$ extending $p_b\cdot p_{b'}$,
and if not then no element of $\Pi_\rho$ extends $p_b\cdot p_{b'}$.
\end{proof}

\begin{definition}\label{d:B}
Given a marked group $(G,A)$  and a positive integer $\rho$, $(\Pi_\rho; B_{2\rho})$ is called\footnote{in recognition of the fact that Peter Cameron considered these objects in \cite{cameron_extending_2004}}
 a \emph{Cameron permutoid}.  If $\mathcal{P}\equiv \langle A\mid R \rangle$ is a finite presentation for a group $G$, then we write $\mathcal{B}_\rho(\P)$ to denote the Cameron permutoid $(\Pi_\rho; B_{2\rho})$.
\end{definition}

\begin{remark}\label{algo}
It is important to note that, in order to construct $\mathcal{B}_\rho(\P)$ from a finite presentation
$\mathcal{P}$, one needs to be able to
calculate which words of length at most $\rho$ in the generators represent equal elements of the group,
and for each pair of such elements $b,x$, one needs to calculate $bx$. This can be achieved
in an algorithmic manner {\em{provided}} that one has a solution to the word problem in $|\mathcal{P}|$.
And in order to achieve the construction for all $\rho>0$ and all presentations in a class $\mathfrak{P}$,
one needs a {\em{uniform solution}} to the word problem for the groups in  $\mathfrak{P}$.
\end{remark}

We have arranged the definitions so that the following lemma is obvious.

\begin{lemma}\label{l:onto}
For all presentations $\mathcal{P} \equiv \<A\mid R\>$ and $\mathcal{P}'\equiv \<A\mid R'\>$ with $R\subset R'$, the natural epimorphism $|\mathcal{P}|\overset{\pi}\to |\mathcal{P}'|$ induces a quotient map of permutoids $\mathcal{B}_\rho(\P)\overset{(\phi, \Phi)}\to\mathcal{B}_\rho(\P')$, where $\Phi$ is the restriction of $\pi$ to $B_{2\rho}$ and $\phi(p_b) = p_{\pi(b)}$.
\end{lemma}

If $\rho$ is large enough then there is a natural isomorphism $\Gamma(\mathcal{B}_\rho(\P))\cong |\mathcal{P}|$.  In order to see this, we need the following well-known triangulation procedure.

\begin{lemma}\label{l:T} Let $\mathcal{P}\equiv\<A\mid R\>$ be a finite presentation, let $m$ be an integer greater than half the length
of the longest relation in $R$, let $B$ be the set of elements of $G=|\mathcal{P}|$ that can be expressed as
words of length at most $m$ in the free group $F(A)$,  let $T$ be the set of words $w\in F(B)$ of length three
that equal the identity in $G$, and let $\mathcal T \equiv \<B\mid T\>$.
Then, the natural map $A\to B\subset G$ induces an isomorphism $|\mathcal{P}|\to |\mathcal{T}|$.
\end{lemma}

\iffalse
\begin{proof} We shall make Tietze moves to transform $\mathcal{P}$ into $\mathcal{T}$.
For $0=1,\dots,m$, let $S_i$ be the set of elements a distance $i$ from $1$ in the word metric
$d_A$ on $G$. Since $1\in B$ we must introduce a generating symbol $e$ representing $1$,
and this is balanced by adding the length-three relation $eee^{-1}$.
Now consider $S_1$. There is a natural surjection $\mu:A^{\pm 1}\to S_1\subset G$. We make Tietze moves
introducing a new generating symbol $b$ for each $b\in S_1$ and adding one relation of the form $ba^{\pm 1}$
detemined by a  choice of $a\in A$ such that $b\mu(a)^{\pm 1}=1$.
We then make further Tietze moves adding the redundant relations $b\alpha^{\pm 1}$ for each of the
remaining $\alpha\in A$ such that $b\mu(\alpha)^{\pm 1}=1$. (Technically speaking, we ought to express these
as length-three relations $ba^{\pm 1}e$ to get a strictly triangular presentation, but we shall ignore this.)

For each $b\in S_2$ we choose $a_1,a_2\in A^{\pm 1}$ so that $b=a_1a_2$ in $G$ and make a Tietze
move on $\<A\mid R\>$, introducing a new generating symbol $b$ and the relation $a_1a_2b^{-1}$. Then,
proceeding inductively on $i$, for each $\beta\in S_i$ we choose $a\in A^{\pm 1}$ and $b\in S_{i-1}$
such that $\beta = ba$ in $G$, and perform the Tietze move that adds $\beta$ as a generating symbol and
$ba\beta^{-1}$ as a relation. The result of all these Tietze moves is a presentation $\< B\mid T'\cup R\>$
for $G$. We make further Tietze moves to add the redundant relations $T\smallsetminus T'$.

Finally, we claim that the relations $R$ are consequences of $T$, and therefore can be deleted by
Tietze moves to complete the passage from $\mathcal{P}$ to $\mathcal{T}$. Indeed, if $r=a_1\dots a_l\in R$, then each prefix $u_i=a_1\dots a_i$ defines an element $g_i\in B$ with $g_ia_{i+1}g_{i+1}^{-1}\in T$  (and $g_0=g_l=1$), so $r$ is freely equal
to $(g_0a_1g_1^{-1})(g_1 a_2 g_2^{-1})\dots (g_{l-1}a_lg_l^{-1})$, which is a product of elements of $T$.
\end{proof}
\fi

\begin{proposition}\label{p:half} If $\rho\geq 1$, then there is a natural epimorphism of groups $\Gamma(\mathcal{B}_\rho(\P))\to |\mathcal{P}|$, and if
$\rho$ is greater than half the length of the longest relator in $R$, this is an isomorphism.
\end{proposition}

\begin{proof}
By definition,
$$
\Gamma(\mathcal{B}_\rho(\P)) = \< p_b\ (b\in B_\rho) \mid p_{b_1}p_{b_2}=p_{b_3} \text{ if $b_1b_2=b_3$ in $|\mathcal{P}|$}\>,
$$
where $B_\rho$ is the ball of radius $\rho$ about the identity in $|\mathcal{P}|$ (with word metric $d_A$).  The homomorphism $\Gamma(\mathcal{B}_\rho(\P))\to |\mathcal{P}|$ defined by $p_b\mapsto b$ is onto (since $\rho\ge 1$ and the image of $B_1$ generates $|\mathcal{P}|$).  And if $\rho$ is greater than half the length of the longest relator in $R$,  then modulo an obvious change of notation this is the isomorphism of Lemma \ref{l:T}.
\end{proof}

We need one final fact.

\begin{lemma} For all marked groups $(G,A)$ and all positive integers $\rho>\rho'>0$,
there is an extension of permutoids $(\Pi_{\rho'}; B_{2\rho'})\to (\Pi_\rho; B_{2\rho})$ given by
the inclusion $B_{2\rho'}\hookrightarrow B_{2\rho}$ and the map $\Pi_{\rho'}\to \Pi_{\rho}$
that extends left-multiplication from $B_{\rho'}$ to $B_{\rho}$.
\end{lemma}

\begin{corollary}\label{c:finite}
If $\mathcal{P}$ is a finite presentation of a finite group $G$ then, for all positive
integers $\rho$, the permutoid $\mathcal{B}_\rho(\P)$ is developable.
\end{corollary}

\begin{proof}
If $\rho$ is sufficiently large then $B_\rho=B_{2\rho}=G$ and $\Pi_\rho < {\rm{Perm}}(G)$ is the subgroup
consisting of left multiplications.
\end{proof}

\begin{remark}
A permutoid defines a {\em{pree}} in an obvious manner. By definition,
a {\em{pree}} is a non-empty set $P$ with a partially defined binary operation, i.e.\ a subset $D\subseteq P\times P$ and a map $m:D\to P$.
This terminology is due to Stallings \cite{stall_pree} (also \cite{rimlinger}); Baer \cite{baer} had earlier used the term {\em{add}} to describe such objects. Both Baer and Stallings established criteria that guarantee a pree will embed in the associated group
$$
G(P,m) := \< P \mid pq=m(p,q) \text{ for all } (p,q)\in D\>.
$$
\end{remark}

\section{Finite completions and finite quotients}

In the language of permutoids, Cameron's Conjecture (Problem \ref{prob}) is that
{\em developability is an undecidable property.}

\begin{theorem}\label{thm} There does not exist an algorithm that, given a
finite permutoid $(\Pi;X)$, can determine whether or not $(\Pi;X)$ is developable.
\end{theorem}

\begin{remark} It is clear that the isomorphism classes of finite permutoids form a recursive set, and
a naive search will eventually find a complete extension of a finite permutoid if such exists. The
content of the above theorem, then, is that there is no algorithm that
can enumerate the isomorphism classes of finite permutoids that do not
have a complete finite extension.
\end{remark}

In \cite[Theorem B]{BWprotrivial} we constructed a recursive set of finite presentations for biautomatic groups such that there is no algorithm that can determine which of these groups has a non-trivial finite quotient. The class of (bi)automatic groups admits a uniform solution to the word problem \cite[pp.~32, 112]{epstein_word_1992}. Theorem \ref{thm} therefore follows immediately from \cite[Theorem B]{BWprotrivial} and the next proposition.

\begin{proposition}\label{prop} Let $\mathfrak{P}$ be a class of finite presentations for groups drawn from
a class in which there is a uniform solution to the word problem. If there were an algorithm
that could determine whether or not a finite permutoid was developable, then
there would be an algorithm that, given any presentation
$\mathcal{P}\in\mathfrak{P}$, could determine whether or not the group $|\mathcal{P}|$ had a non-trivial finite quotient.
\end{proposition}
\begin{proof}
Given $\mathcal{P}\in\mathfrak{P}$, take $\rho$ to be at least half the length of the longest relator and use the solution to the word problem to construct $\mathcal{B}_\rho(\P)$ (cf.\ Remark \ref{algo}). Then list representatives $P_i$ for the finitely many isomorphism classes of the non-trivial
quotient permutoids.  The proposition now follows from the claim that $|\mathcal{P}|$ has a non-trivial finite quotient if and only if one of the $P_i$ is
developable.

On the one hand, if one of the  $P_i$ is developable then $\Gamma(P_i)$ has a finite quotient, by Lemma \ref{l:quot}(3), and hence, by Lemma \ref{l:quot}(1),  so does $\Gamma(\mathcal{B}_\rho(\P))$, which, by Proposition \ref{p:half}, is isomorphic to  $|\mathcal{P}|$.  Conversely, if $|\mathcal{P}|$ has a non-trivial finite quotient, with presentation $\mathcal{P}'=\<A \mid R'\>$ say, where $R\subset R'$, then $\mathcal{B}_\rho(\P')$ will be a quotient permutoid of $\mathcal{B}_\rho(\P)$, and the  $P_i$
isomorphic to it will be developable, by Corollary \ref{c:finite}.
\end{proof}

\begin{remark}
The key observation that if $\mathcal{B}_\rho(\P)$ has a complete finite extension then $|\mathcal{P}|$ has a non-trivial finite quotient is due to Peter Cameron \cite{cameron_extending_2004}.
\end{remark}

\section{Rigid developments and pseudogroups}

{\em Pseudogroups} play an important role in many geometric contexts.
A pseudogroup of local homeomorphisms on a topological space $X$ is a collection $\mathcal{H}$
of homeomorphisms $h : U \to V$ of open sets of $X$ such that:
\begin{enumerate}
\item if $h : U \to V$ and $h':U'\to V'$ are in $\mathcal{H}$ then $h^{-1}$ and the composition
$h'h: h^{-1}(V\cap U')\to h'(V\cap U')$ belong to $\mathcal{H}$;
\item the restriction of $h$ to any open subset of $U$ belongs to $\mathcal{H}$;
\item ${\rm{id}}_X \in\mathcal{H}$;
\item  if a homeomorphism between open subsets of $X$ is the union of elements
of $\mathcal{H}$, then it too belongs to $\mathcal{H}$.
\end{enumerate}
We shall concentrate on the case where $X$ is a finite set with the discrete topology.

A set $\Pi$ of partial permutations of a set $X$ determines a
pseudogroup denoted $\mathcal{H}_\Pi$, namely the pseudogroup
generated by all restrictions of the elements $p\in\Pi$. For example,
the pseudogroup associated to a Cameron
 permutoid $(\Pi_\rho; B_{2\rho})$ consists of all maps $U\to V$, with
$U,V\subseteq B_{2\rho}$, that are restrictions of left-muliplications
$x\mapsto g.x$ on $G$.

If $(\Pi;X)$ is a permutoid, then by passing
from $\Pi$ to $\mathcal{H}_\Pi$ one loses the crucial condition \ref{prob}(2).
Correspondingly, $\mathcal{H}_\Pi$ can always be
embedded in the pseudogroup $\mathcal{H}_{\Pi'}$ associated to a set $\Pi'$ of permutations
of $X$: take any choice of extension $p'\in {\rm{Perm}}(X)$ for $p\in\Pi$.

A more substantial analogue of Problem \ref{prob} in the context of pseudogroups
arises when one restricts attention to pseudogroups that
are {\em rigid} in the sense that maps are defined by their value at any point.

\begin{definition} A permutoid $(\Pi;X)$ is {\em rigid} if
for all $p\neq q\in\Pi$, there is no $x\in X$ such that $p(x)= q(x)$.

A pseudogroup $\mathcal{H}$ is {\em rigid} if $f\cup g \in \mathcal{H}$
whenever $f,g\in \mathcal{H}$ and  $f(x)=g(x)$ for some $x\in X$ (equivalently, every
element of $\mathcal{H}$ has a unique maximal extension).
\end{definition}

A basic example of a rigid pseudogroup is the pseudogroup $G\ltimes X$
associated to a free action of a group on a space $X$ (in our case a finite
set with the discrete topology). The elements of this pseudogroup are the
restrictions of the transformations in the action. In close analogy with Problem
\ref{prob}, one would like to know, given a finite rigid pseudogroup, $\mathcal{H}$ on $X$,
if one can embed $X$ in a finite set $Y$ so that the elements of $\mathcal{H}$ are restrictions
of transformations of $Y$ in a free action of a finite group $G$; in other
words we wish to embed $\mathcal{H}$ in some $G\ltimes Y$. When this can be done, we say that
$\mathcal{H}$ is {\em developable}.

\begin{theorem}\label{t:ps}
There does not exist an algorithm that can determine whether or not a finite, rigid
pseudogroup has a finite development.
\end{theorem}

The proof of this theorem is implicit in our earlier arguments; to translate
them we need the following lemma.

\begin{lemma} \label{l:trans}
Let $\mathcal{H}$ be a rigid pseudogroup on a finite set $X$ and let $\Lambda\subset \mathcal{H}$ be
the set of maximal elements.
\begin{enumerate}
\item $(\Lambda;X)$ is a rigid permutoid.
\item $\mathcal{H}_{\Lambda} = \mathcal{H}$.
\item If $\mathcal{H}=\mathcal{H}_{\Pi}$ for some permutoid $(\Pi;X)$,
then the map that assigns each $p\in\Pi$ to its maximal
extension in $\mathcal{H}$ defines an extension of permutoids $(\Pi;X)\to (\Lambda;X)$.
\item If $\mathcal{H}$ is developable, then so is $(\Lambda;X)$ (and hence $(\Pi;X)$).
\end{enumerate}
\end{lemma}

\begin{proof} The first three items follow easily from the
definitions. For example, if $p,q\in\Pi$ and $q(x)\in {\rm{ran}}(q)\cap{\rm{dom}}(p)$, then
the unique maximal element $r\in \mathcal{H}$ with $r(x)=pq(x)$ is the unique
element of $\Pi$ such that $r$ extends $p\cdot q$.

(4). If $G\ltimes Y$ is a finite development of $\mathcal{H}$, then each maximal
element $p\in \mathcal{H}$ is the restriction of the action of a unique $\hat{p}\in G$,
so  $\hat{r}=\hat{p}\hat{q}$ if $r$ extends $p\cdot q$. Thus
$\Phi:X\hookrightarrow Y$ and
 $\phi(p):=\hat{h}$ define a development of $(\Pi;X)$.
\end{proof}

Let $G$ be a group with finite generating set $A$ and let $B_r$ denote the ball of radius
$r$ about $1\in G$ in the corresponding word metric.
Earlier, we considered the permutoid $\mathcal{B}_\rho(\P)=(\Pi_\rho; B_{2\rho})$. The
associated pseudogroup $\mathcal{H}_{\Pi_\rho}$ consists of all maps $U\to V$, with
$U,V\subseteq B_{2\rho}$, that are restrictions of left multiplications
$\lambda_g:G\to G$.

\begin{proposition}\label{p2} Let $G$ be a group with finite presentation $\<A\mid R\>$,
let $\rho>\frac 1 2 \max\{|r|:r\in R\}$ be an integer
and consider the permutoid $\mathcal{B}_\rho(\P) =  (\Pi_\rho; B_{2\rho})$.
The following conditions are equivalent.
\begin{enumerate}
\item $G$ has a non-trivial finite quotient;
\item $\mathcal{B}_\rho(\P)$ has a quotient permutoid
that is developable;
\item $\mathcal{B}_\rho(\P)$ has a quotient permutoid
that  has a {\em rigid} finite development;
\item $\mathcal{B}_\rho(\P)$ has a quotient permutoid whose associated pseudogroup is
rigid and developable.
\end{enumerate}
\end{proposition}

\begin{proof} We proved the equivalence of (1) and (2) in the proof of Proposition \ref{prop}.
(3) implies (2), trivially, and (1) implies (3) because if $Q$ is a finite
quotient of $G$, then the action of $Q$ by left-multiplication on itself provides
a rigid development for some quotient $P$  of $\mathcal{B}_\rho(\P)$.

Moreover, the rigid pseudogroup $Q\ltimes Q$  associated to this action (where $Q$ acts on itself by left multiplication)
is a development of the pseudogroup defined by $P$, and therefore (1) implies (4).
Finally,  Lemma \ref{l:trans}(4) tells us that (4) implies (3).
\end{proof}

\noindent{\em Proof of Theorem \ref{t:ps}.}
We follow the proof of Proposition \ref{prop}. Taking finite presentations
in a class $\mathfrak P$
where there is a uniform solution to the word problem but no algorithm that
can determine if the groups presented have finite quotients or not, we construct the
permutoids $\mathcal{B}_\rho(\P)$ as above, list the finitely many quotients of each
$\mathcal{B}_\rho(\P)$, then pass to the pseudogroups defined by these quotients,
retaining only those pseudogroups
that are rigid (an easy check).
If there were an algorithm that could determine developability for rigid
pseudogroups, then we would apply it to the members of the resulting list and thereby
(in the light of Proposition \ref{p2}) determine which of the groups
with presentations in $\mathfrak P$  have finite quotients. This would
contradict our choice of $\mathfrak P$, and therefore no such algorithm exists.
\qed

\begin{remark}
The undecidability phenomena that we have articulated in the language of
permutoids and pseudogroups can equally be expressed in the language of
groupoids or inverse semigroups (cf.~\cite{lawson}). In the context of inverse semigroups,
Steinberg \cite{stein} has proved a result similar to Theorem \ref{t:ps} (see also
\cite{hall+}). Also, instead of
considering finite sets, one could consider sets of partial automorphisms of
simplicial complexes, for example.
\end{remark}