Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata

摘要

We show that every language accepted by a nondeterministic auxiliary pushdown automaton in polynomial time (that is, every language in SAC1 = LogCFL) can be accepted by a symmetric auxiliary pushdown automaton in polynomial time.