**Context:** Let $\Sigma=\{U,C,A,G\}$ and $L\subset\Sigma^*$, i.e. $L$ is a language over the alphabet $\Sigma$. Let $\Sigma'=\{0,1\}$ and define a homomorphism $f:\Sigma^*\to\Sigma'^*$ by extending $U \to 00$, $C \to 01$, $A \to 10$, and $G \to 11$ in the only possible way to a homomorphism. For $L':=f(L)$ we have $L=f^{-1}(L')$, because $f$ is injective. The languages $L$ and $L'$ are nearly the same for most practical purposes. However, defining a category where they are actually isomorphic is challenging, because $f^{-1}$ is only a partial function. Nailing down the notion of a partial homomorphism between monoids seems like a reasonable first step.

A homomorphism $h:M_0\to M'_0$ between two monoids with zero $M_0$ and $M'_0$ is a monoid-homomorphism between $M_0$ and $M'_0$, which maps the zero of $M_0$ to the zero of $M'_0$.

(1) One idea to define partial homomorphisms between two monoids $M$ and $M'$ is to adjoint zeros to $M$ and $M'$ to get monoids with zero $M_0$ and $M'_0$, and define that the partial homomorphisms between $M$ and $M'$ are the restrictions of the homomorphisms between $M_0$ and $M'_0$.

(2) Another idea is that a partial homomorphisms $p:M\to M'$ is a partial function $p$ which satisfies

- $p(1)=1'$.
- If $p(x)=x'$ and $p(y)=y'$, then $p(xy)=x'y'$.

A partial homomorphism according to (1) satisfies the conditions (2), and additionally satisfies

- If $x\notin\operatorname{dom}(p)$ and $y\in M$, then $xy\notin\operatorname{dom}(p)$ and $yx\notin\operatorname{dom}(p)$.

Conditions 1, 2, and 3 together should be equivalent to definition (1). If not, please correct me.

I always favored definition (1), because then a partial homomorphism would be uniquely determined by its values on a generating set. And for a quite natural definition of partial monoids, the category of partial monoids and partial homomorphisms is equivalent to the category of monoids with zero, if definition (1) is extended appropriately to partial monoids.

**Context continued** Sadly, $f^{-1}$ is only a partial homomorphism according to definition (2), but fails to satisfy definition (1). This is sad, because the set of partial homomorphisms from $\Sigma^*$ to $\Sigma'^*$ according to definition (1) is easy to describe. For definition (2) it is not even clear whether $\operatorname{dom}(p)$ will always be computationally enumerable, let alone having any chance to computationally enumerate the set of partial homomorphisms itself. But maybe the partial isomorphisms are better behaved, so using definition (2) could still make sense.

A further test for definitions (1) and (2) is to generalize them to define when a relation $R\subset M\times M'$ is a morphism between $M$ and $M'$. Now (1) no longer makes sense, but conditions 1, 2, and 3 still make sense and become

- $1\ R\ 1'$.
- If $x\ R\ x'$ and $y\ R\ y'$, then $xy\ R\ x'y'$.
- If $x\notin\operatorname{dom}(R)$ and $y\in M$, then $xy\notin\operatorname{dom}(R)$ and $yx\notin\operatorname{dom}(R)$.

(Some authors require $\operatorname{dom}(R)=M$ for relational morphisms instead of condition 3. Thus nothing is said about partial homomorphisms, and the useful asymmetry between source and target is maintained.)

Condition 3 feels unnatural to me in this context, because it seems unable to ensure that a morphism is uniquely determined by its behavior on a generating set. But at least $\operatorname{dom}(R)$ would still be determined by its intersection with a generating set, so even this test is not fully conclusive.

Questions: Is definition (1) ever used to define partial homomorphisms? Can definition (2) be fixed to reduce its drawbacks? Maybe by using it only to define partial isomorphisms? Is the "unfixed" definition (2) ever used?