A1 Refereed original research article in a scientific journal
The equivalence problem for languages defined by transductions on D0L languages
Authors: Honkala J
Publisher: TAYLOR & FRANCIS LTD
Publication year: 2005
Journal: International Journal of Computer Mathematics
Journal name in source: INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
Journal acronym: INT J COMPUT MATH
Volume: 82
Issue: 8
First page : 911
Last page: 918
Number of pages: 8
ISSN: 0020-7160
DOI: https://doi.org/10.1080/00207160412331336116
Abstract
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.
UTU Research Portal