WFST over semiring

A weighted finite state transducer (WFST) (Σ,Δ,Q,E,I,F,λ,ρ) over a semiring (K,⊕,⊗,0¯,1¯) is defined as:

T(x,y)=⊕π∈P(I,x,y,F)λ(p[π])⊗w[π]⊗ρ(n[π])

Semiring is a ring may lack negation. The two operations:

• Sum: compute the weight of a sequence (sum of the weights of the

  paths

  labeled with that

  sequence

  )
• Product: compute the weight of a path (product of the weights of constitute transitions)

Important semirings:

• Probability semiring: (R+,+,×,0,1)
• Log semiring: (R∪{−∞,+∞},⊕log,+,+∞,0)
• Tropical semiring: (R∪{−∞,+∞},min,+,+∞,0)