Assume that ($\oplus$, $\otimes$) is a semiring over the non-negative reals.
If $\otimes$ is +, what are the possible operators for $\oplus$?
So far I have proven that max and softmax (logsumexp) are solutions. Can we characterize all possible $\oplus$?
I'd also appreciate references to relevant papers.
I'll give two answers. The first one just echoes the comments and saying that there are no such semirings, and the other saying that max gives the only continuous such semiring, if you take a nonstandard definition of semiring.
The standard definition of a (commutative) semiring is a set $R$ equipped with two operations $\otimes$ and $\oplus$, so that $(R,\otimes)$ and $(R,\oplus)$ are commutative monoids, so that $\otimes$ distributes over $\oplus$, and so that the unit of $\oplus$ annihilates $R$ under $\otimes$. I focus on the commutative case because you always want $\otimes$ to be addition, which is commutative.
Let $R$ denote the non-negative reals.
It's basically been pointed out in the comments that with this definition, there can be no such semiring structure on $R$ with addition as $\otimes$. This is because of the annihilation condition. Let $e$ be the unit of $\oplus$; then $e+a=e$ for all $a$ in $R$, which is not possible.
Next, drop the annihilation condition. I'll show that max is the only continuous choice for $\oplus$ in this less restrictive definition. I will not assume that the additive unit is $0$. Note that choosing softmax for $\oplus$ (and addition for $\otimes$) does not yield a semiring structure on $R$ with this definition because $\oplus$ does not have an identity element.
First, note that $a + (0\oplus 0) = (a + 0) \oplus (a+0) = a\oplus a$ for all $a$ by distributivity. This is true for the additive unit so $(0\oplus 0)=0$ and thus $(a\oplus a)=a$ for all $a$.
Then define $f(a)= 0\oplus a$. Using distributivity, $(b\oplus (a+b))= f(a)+b$ for all $a$ and $b$. So $\oplus$ is totally determined by $f$.
By associativity of $\oplus$, we have $f(a) = 0\oplus a=(0\oplus 0)\oplus a=0\oplus (0\oplus a)=f(f(a))$, so $f$ is a retract. Decompose $R$ as $F\sqcup G$ where $a$ is in $F$ if $f(a)=a$.
If $G$ is empty, then $(b\oplus (a+b))=a+b=\max\{a,a+b\}$. This gives the answer of max for $\oplus$ that we already know. Then instead we can assume that $G$ is nonempty. Now let $z$ be the infimum of $G$. $F$ is closed and contains $0$ so $z\in F$. Then $(z\oplus 2z) = z + (0\otimes z)= 2z$ by distributivity. But then by associativity
$$2z = z\oplus 2z = (0\oplus z)\oplus 2z = 0\oplus (z\oplus 2z)= 0\oplus 2z = f(2z)$$ so $2z\in F$.
Now assume that $f$ is continuous. We will derive a contradiction. First suppose $a\in G$ and $b\in F$ with $a < b$. Then since $f(0)=0$ and $f(b)=b$, by the intermediate value theorem there is some $c$ with $f(c)=a$. But this implies $f(a)=f^2(c)=f(c)=a$, a contradiction since $a\in G$. Then we have shown that if $a\in G$ then all $b>a$ are also in $G$. In particular, if $z>0$ then $2z$ is in both $F$ (by the explicit calculation above) and $G$ (by this paragraph, by the definition of infimum), a contradiction.
The only remaining possibility is $\inf G=0$. But then the connectedness of $F$ implies that $F=\{0\}.$ But in this case, since $f(R)=F$, necessarily $f(R)=0$ which implies that $a\oplus (a+b)= a = \min\{a,a+b\}$. But $\min$ does not have a unit in $R$.
Maybe this can be modified to show that in the case that one also drops the assumption that $\oplus$ have a unit, that min and softmax are the only other continuous options. I'll leave that to someone else.
I'll post my comment here. If $f(x,y)=x\oplus y$ and $f(x,y)$ is differentiable in $x$ and $y$ then $f(x,y) = \log_b(b^x + b^y)$. (I'm ignoring that $x \oplus y$ has no identity element (which would be $-\infty$ ad hoc)).
by def $f(x,y)+c=f(x+c,y+c)$. Taking $F(x,y)=e^{f(log(x),log(y))}$ then $F(x,y)⋅c=F(cx,cy)$.
Taking associativity and commutivity in to consideration; if i'm not mistaken the only differentiable solution to $cF(x,y)=F(cx,cy)$, $F(x,y)=F(y,x)$ and $F(x,F(y,z))=F(F(x,y),z)$ is $F(x,y)=\sqrt[r ]{x^r+y^r}$, and therefore $x \oplus y = \log_b(b^x+b^y)$ with $r = \log(b)$. QED
$r$ can then be found for arbitrary $\oplus$ by plugging in values.
I suspect there is no nice and explicit characterization.
You can take a universal-algebraic approach: start with the set of positive reals, and form the term algebra using the two operations. Then form the equivalence relation that "defines" times, using relations like 1/2 "times" 2/3 is identified with 7/6. Now you have a quotient by this relation which forms the semigroup of the augmented set under times, and you introduce further relationships that are the semiring identities. The resulting quotient S will still be "larger than the reals , but now you take any quotient of S that does not identify two reals and you have a sample semiring with your definition of times.
There may also be a clone-theoretic approach that may yield an alternative description, but I don't see such a description being useful. It may become useful to describe subsets of such functions, e.g. those that are continuous or order-preeserving.
Gerhard "When In Doubt, Try Everything" Paseman, 2016.07.24.
