Language Acceptors with a Pushdown: Characterizations and Complexity.

We study one-way nondeterministic pushdown automata (N P D A), optionally with reversal-bounded counters. Finite-turn pushdown automata are pushdown automata with a bound on the number of switches between pushing and popping. We give new characterizations for finite-turn pushdown automata, and for finite-turn pushdown automata augmented with reversal-bounded counters. The first is in terms of multi-tape nondeterministic finite automata (N F A), and the second is in terms of multi-tape N F A with reversal-bounded counters. We then use the characterizations to determine the complexity of the languages defined by these automata. In particular, we show that languages accepted by finite-turn N P D A augmented with reversal-bounded counters are in N L O G. For the non-finite-turn case, the languages are in D S P A C E (log 2 n) and in P. We also look at the space complexity of languages accepted by two-way machines. In particular, we show that every language accepted by a two-way N P D A with reversal-bounded counters that makes a polynomial (resp., exponential) number of input head reversals is in D S P A C E (log 2 n) (resp., D S P A C E (n 2)). This remains true if the pushdown can flip its contents a bounded number of times. [ABSTRACT FROM AUTHOR]