FST Weight Requirements

A semiring is specified by two binary operations ⊕ and ⊗ and two designated elements 0 and 1 with the following properties:

• ⊕: associative, commutative, and has 0 as its identity.
• ⊗: associative and has identity 1, distributes w.r.t. ⊕, and has 0 as an annihilator: 0 ⊗ a = a ⊗ 0 = 0.

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.
• NoWeight: static member function that returns an element that is not a set member; used to signal an error.
• >>: 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))
  Typically the identity mapping in a (both left and right) semiring. In the left string semiring, it maps to the reverse string in the right string semiring.
• 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.