Hacker News new | past | comments | ask | show | jobs | submit login
Fun with semirings (2013) [pdf] (cam.ac.uk)
43 points by jordigh on June 21, 2015 | hide | past | favorite | 5 comments



This link is the talk slides. There’s also a paper, which is probably a bit more useful if you aren’t listening to a presenter. http://www.cl.cam.ac.uk/~sd601/papers/semirings.pdf


A lot more detailed indeed.

ps: also the author of `mov is Turing complete`.


>Our focus will be on closed semirings, which are semirings with an additional operation called closure (denoted * ) which satisfies the axiom: a* = 1 + a * a* = 1 + a* * a

>In semirings where summing an infinite series makes sense, we can define a* as: 1 + a + a^2 + a^3 + ...

>In other semirings where subtraction and reciprocals make sense we can define a* as (1 - a)^-1

Suddenly the "generating functions" from my combinatorics course make so much more sense. It was never about functions at all! It was about reusing our knowledge of algebra on the real field and power series to manipulate a closed semiring of combinations.

In retrospect, I think it would have been less confusing to use the abstract algebra from the outset.


The term you're looking for here is "formal power series".

https://en.wikipedia.org/wiki/Formal_power_series


As Sniffnoy (https://news.ycombinator.com/item?id=9753381) mentions, you are talking about formal power series; but, although certain power series (like `x`) admit closures analogous to those above, not all (like `1`) do, and so I don't think that the formal-power-series ring (not just semiring!) is closed in any useful version of this sense.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: