Semirings (columbicubiculomania, pt.IV)

[winterkoninkje]

Anyone who's hung around me long enough knows that I'm a great fan of semirings. Partly this is because of their ubiquity in natural language processing, but mostly it's because they're the intersection of two of the most powerful and ubiquitous abstractions in mathematics. Semirings simultaneously generalize rings (by not necessarily having negation) and bounded lattices (by not necessarily being commutative nor having both operators distribute). Therefore, they generalize both arithmetic and ordering, two of the core components of mathematics. Also the fact that the natural numbers do not form a ring is a strong case for taking semirings seriously. I don't have a map this time, instead I have an extensive list of common examples. The examples fall into about half a dozen common patterns.

• Natural number-like semirings
• Integer-like rings
• Tropical and Viterbi semirings
• Bounded distributive lattices
• Boolean rings
• Regular languages
• Square matrices over a semiring

I'm sure you're already familiar with the natural numbers, integers, etc., so I won't spend much time talking about them. The one thing worth mentioning here, though, is what the heck that last column is for. It's for *-semirings (i.e., closed semirings), not to be confused with *-(semi)rings (i.e., (semi)rings with involution). Jacques Carette introduced me and Russell O'Connor to them, and Russell has written a bit about them. Since he does a good job of explaining them, I won't talk about them just now. But, because they're a bit obscure, I made sure to indicate what the asteration operation is when it exists. The one especially notable point here is that the Alexandroff compactification of the reals is no longer a ring! (Another reason to take semirings seriously.) We give up the ring-ness of the reals to obtain closed-ness and compact-ness.

The tropical and Viterbi semirings are a sort of cross between arithmetic and ordering, and you've probably never heard of them before. They are, however, rather common in computer science. They tend to arise whenever we use dynamic programming in order to find the "best" of some set of things: e.g., the most likely tag sequence, the shortest path, the longest path, etc. This is what part of speech tagging, matrix chain multiplication, and Dijkstra's algorithm are all about. And recognizing that these are semirings is what leads to generalizations like forward–backward and inside–outside, to say nothing of the Gauss–Jordan–Floyd–Warshall–McNaughton–Yamada algorithm that comes from focusing on *-semirings.

The last major class I'll talk about are the bounded distributive lattices. The reason to discuss these is just to point out that this includes all Boolean algebras (hence classical logic and subset inclusion hierarchies), all Heyting algebras (hence intuitionistic logic), and all bounded totally ordered sets.

This chart is released under Creative Commons Attribution-ShareAlike 3.0. Any questions? Anything I missed? Anything that needs further explanation?

Edit 2019.04.27: Removed the whiny intro paragraph, and fixed the link to the pdf.

Comments

[tarchannan]

Hi - incorrect assumption in second sentence. I noticed, cared, but was so busy and tired out by pre-xmas that I put off mentioning it to you until "sometime later".

[winterkoninkje]

Fair enough. Hope you enjoy them when you get the time

[xuenay.livejournal.com]

I liked the first map, but unfortunately my knowledge of algebra wasn't sufficient for me to follow things further.

[winterkoninkje]

No worries. The maps are intended, actually, for folks who wouldn't necessarily recognize much beyond the big landmarks. E.g., for the rings, I'd imagine the interested non-mathematician would only recognize fields, rings, commutative rings, and possibly Boolean rings or Kleene algebras if they're computer scientists. In refining the maps since I started them, I learned a whole lot about non-associative algebra and about ring-theory proper (i.e., what lies between rings and fields). So while I started with more than the bare landmarks, even I didn't used to recognize everything there.

In addition to the terminological issues I mentioned in the first post, another goal is just to show the breadth of the world. Interested non-mathematicians tend not to explore the landscape very much. But is that due to lack of knowledge? or due to rating the received knowledge too highly, and not realizing they're allowed to explore on their own? I think, when people's horizons are narrow, the idea of expanding those horizons doesn't even emerge, or if it is conceived then it's something for the brave and adventurous to do. But as people's horizons grow wider, they begin to realize that it's okay to eschew the well-worn path between cities, and slowly they begin to wonder: what's beyond that next hill?