Publication Search Form




We found publication with these paramters.

Extraction and recoding of input-Epsilon Cycles in finite state transducers

Andre Kempe
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.
volume 313/1 of Theoretical Computer Science, Elsevier Science, pages 145-158.