Decidability problems for unary output sequential transducers. (English) Zbl 0743.68098

By a well known theory of 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 M. Latteux and 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.


68Q45 Formal languages and automata


Zbl 0638.68087
Full Text: DOI


[1] Berstel, J., Transductions and Context-Free Languages (1979), Teubner: Teubner Stuttgart · Zbl 0424.68040
[2] Eilenberg, S., Automata, Languages, and Machines, Vol. A (1974), Academic Press: Academic Press New York · Zbl 0317.94045
[3] Ibarra, O. H., The unsolvability of the equivalence problem for ε-free NGSM’s with unary input (output) alphabet and applications, SIAM J. Comput., 7, 524-532 (1978) · Zbl 0386.68054
[4] Karhumäki, J.; Linna, M., A note on morphic characterization of languages, Discrete Appl. Math., 5, 243-246 (1983) · Zbl 0499.68031
[5] Latteux, M.; Leguy, J., On the composition of morphisms and inverse morphisms, (Lecture Notes in Computer Science, 154 (1983), Springer: Springer Berlin), 430-432 · Zbl 0523.68067
[6] Latteux, M.; Turakainen, P., A new normal form for the compositions of morphisms and inverse morphisms, Math. Systems Theory, 20, 261-271 (1987) · Zbl 0638.68087
[7] Simon, I., Recognizable sets with multiplicities in the tropical semiring, (Lecture Notes in Computer Science, 324 (1988), Springer: Springer Berlin), 107-120 · Zbl 0656.68086
[8] Turakainen, P., A homomorphic characterization of principal AFLs without using intersection with regular sets, Inform. Sci., 27, 141-149 (1982) · Zbl 0506.68063
[9] Turakainen, P., A machine-oriented approach to compositions of morphisms and inverse morphisms, EATCS Bull., 20, 162-166 (1983)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.