Extraction of ε-Cycles from Finite-State Transducers

Much attention has been brought to determinization and ε-removal in previous work. This article describes an algorithm for extracting all ε-cycles, which are a special type of non-determinism, from an arbitrary finite-state transducer (FST). The algorithm factorizes (decomposes) the FST, T, into two FSTs, T 1 and T 2, such that T 1 contains no ε-cycles and T 2 contains all ε-cycles of T. Since ε-cycles are an obstacle for some algorithms such as the factorization of ambiguous FSTs, the proposed approach allows us to by-pass this problem. ε-cycles can be extracted before and re-inserted (by composition) after such algorithms.