A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
DECIDABILITY PROBLEMS FOR UNARY OUTPUT SEQUENTIAL TRANSDUCERS
Tekijät: HARJU T, KLEIJN HCM
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 1991
Lehti:: Discrete Applied Mathematics
Tietokannassa oleva lehden nimi: DISCRETE APPLIED MATHEMATICS
Lehden akronyymi: DISCRETE APPL MATH
Vuosikerta: 32
Numero: 2
Aloitussivu: 131
Lopetussivu: 140
Sivujen määrä: 10
ISSN: 0166-218X
DOI: https://doi.org/10.1016/0166-218X(91)90096-F
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali