A1 Refereed original research article in a scientific journal
DECIDABILITY PROBLEMS FOR UNARY OUTPUT SEQUENTIAL TRANSDUCERS
Authors: HARJU T, KLEIJN HCM
Publisher: ELSEVIER SCIENCE BV
Publication year: 1991
Journal:: Discrete Applied Mathematics
Journal name in source: DISCRETE APPLIED MATHEMATICS
Journal acronym: DISCRETE APPL MATH
Volume: 32
Issue: 2
First page : 131
Last page: 140
Number of pages: 10
ISSN: 0166-218X
DOI: https://doi.org/10.1016/0166-218X(91)90096-F
Abstract
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.
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.
UTU Research Portal