residuated idempotent semiring

In general, in the idempotent semiring $(max,+)$, an equation of form $Ax=b$ has no solution, but the inequality $Ax\leq b$ does by taking $x=\mathbb{0}$. (Here recall that in any idmepotent semiring, there is a natural partial order on the elements.) It is natural to relax equality in the search for somultions, and study instead the set of its ‘subsolutions’. One way forward in this approach is to use the notion of residuated mapping from the theory of posets.

An idempotent semiring, $S$ is residuated if the right and left multiplication maps

$\lambda_a:x\mapsto ax$

and

$\rho_a:x\mapsto xa$

from $S$ to itself are residuated.

Any complete idempotent semiring is automatically residuated. We set

$a \backslash b:= \lambda^\#_a (b) = max \{x \mid ax \leq b\}$

and

$b / a:= \rho_a^\# (b) = max \{ x \mid xa \leq b\}.$

In the completed $(max,+)$ semiring, $\overline{\mathbb{R}}_{max}$, $a\backslash b$ and $b/a$ are equal and both equal $b-a$, provided that $a\neq \mathbb{0}$, in which case they equal $+\infty$.

- Stéphane Gaubert,
*Methods and Applications of $(max,+)$ Linear Algebra,*Report 3088, January 1997, INRIA.

Last revised on September 9, 2021 at 04:53:05. See the history of this page for a list of all contributions to it.