DECIDABILITY PROBLEMS FOR UNARY OUTPUT SEQUENTIAL TRANSDUCERS



: HARJU T, KLEIJN HCM

Publisher: ELSEVIER SCIENCE BV

: 1991

Discrete Applied Mathematics

DISCRETE APPLIED MATHEMATICS

: DISCRETE APPL MATH

: 32

: 2

: 131

: 140

: 10

: 0166-218X

DOI: https://doi.org/10.1016/0166-218X(91)90096-F


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



Last updated on 2025-13-10 at 11:25