Decidability problems for unary output sequential transducers (Q1179182): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q1806108 |
Changed an Item |
||
Property / author | |||
Property / author: Tero J.Harju / rank | |||
Normal rank |
Revision as of 14:47, 29 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Decidability problems for unary output sequential transducers |
scientific article |
Statements
Decidability problems for unary output sequential transducers (English)
0 references
26 June 1992
0 references
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.
0 references
sequential transducers
0 references
morphic composition
0 references
decidability
0 references