Decidability problems for unary output sequential transducers.

*(English)*Zbl 0743.68098By 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.

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.

Reviewer: P.Turakainen (Oulu)

##### MSC:

68Q45 | Formal languages and automata |

PDF
BibTeX
XML
Cite

\textit{T. Harju} and \textit{H. C. M. Kleijn}, Discrete Appl. Math. 32, No. 2, 131--140 (1991; Zbl 0743.68098)

Full Text:
DOI

##### References:

[1] | Berstel, J., Transductions and context-free languages, (1979), Teubner Stuttgart · Zbl 0424.68040 |

[2] | Eilenberg, S., Automata, languages, and machines, Vol. A, (1974), 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, (), 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, (), 107-120 |

[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.