Publication Search Form




We found publication with these paramters.

Extraction of Epsilon-Cycles From Finite-State Transducers

Andre Kempe
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 algorithms.
Proc. CIAA 2001, Pretoria, South Africa, pp. 191-202. (Final Proc. to appear in Lecture Notes in Computer Science, 2002, Springer-Verlag).