Extraction of Epsilon-Cycles From Finite-State Transducers
Much attention has been brought to determinization and epsilon-
removal in previous work. This article describes an algorithm for
extracting all epsilon-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,
T1 and T2, such that T1 contains no epsilon-cycles and T2 contains
all epsilon-cycles of T. Since epsilon-cycles are an obstacle for
some algorithms such as the factorization of ambiguous FSTs, the
proposed approach allows us to by-pass this problem. Epsilon-cycles
can be extracted before and re-inserted (by composition) after such
Proc. CIAA 2001, Pretoria, South Africa, pp. 191-202. (Final Proc. to appear in Lecture Notes in Computer
Science, 2002, Springer-Verlag).