On the equivalence of some transductions involving letter to letter morphisms on regular languages (Q1058303): Difference between revisions

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.