chessai/semirings

Tropical semirings

Closed this issue · 8 comments

chessai commented

There is a third tropical semiring that extends its set with both positive and negative infinity (typically treated as the extended real number line).

Bodigrim commented

Is it isomorphic to Tropical Minima (Tropical Maxima a)?

chessai commented

No - I don't think so. It looks like this:

data P = PlusInf | NegInf | P Natural

instance Semiring P where
  zero = NegInf
  one = P 0
  plus PlusInf _ = PlusInf
  plus _ PlusInf = PlusInf
  plus NegInf y = y
  plus x NegInf = x
  plus (P x) (P x) = P $ max x y
  times _ NegInf = NegInf
  times NegInf _ = NegInf
  times PlusInf _ = PlusInf
  times _ PlusInf = PlusInf
  times (P x) (P y) = P $ plus x y
chessai commented

I was wrong - the extended real number line isn't a valid semiring, the above requires something like Word or Natural.

chessai commented

The paper that introduces the semiring P is from 1986. Torsion Matrix Semigroups and Recognizable Transductions, by Jean-Paul Mascle. It uses Natural. Negatives can't be allowed - the extended real number line can't even form a semigroup.

Bodigrim commented

I am not sure what kind of intuition stands behind times rules: why times PlusInf NegInf == NegInf and not PlusInf?

chessai commented

@Bodigrim yeah, I think times PlusInf NegInf and times NegInf PlusInf are undefined. Kind of a bummer.

chessai commented

given that their is undefined behaviour in the definition here, i'm not inclined to support this.

jwaldmann commented

How does this relate to "the completed max-plus semiring", "the completed min-plus semiring", from http://www.cmap.polytechnique.fr/~gaubert/PAPERS/hla-preprint.pdf (cited in http://www.cmap.polytechnique.fr/~gaubert/MADRIDCOURSE/ )