Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-070 | 17th April 2010 18:59

Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata

RSS-Feed




TR10-070
Authors: Eric Allender, Klaus-Joern Lange
Publication: 17th April 2010 18:59
Downloads: 3052
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint