Theory of Computing
-------------------
Title     : Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata
Authors   : Eric Allender and Klaus-Joern Lange
Volume    : 10
Number    : 8
Pages     : 199-215
URL       : https://theoryofcomputing.org/articles/v010a008

Abstract
--------

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.

A preliminary version of this work appeared in 
Proc. IEEE Conference on Computational Complexity (CCC'10).