Economy of Descriptions for Basic Constructions on Rational Transductions

The state complexities of basic constructions on rational transductions are investigated. Given rational transductions, described by rational transducers, and an operation thereon we consider the number of states that is sufficient and necessary in the worst case to describe the resulting transduction. In particular, tight bounds are shown for inversion, union, weak intersection, concatenation, reversal, homomorphism, and composition, i.e., for some of those operations under which rational transductions are closed.