The composition of two (weighted) finite-state transducers is usually carried out in two steps: In the first step, all accessible states of the result are constructed regardless of their co-accessibility. Non-co-accessible states are removed afterwards in the second step. This approach can lead to huge intermediate automata with only a fraction of their states being useful in the end. We present a novel composition algorithm which avoids the construction of non useful states by using a single depth-first traversal while having the same asymptotic complexity as the existing approaches.
展开▼
