Assume the binary operator is given as a table/matrix, so constant time to compute $xy$. And likewise, assume the (relation giving rise to the) partially ordered set is also given as a table, or in any case assume constant time to check if $x \le y$.

If I want to check if a finite binary operator is residuated, what's an efficient way to do this check with the operator and order given as in above data structures?

It looks like a "dumb" approach would be O($n^3$), i.e. for every $a$ and $b$ fixed giving rise to the inequation $ax \le b$, search for (the greatest) $x$ that satisfies it. If such an $x$ cannot be found (for some $a$ and $b$), then the operator is not resituated. (That also computes the residual if you keep searching for the greatest $x$ on each inequation).

Is there a faster way?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.