Fixed point languages of rational transductions (Q1822509)

This paper studies fixed points of rational transductions (rational relations). The set of fixed points of a rational transduction as a subset of a free monoid is called a fixed point language. Here we prove that a fixed point language is always a context-sensitive language and study some special cases. The results may also be viewed as a contribution to the qualitative theory of equation in free monoids.