Monoids, Rings, Quasi-Rings, and Semirings

To understand the underlying mathematics of signature compilation, we need to understand the algebraic structures of monoids, rings, quasi-rings, and semi-rings.

Definition 2   A monoid is a structure $\langle P,\cdot,e\rangle$ such that:

• $P$ is a set closed under $\cdot$: $a\cdot b\in P$, for all $a,b\in P$,
• $\cdot$ is an associative binary operator: $a\cdot(b\cdot c)=(a\cdot b)\cdot c$, for all $a,b,c\in P$, and
• $e\in P$ is an identity for $\cdot$: $e\cdot a=a\cdot e=a$ for all $a\in P$.

Definition 3   A quasi-ring is a structure $\langle P, \oplus, \otimes, \bar{0}, \bar{1}, \rangle$ such that:

• $\langle P, \oplus, \bar{0}\rangle$ is a monoid,
• $\langle P, \otimes, \bar{1}\rangle$ is a monoid,
• $\bar{0}$, is an annihilator of $\otimes$: $a\otimes\bar{0} = \bar{0}\otimes a = \bar{0}$ for all $a\in P$, and
• $\otimes$ distributes over $\oplus$: $a\otimes(b\oplus c) = (a \otimes b) \oplus (a\otimes c)$ and $(b\oplus c)\otimes a = (b\otimes a) \oplus (c\otimes a)$, for all $a,b,c\in P$.

Definition 4   A ring is a quasi-ring with an additive inverse, i.e., for all $a\in P$, there exists $b\in P$ such that $a\oplus b=b\oplus a = \bar{0}$.

If $P$ is a quasi-ring, then multiplication of matrices is well-defined and has certain nice properties such as associativity and the existence of an identity.

Definition 5   Given a quasi-ring, $Q=\langle P,\oplus,\otimes,\bar{0},\bar{1} \rangle$, an $m\times n$ matrix, $A$, over $Q$, and an $n\times p$ matrix, $B$, over $Q$, then $A\cdot B$ (matrix multiplication) is the $m\times p$ matrix, $C$ over $Q$ such that:

$$c_{i,j}=\bigoplus_{k=1}^{n}a_{i,k}\otimes b_{k,j}.$$

$B_{\mathrm XOR}$ and $B_{\mathrm OR}$ are both Boolean quasi-rings. $B_{\mathrm XOR}$ is also a Boolean ring; $B_{\mathrm OR}$ is not. $B_{\mathrm OR}$ is a closed Boolean semi-ring:

Definition 6   A closed semiring is a quasi-ring, $\langle P,\oplus, \otimes,\bar{0},\bar{1}\rangle$, such that:

• $\oplus$ is idempotent: $a\oplus a=a$, for all $a\in P$,
• $P$ is closed under countable infinite summaries, $a_1\oplus a_2\oplus\ldots$, which are well-defined,
• associativity, commutativity, and idempotence extend to infinite summaries, and
• $\otimes$ distributes over infinite summaries.

In a Boolean semiring, $\oplus$ corresponds to OR and $\otimes$ corresponds to AND. OR is idempotent, i.e., $1\oplus 1=1$. This is vital for ensuring that matrix multiplication can compute a transitive closure, since transitively closed subsumption should not be `turned off' by immediate subsumption chains on more than one subtyping branch. So we need idempotence in the underlying Boolean quasi-ring. XOR is not idempotent; so the Boolean ring is not the correct structure to use.