A semiring is specified by two binary operations ⊕ and ⊗ and two designated elements 0 and 1 with the following properties:
A left semiring distributes on the left; a right semiring is similarly defined.
A Weight
class must have binary functions Plus
and Times
and static member functions Zero()
and One()
and
these must form (at least) a left or right semiring.
In addition, the following must be defined for a Weight
:
Member
: predicate on set membership.
>>
: reads textual representation of a weight.
<<
: prints textual representation of a weight.
Read(istream &)
: reads binary representation of a weight.
Write(ostream &)
: writes binary representation of a weight.
Hash
: maps weight to size_t.
ApproxEqual
: approximate equality (for inexact weights)
Quantize
: quantizes wrt delta (for inexact weights)
Divide
: ∀ a,b,c
s.t. Times(a, b) = c
b' = Divide(c, a, DIVIDE_LEFT)
if a left semiring, b'.Member()
and Times(a, b') = c
a' = Divide(c, b, DIVIDE_RIGHT)
if a right semiring and a'.Member()
and Times(a', b) = c
b' = Divide(c, a) = Divide(c, a, DIVIDE_ANY) = Divide(c, a, DIVIDE_LEFT) = Divide(c, a, DIVIDE_RIGHT)
if a commutative semiring, b'.Member()
and Times(a, b') = Times(b', a) = c
ReverseWeight
: the type of the corresponding reverse weight. Typically the same type as Weight
for a (both left and right) semiring. For the left string semiring, it is the right string semiring.
Reverse
: a mapping from Weight
to ReverseWeight
s.t. Reverse(Reverse(a)) = a
Reverse(Plus(a, b)) = Plus(Reverse(a), Reverse(b))
Reverse(Times(a, b)) = Times(Reverse(b), Reverse(a))
Properties
: specifies properties that hold: LeftSemiring
: indicates weights form a left semiring
RightSemiring
: indicates weights form a right semiring
Commutative
: ∀ a,b
: Times(a, b) = Times(b, a)
Idempotent
: ∀ a
: a ⊕ a = a
.
Path
: ∀ a, b
: a ⊕ b = a
or a ⊕ b = b.
-- MichaelRiley - 23 Feb 2009