residuated idempotent semiring


In general, in the idempotent semiring (max,+)(max,+), an equation of form Ax=bAx=b has no solution, but the inequality AxbAx\leq b does by taking x=𝟘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, SS is residuated if the right and left multiplication maps

λ a:xax\lambda_a:x\mapsto ax


ρ a:xxa\rho_a:x\mapsto xa

from SS to itself are residuated.


Any complete idempotent semiring is automatically residuated. We set

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


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

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


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