An acceptor is a finite automaton where each transition has a label and possibly a weight. In this library, an acceptor is represented as a transducer with the input and output label of each transition being equal.
accessible
A state q is accessible iff there is a path from the initial state to q.
co-accessible
A state q is co-accessible iff there is a path from q to a final state.
delayed
An FST is delayed (or lazy, on-the-fly, or dynamic) if the computation of its states and transitions occur only when requested. The complexity of a delayed FSTs constructor is constant-time, while the complexity of its traversal is a function of only those states and transitions that are visited.
deterministic
An acceptor is deterministic iff for each state q there is at most one transition labeled with a given label. A transducer can be input deterministic (or subsequential) or output deterministic.
epsilon, ε
An input label that consumes no input or an output label emits no output.
equivalent
Two transducers are equivalent if for each input string, they produce the same output strings with the same weight. The output strings, however, may differ in the number of paths, in the location of epsilon transitions, or in the distribution of the weights along the paths.
functional
A transducer is functional if each input string is transduced to a unique output string. There may be multiple paths, however, that contain this input and output string pair.
multiplicity
The maximum number of times a label is repeated at a state - a measure of non-determinism.
out-degree
The number of transitions exiting a state.
semiring
A semiring is a set of elements (weights) together with 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.
successful path
A path from the initial state to some final state.
transducer
A transducer is a finite automaton where each transition has an input label, an output label, and possibly a weight.