Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata

摘要

We show that every language accepted by a nondeterministicauxiliary pushdown automaton in polynomial time (that is, everylanguage in SAC$^1$=LogCFL) can be accepted by a symmetricauxiliary pushdown automaton in polynomial time. A preliminary versionof this work appeared in Proc. IEEE Conference on Computational Complexity (CCC'10).