  We prove that the problems of representing a finite ordered complemented
semigroup or finite lattice-ordered semigroup as an algebra of binary relations
over a finite set are undecidable. In the case that complementation is taken
with respect to a universal relation, this result can be extended to infinite
representations of ordered complemented semigroups.
