On the composition of morphisms and inverse morphisms

Abstract

In order to study composition of morphisms and inverse morphisms, we introduce starry transductions t which are, by definition, those verifying: ε ∃ t(ε) and for all words u, v, t(u) t(v) ⊂t(uv). We show that each starry transduction can be factored with two morphisms and two inverse morphisms. Then, we study some particular starry transductions. So, we prove that each rational substitution can be factored into a single morphism and two inverse morphisms and that each decreasing starry transduction can be factored into a single inverse morphism and two morphisms. That permits us to give an answer to a question posed in [5], by showing that for every rational language R, there exist morphisms h₁, h₂, h₃, g₁, g₂, g₃, such that R=h ⁻¹₃ o h₂ o h ⁻¹₁ (a)=g₃ o g ⁻¹₂ o g₁(a^*b).