2026/06/11 by Oscar H. Ibarra, Ian McQuillan · 1 voice
Computer Science · #cs.FL
paper · pdf · doi:10.1142/s0129054124430044
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 the second is in terms of multi-tape NFA 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 NPDA augmented with reversal-bounded counters are in NLOG. For the non-finite-turn case, the languages are in DSPACE(log2 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 NPDA with reversal-bounded counters that makes a polynomial (resp., exponential) number of input head reversals is in DSPACE(log2n) (resp., DSPACE(n2)). This remains true if the pushdown can flip its contents a bounded number of times.