Semirings in Operations Research and Computer Science: More Algebra

Abstract

We undertake an axiomatic study of certain semirings and related structures that occur in operations research and computer science. We focus on the properties A,I,U,G,Z,L that have been used in the algebraic study of path problems in graphs and prove that the only implications linking the above properties are essentially those already known. On the other hand we extend those implications to the framework of left and right variants of A,I,U,G,Z,L, and we also prove two embedding theorems. Further generalizations refer mainly to semiring-like algebras with a partially defined addition, which is needed in semantics. As suggested by idempotency (I) and absorption (A), we also examine in some detail the connections between semirings and distributive lattices, which yield new systems of axioms for the latter.