Volume 10 (2014) Article 8 pp. 199-215
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata
Received: December 20, 2011
Revised: September 12, 2014
Published: September 17, 2014
We show that every language accepted by a nondeterministic auxiliary pushdown automaton in polynomial time (that is, every language in SAC$^1$=LogCFL) can be accepted by a symmetric auxiliary pushdown automaton in polynomial time.