Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata

Eric Allender & Klaus-Jörn Lange
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.
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.