  Finite-turn pushdown automata (PDA) are investigated concerning their
descriptional complexity. It is known that they accept exactly the class of
ultralinear context-free languages. Furthermore, the increase in size when
converting arbitrary PDAs accepting ultralinear languages to finite-turn PDAs
cannot be bounded by any recursive function. The latter phenomenon is known as
non-recursive trade-off. In this paper, finite-turn PDAs accepting bounded
languages are considered. First, letter-bounded languages are studied. We prove
that in this case the non-recursive trade-off is reduced to a recursive
trade-off, more precisely, to an exponential trade-off. A conversion algorithm
is presented and the optimality of the construction is shown by proving tight
lower bounds. Furthermore, the question of reducing the number of turns of a
given finite-turn PDA is studied. Again, a conversion algorithm is provided
which shows that in this case the trade-off is at most polynomial. Finally, the
more general case of word-bounded languages is investigated. We show how the
results obtained for letter-bounded languages can be extended to word-bounded
languages.
