Minimal signatures with undecidability of representability by binary relations

Robin Hirsch, Marcel Jackson, Jaš Šemrl

A semigroup of binary relations (under composition) on a set $X$ is \emph{complemented} if it is closed under the taking of complements within $X\times X$. We resolve a 1991 proble…