8-tuple , where: are defined as above; (where ε is the empty string) is the finite set of transitions; maps initial states to weights; maps final states to weights. In order to make certain operations on WFSTs well-defined, it is convenient to require the set of weights to form a semiring. Two typical semirings used in practice are the log semiring and tropical semiring: nondeterministic automata may be regarded as having weights in the Boolean semiring. Stochastic FST Stochastic FSTs (also known as probabilistic FSTs or statistical FSTs) are presumably a form of weighted FST. Operations on finite-state transducers The following operations defined on finite automata also apply to finite transducers: Union. Given transducers and , there exists a transducer such that if and only if or . Concatenation. Given transducers and , there exists a transducer such that if and only if there exist with and Kleene closure. Given a transducer , there might exist a transducer with the following properties: and does not hold unless mandated by () or (). Composition. Given a transducer on alphabets Σ and Γ and a transducer on alphabets Γ and Δ, there exists a transducer on Σ and Δ such that if and only if there exists a string such that and . This operation extends to the weighted case. This definition uses the same notation used in mathematics for relation composition. However, the conventional reading for relation composition is the other way around: given two relations and , when there exist some such that and Projection to an automaton. There are two projection functions: preserves the input tape, and preserves the output tape. The first projection, is defined as follows: Given a transducer , there exists a finite automaton such that accepts x if and only if there exists a string y for which The second projection, is defined similarly. Determinization. Given a transducer , we want to build an equivalent transducer that has a unique initial state and such that no two transitions leaving any state share the same input label. The powerset construction can be extended to transducers, or even weighted transducers, but sometimes fails to halt; indeed, some non-deterministic transducers do not admit equivalent deterministic transducers. Characterizations of determinizable transducers have been proposed along with efficient algorithms to test them: they rely on the semiring used in the weighted case as well as a general property on the