The equivalence problem for languages defined by transductions on D0L languages

: Honkala J

Publisher: TAYLOR & FRANCIS LTD

: 2005

: International Journal of Computer Mathematics

: INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS

: INT J COMPUT MATH

: 82

: 8

: 911

: 918

: 8

: 0020-7160

DOI: https://doi.org/10.1080/00207160412331336116

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.