Descriptional complexity of bounded context-free languages

We investigate finite-turn pushdown automata (PDAs) from the point of view of descriptional complexity. It is known that such automata 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, we consider finite-turn PDAs that can accept bounded languages. First, we study letter-bounded languages and prove that, in this case, the non-recursive trade-off is reduced to a recursive trade-off, more precisely, to an exponential trade-off. We present a conversion algorithm and show the optimality of the construction by proving tight lower bounds. Furthermore, we study the question of reducing the number of turns of a given finite-turn PDA. Again, we provide a conversion algorithm which shows that, in this case, the trade-off is at most polynomial. Finally, we investigate the more general case of word-bounded languages and show how the results obtained for letter-bounded languages can be extended to word-bounded languages.