I've not seen Rivas' paper -- I'll have to read it! But yes, I'm familiar with the Cayley embedding from my undergraduate abstract algebra class ^_^
I suspect the monoidal preorder compatibility condition can be rephrased in terms of the left and right actions of the monoid. Something like, \\(x \le y \implies L_z(x) \le L_z(y)\\) and \\(x \le y \implies R_z(x) \le R_z(y)\\) for all \\(z\\). So the left and right actions for all elements have to be monotone maps.
Does that complexity reduction have anything to do with [difference lists](https://stackoverflow.com/questions/13879260/why-are-difference-lists-more-efficient-than-regular-concatenation)?