Language Acceptors with a Pushdown: Characterizations and Complexity (opens in new tab)

We study one-way nondeterministic pushdown automata (NPDA), 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 (NFA), and t...