OpenGrm SFST Glossary

backoff-complete FST

a canonical FST for which each state s that has a failure transition to a state s' and another transition with a label x then there is also a transition labeled with x from s'.

canonical FST

an FST for which:

• the states are sorted by input label
• there may be failure transitions but
  • there is at most one such transition per state
  • there are no failure-transition (and/or epsilon-transition) cycles
• no assumption is made of general determinism or what transitions must be present on failure (unlike in a canonical n-gram model).
• there may be epsilon transitions¹ but they are treated by failure transitions as regular symbols with each instance behaving as if it is uniquely labeled (i.e, they are not constrained by failure transitions).

faliure transition

specially (phi) labeled transitions that are taken only when no immediate match is possible at a given state

normalized FST

a canonical FST for which the weights of the paths into the future from each state sum to Weight::One()²

---

¹When the phi_label is not 0.
²Computation is done using the log semiring (Log64Weight), appropriate for negative log probabilities. The input weight type is converted to this type internally if needed (with conversion done using a WeightConvert functor, pre-defined for common weight types like TropicalWeight and LogWeight).