THE COMPLEXITY OF OPTIMIZING FINITE-STATE TRANSDUCERS

An optimizing finite-state transducer is a nondeterministic finite-sta te transducer in which states are either maximizing or minimizing. In a given state, the optimal output is the maximum or minimum - over all possible transitions - of the transition output concatenated with the optimal output of the resulting state. The ranges of optimizing finit e-state transducers form a class in NL which includes a hierarchy base d on the number of alternations of maximizing and minimizing states in a computation.