Decidability problems for unary output sequential transducers (Q1179182)

By a well known theory of \textit{Ibarra}, the equivalence problem for unary output sequential transducers (that is, nondeterministic generalized sequential machines having accepting states) is undecidable. This is the case even if one of the transducers is a finite substitution which, on the other hand, is a special composition of morphisms and inverse morphisms called morphic composition. Using a normal form for morphic compositions due to \textit{M. Latteux} and \textit{P. Turakainen} [Math. Syst. Theory 20(4), 261-271 (1987; Zbl 0638.68087)], the authors first prove that it is decidable whether or not a given morphic composition is equal to the finite substitution used by Ibarra. The problem is reduced to the emptiness problem for counter languages being decidable. Then using Ibarra's theorem they show that it is undecidable whether or not a given rational transduction is a morphic composition. In contrast to Ibarra's theorem the authors prove that it is decidable whether or not two given unary output sequential transducers are multiplicitly equivalent, that is, whether the transducers have equally many computations for each input/output pair. Using Ibarra's result again it is shown that it is undecidable whether or not two given generalized finite automata (that is, finite automata capable of reading words while performing a computation step) are equivalent when also the lengths of the computation are taken into account. Also some other related decidability results are established.