Volume 10 (2014) Article 8 pp. 199-215
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata
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.