A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
The equivalence problem for languages defined by transductions on D0L languages
Tekijät: Honkala J
Kustantaja: TAYLOR & FRANCIS LTD
Julkaisuvuosi: 2005
Journal: International Journal of Computer Mathematics
Tietokannassa oleva lehden nimi: INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
Lehden akronyymi: INT J COMPUT MATH
Vuosikerta: 82
Numero: 8
Aloitussivu: 911
Lopetussivu: 918
Sivujen määrä: 8
ISSN: 0020-7160
DOI: https://doi.org/10.1080/00207160412331336116
Tiivistelmä
We study the equivalence problem for languages defined by various types of transducers acting on D0L languages. We show that, given epsilon-free sequential transducers S-1,..., S-k, T-1,..., T-k and D0L languages L-1,L- L-2, whether or not /S-1/ (L-1) boolean OR...boolean OR /S-k/(L-1) = /T-1/ (L-2) boolean OR...boolean OR /T-k/ (L-2) is decidable.
We study the equivalence problem for languages defined by various types of transducers acting on D0L languages. We show that, given epsilon-free sequential transducers S-1,..., S-k, T-1,..., T-k and D0L languages L-1,L- L-2, whether or not /S-1/ (L-1) boolean OR...boolean OR /S-k/(L-1) = /T-1/ (L-2) boolean OR...boolean OR /T-k/ (L-2) is decidable.
Turun yliopiston Tutkimustietojärjestelmän portaali