On the equivalence of some transductions involving letter to letter morphisms on regular languages |
| |
Authors: | Yael Maon |
| |
Affiliation: | (1) Department of Computer Science, Tel-Aviv University, Tel-Aviv, Israel |
| |
Abstract: | Summary Equivalence problems of some transductions involving letter to letter morphisms on regular languages are discussed. In particular, we deal with finite substitutions and inverses of finite substitutions. Our main results are the following: (i) The equivalence problem of inverses of finite substitutions on regular languages is undecidable, (ii) The existential equivalence problem of finite substitutions on regular languages is undecidable, and (iii) The length-equivalence problem of finite substitutions on regular languages is decidable. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|