I am studying the so called Max Min Plus Scaling (MMPS) systems that are defined as functions containg max, min, sum and multiplication by a scalar operation. An example is the function $f(x) = \max(5x+3,3x-8)-\min(-x,4x-2)+5x-7$. I want to find out how to determine that two MMPS are identical, meaning that they assume the same values $\forall x \in \mathbb{R}$. This is not trivial, since many functions are actually the same even though they seem different. For instance, the three functions
$$g(x)=\max(-x,x)\\h(x)=\max(\min(-x,-2x),\min(x,2x))\\i(x)=\max(\min(-x,-3x),x)$$
are all identical (they all correspond to the function $f(x)=|x|$).
How can I prove if two MMPS functions are the same? I could rewrite the two MMPS functions in the canonical form which means I am writing the MMPS as a min of max functions, or as a max of min functions, but then I don't know how to proceed because for instance $h_1(x)=\max(\min(-x,-2x),\min(x,2x))$ and $h_2(x)=\max(\min(-x,-5x),\min(x,5x))$ are both in canonical form but they are identical. In other words, one function $f(x)$ may have infinite canonical forms.
Best Answer
When dealing with this kind of functions, you should divide the range of function so that you could eliminate canonical forms then prove that they are identical in fact. For demonstration, let's prove that your $f,g,i$ are same by dividing the range of function.
Note that the parameters of $\max$s and $\min$s in your $g,h,i$ are integer multiples of $x$ or their $\max$, $\min$ result. Therefore, we only need to consider two cases: $x \ge 0$ and $x<0$.
i) $x \ge 0$
$2x \ge x \ge 0 \ge -x \ge -2x \ge -3x$. Therefore $$g(x)=\max(-x,x)=x\\h(x)=\max(\min(-x,-2x),\min(x,2x))=\max(-2x,x)=x\\i(x)=\max(\min(-x,-3x),x)=\max(-3x,x)=x$$
ii) $x < 0$
$2x < x < 0 < -x < -2x < -3x$. Therefore $$g(x)=\max(-x,x)=-x\\h(x)=\max(\min(-x,-2x),\min(x,2x))=\max(-x,2x)=-x\\i(x)=\max(\min(-x,-3x),x)=\max(-x,x)=-x$$
By i) and ii), $g,h,i$ are identical.