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 center is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.
We found no citations for this text. For information on how to provide citation information, please see our documentation.