Andre Kempe
volume 313/1 of Theoretical Computer Science, Elsevier Science, pages 145-158.
Much attention has been brought to determinization and e-removal in previous work. This article describes
an algorithm for extracting all e-cycles, which are a particular type of non-determinism, from an arbitrary
finite-state transducer (FST). The algorithm decomposes the FST, T, into two FSTs, T1 and T2, such that T1
contains no e-cycles and T2 contains all e-cycles of T. The article also proposes an alternative approach where
each e-cycle of T is replaced by a single transitions with a complex label that describes the output of the
cycle. Since e-cycles are an obstacle for some algorithms such as the decomposition of ambiguous FSTs,
the proposed approaches allow us to by-pass this problem. e-Cycles can be extracted or recoded before and
re-inserted (by composition) after such algorithms.
Report number: