The complexity of optimizing finite-state transducers (Q1329734)

The model of an optimizing finite state transducer is a hybrid between an alternating finite state automaton and a metric Turing machine as introduced by Krentel. The alternating character is introduced by assigning the labels MAX and MIN to states in a finite state transducer. The device realises a transducer by mapping an input string on the output string generated along a branch in a full computation tree selected by chosing the lexicographical maximum (minimum) depending on the state's label over the optimizing yields over the subtrees as determined recursively by this definition one level below in the tree. As a consequence the semantics equation amounts to a recursive scheme which has to be evaluated bottom up, processing in this way the input symbols from right to left rather than in the standard left-to-right order. As defined the evaluation of the transducer requires exponential time and polynomial space. In the paper the authors provide for an evaluation scheme based on an exotic matrix calculus (which fails to obey elementary matrix algebras laws like associativity of multiplication) which reduces the evaluation time to the polynomial level. A subsequent space efficient representation reduces the problem of membership in the range of a transducer to nondeterministic logspace. This construction is rather ingenious (the standard guess and verify method still requiring linear space). These ranges furthermore include non context free languages. By bounding the number of alternations of MAX and MIN along a computation branch a hierarchy is obtained, of which only the bottom layers can be shown to be proper. Further results on this model can be found in the first author's ph.d. thesis defended in 1988 at Iowa State Univ.