2
$\begingroup$

Consider the arithmetic expressions obtained by allowing the constants 0 and 1, boolean variables, and allowing the operations $\min\{s,t\},\max\{s,t\}$, and $1-t$ where $s,t$ are expressions. Clearly we can only get the values 0 and 1 by evaluating these expressions (with an assignment to the variables). We wish to add a quantitative element to these expressions, by means of a weighted average. We consider the following operators: $\oplus_\lambda$, which is defined by $s\oplus_\lambda t=\lambda s+ (1-\lambda)t$, for any $\lambda\in [0,1]$. $\otimes_\lambda$, which is defined by $s\otimes_\lambda t=\lambda \max\{s,t\}+(1-\lambda)\min\{s,t\}$.

Intuitively, the difference is whether we attempt to interpolate between $\min$ and $\max$, or to add an addition element.

The question is: is the arithmetic with $\oplus$ strictly more expressive than $\otimes$?

Obviously, $\otimes$ can be captured by $\oplus$, since: $$s\otimes_\lambda t=\max\{s,t\}\oplus_\lambda \min\{s,t\}$$ For the other direction, we have a partial result: $$(s\otimes_\lambda 0)\otimes_\frac12 (t\otimes_{1-\lambda}0)=\frac12(s\oplus_\lambda t)$$ But I can't seem to be able to get rid of that $\frac12$ (recall that $\lambda\in [0,1]$), or to prove that there is an expressiveness difference.

Thanks!

$\endgroup$
3
  • 1
    $\begingroup$ $\min$, $\max$, and $\otimes_\gamma$ are all commutative. $\oplus_\gamma$ is not (except when $\gamma = 1/2$). $\endgroup$
    – Jeffε
    Mar 2 '12 at 13:04
  • $\begingroup$ $\oplus_\lambda$ is not symmetric unless $\lambda=\frac{1}{2}$. $\endgroup$
    – Kaveh
    Mar 2 '12 at 14:25
  • 1
    $\begingroup$ As you can see, we can break the symmetry "manually", by selecting $\lambda$ according to the order of the parameters. That's how we obtain $\frac12(s\oplus_\lambda t)$ using the symmetric $\otimes$. So this doesn't prove that $\oplus$ is more expressive. $\endgroup$
    – Shaull
    Mar 2 '12 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.