Descriptional complexity of two-way pushdown automata with restricted head reversals

Two-way nondeterministic pushdown automata () are classical nondeterministic pushdown automata () enhanced with two-way motion of the input head. In this paper, the subclass of accepting bounded languages and making at most a constant number of input head turns is studied with respect to descriptional complexity aspects. In particular, the effect of reducing the number of pushdown reversals to a constant number is of interest. It turns out that this reduction leads to an exponential blow-up in case of nondeterministic devices, and to a doubly-exponential blow-up in case of deterministic devices. If the restriction on boundedness of the languages considered and on the finiteness of the number of head and pushdown turns is dropped, the resulting trade-offs are no longer bounded by recursive functions, and so-called non-recursive trade-offs are shown.