Decidability problems for unary output sequential transducers

Ibarra has proved that the equivalence problem for unary output sequential transducers (nondeterministic and with accepting states) is undecidable. Here the authors apply this result to prove that one cannot decide whether a sequential transducer realizes a composition of morphisms and inverse morphisms. Next they translate Ibarra’s result to generalized finite automata and among other things, prove that it is undecidable whether two generalized finite automata are equivalent when the lengths of the computations are also taken into consideration. Finally the authors show that in contrast to Ibarra’s result the multiplicity equivalence problem for unary output sequential transducers is decidable.