Balance of many-valued transductions and equivalence problems

AbstractThe notion of balance of two morphisms on a given language is generalized to deal with the whole family of rational transductions. The usefulness of balance for proving decidability of equivalence of rational transductions is established. In particular, an alternative proof for a result of Culik showing the decidability of the equivalence problem of single-valued rational transductions on regular languages is given. In addition, a new result showing the decidability of the equivalence problem of inverses of single-valued rational transductions on regular languages is obtained