Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata
Eric Allender, Klaus-Jörn Lange · 2010
We show that every language accepted by a nondeterministic auxiliary pushdown automaton in polynomial time (that is, every language in SAC1= Log(CFL)) can be accepted by a symmetric auxiliary pushdown automaton in polynomial time.