TWiki> FST Web>FstQuickTour>FstWeightRequirements (2012-03-01, MichaelRiley)

# 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.`
Topic revision: r15 - 2012-03-01 - MichaelRiley

Copyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback