-1
$\begingroup$

Is it possible to define an extension of the probability semiring $(\mathbb{R}^+, +, \times, 0, 1)$ such that

  • Closure $a^* = 1 + a + a^2 + \ldots$ is defined for every element of the semiring, not just for those less than $1$;
  • The semiring is divisible and cancellable.
  • There exists a total order on the elements of the semiring, such that
    • $a^* > b^*$ for any $a > b$
    • Higher-order infinities are greater than the lower-order ones: $(a^*)^* > b^*$ for any $a$ and $b$ (except where the corresponding geometric series converges to a finite value).
    • A sum or a product of a finite number of infinities is less than the next level of infinity: $a^*b^*c^* < (d^*)^*$ (again, assuming that all the involved geometric series diverge).
    • [optional] $0 < \frac{1^*}{1^* + 2^*} < \varepsilon$ for any $\varepsilon \in \mathbb{R}_{>0}$ (so, division by a higher-order infinity results in an "infinitesimal" value). Analogously, $1 < \frac{2^*}{1^* + 2^*} < 1+\varepsilon$ for any $\varepsilon \in \mathbb{R}_{>0}$.
  • The semiring can be efficiently implemented on a computer, meaning that the representation of the semiring elements is finite and, preferrably, short (assuming the floating point approximation being used), and the operations can be implemented with a reasonably low space and time complexity.

Are any such extensions known in literature? If not, is there a fundamental reason why such a semiring cannot be consistently defined?

To provide some background, I'm wondering whether it's possible to define a semiring such that every weighted automaton over that semiring will have well-defined values and a normalizer despite the presence of "diverging" loops.

$\endgroup$
9
  • $\begingroup$ What do you mean by `divisible semiring'? Does it mean that you have an operation of division inverse to multiplication? If so (and if you have a multiplicative unity) then your conditions are contradictory, because $(1^*+2^*)^{-1}$ should be zero and non-zero simultaneously (notice that $0a=a0=0$ by the definition of a semiting - or do you omit this?). $\endgroup$ Jan 15, 2014 at 10:02
  • $\begingroup$ Yes, I mean that for every element $a$ there exists element $a^{-1}$ such that $aa^{-1}=a^{-1}a=1$. You made a fair point. I probably have to tweak conditions to introduce not only infinite, but also infinitesimal values. $\endgroup$ Jan 15, 2014 at 11:05
  • $\begingroup$ I've modified my question, removing the inconsistent condition. $\endgroup$ Jan 16, 2014 at 13:59
  • $\begingroup$ I still don't quite get the "dominance" property of divisibility; assuming $(a/b)*b$ should be $a$, your second example gives $2^*=1^*+2^*$, so that either $1^*=0$, or your semiring is not cancellable - are you ok with the latter? $\endgroup$ Jan 16, 2014 at 14:26
  • 1
    $\begingroup$ Well, do you need the closure to be defined for all elements but not for those from $\mathbb R^+$? If no, how can one interprete $(A^*)^*$? Otherwise, how to interprete the condition $(A^*)^*>b^*$ (what would you do if $a^*=b$?)? $\endgroup$ Jan 16, 2014 at 19:36

1 Answer 1

0
$\begingroup$

Perhaps this is not what you want, because I do not realize which restrictions you put on ``infinite sums''. They are not defined in a usual semiring, so right now I assume that you merely wish all the elements $a^*$ to exist.

In order to fulfill the third condition you simply need that $2^*+1^*=2^*$. Here is one of the ways to perform this.

Let $S=\{0\}\cup (\mathbb R_{>0}\times \mathbb R)$. Zero is isolated, so the operations with it are trivial. For all other elements, we put $(a,b)\cdot (c,d)=(ac,b+d)$ and $$ (a,b)+(c,d)=\begin{cases} (a,b), & b>d;\\ (c,d), & b<d;\\ (a+c,b), &b=d. \end{cases} $$ This is a semifield, $(1,0)$ is multiplicative identity, and $\{0\}\cup (\mathbb R_{>0}\times\{0\})$ is a subsemifield isomorphic to the probability semiring. Now we may define $a^*$ as $(1,a)$.

$\endgroup$
6
  • $\begingroup$ Thanks for your answer, it clearly shows that I have to think more about the requirements I would like to impose on the inifite sums. In the semiring semiring you propose, for instance, $\frac{1^*}{2^*} = 0.5$, which I intuitively fill to be wrong. $\endgroup$ Jan 16, 2014 at 15:32
  • $\begingroup$ No, $\frac{1^*}{2^*}$ is not $0.5$; it is a completely different element, namely $(1,-1)$. $\endgroup$ Jan 16, 2014 at 16:53
  • $\begingroup$ Sorry, that's true, looks like I've accidentaly swapped $a$ and $b$ when computing this. How would you then define the closure of an infinite sum in this semiring, i.e. what is $(1, 1)^*$? $\endgroup$ Jan 16, 2014 at 17:07
  • $\begingroup$ Well, honestly speaking, I do not know. If you need to have only these sums --- then why not to set it by the definition? Otherwise, perhaps, you wish a larger class of infinite sums to be computable; in this case it would be better to specify this class... $\endgroup$ Jan 16, 2014 at 17:36
  • $\begingroup$ In any case, it seems that after the set up was completely changed, it does not matter anymore. $\endgroup$ Jan 16, 2014 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.