Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with AuxPDAs:
TR10-070 | 17th April 2010
Eric Allender, Klaus-Joern Lange

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 SAC$^1$ = LogCFL) can be accepted by a symmetric auxiliary pushdown automaton in polynomial time.

more >>>

ISSN 1433-8092 | Imprint