A language L is bounded context-free if it is accepted by a pushdown automaton (PDA) M with a bounded number of reversals; that is, there is a constant upper bound for the number of times M switches between pushing and popping on the stack. Such languages have been investigated for decades; one point is that various algorithmic problems for context-free languages become decidable or more tractable under this restriction.

In this paper, the above property is established for a number of specific languages, beginning with a new proof that every context-free language is accepted by a PDA with at most 2n-3 reversals. Subsequently, a characterization of semi-linear languages in terms of reversal-bounded automata is given. Further results involve a generalization of languages and corresponding automata: if L is a set of tuples of strings, then L may be accepted by a multi-tape automaton of an appropriate type. One of the facts shown is a generalization of the familiar fact that every context-free language over a one-symbol alphabet is regular.

The paper does not contain any negative results of the form that certain languages are not bounded context-free, or not deterministic context-free, and so on. Naturally, such negative results are potentially more difficult, and some negative conjectures of this kind are stated as open problems.