Economy of Description for Basic Constructions on Rational Transductions
Henning Bordihn, Markus Holzer, Martin Kutrib, Justus Liebig University Giessen · University writing server of the Justus Liebig University Giessen (Justus-Liebig-Universität Gießen) · 2002
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.