  We study the algebraic properties of binary relations whose underlying
digraph is smooth, that is has no source or sink. Such objects have been
studied as surjective hyper-operations (shops) on the corresponding vertex set,
and as binary relations that are defined everywhere and whose inverse is also
defined everywhere. In the latter formulation, they have been called
multipermutations. We study the lattice structure of sets (monoids) of
multipermutations over an n-element domain. Through a Galois connection, these
monoids form the algebraic counterparts to sets of relations closed under
definability in positive first-order logic without equality. The first side of
this Galois connection has been elaborated previously, we show the other side
here. We study the property of inverse on multipermutations and how it connects
our monoids to groups. We use our results to give a simple dichotomy theorem
for the evaluation problem of positive first-order logic without equality on
the class of structures whose preserving multipermutations form a monoid closed
under inverse. These problems turn out either to be in Logspace or to be
Pspace-complete. We go on to study the monoid of all multipermutations on an
n-element domain, under usual composition of relations. We characterise its
Green relations, regular elements and show that it does not admit a generating
set that is polynomial on n.
