Cyclic rational transductions and polynomials of rational functions (Q916404)

This paper investigates several properties of rational transductions of finite image, i.e. mappings that map elements of a language \({\mathfrak L}\) to finite sets of elements of another language \({\mathfrak L}_ 1\). When X and Y are disjoint, then a transduction \(\tau\) from X to Y is rational when it is equal to \(\pi_ X^{-1}\circ \cap R\circ \pi_ Y\), where \(R\subset (X\cup Y)*\) is a rational language, and \(\pi_ X\) and \(\pi_ Y\) are the projections of (X\(\cup Y)*\) to X* and Y* respectively. A transduction \(\tau\) is polynomially bounded when the number of elements in the image \(\omega\tau\) is polynomially bounded by the length of \(\omega\). A transduction is cyclic if the image of each element is a subset of a cyclic set v* for some \(v\in {\mathfrak L}_ 1\). The sum of two rational transductions is defined by \(\omega.(\tau_ 1+\tau_ 2)=\omega.\tau_ 1\cup \omega.\tau_ 2\). The product of two rational transductions is defined by \(\omega.(\tau_ 1\times \tau_ 2)=\cup_{\omega_ 1\omega_ 2=\omega}(\omega_ 1.\tau_ 1)(\omega_ 2.\tau_ 2)\). A polynomial of transductions is a sum of products of transductions. Several properties of polynomially bounded and cyclic rational transductions, and polynomials of them are investigated.