DocumentCode :
2834089
Title :
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata
Author :
Allender, Eric ; Lange, Klaus-Jörn
Author_Institution :
Dept. of Comput. Sci., Rutgers Univ., New Brunswick, NJ, USA
fYear :
2010
fDate :
9-12 June 2010
Firstpage :
172
Lastpage :
180
Abstract :
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.
Keywords :
automata theory; computational complexity; polynomials; automata nondeterminism; nondeterministic auxiliary pushdown automaton; polynomial time; symmetric auxiliary pushdown automaton; time bounded auxiliary pushdown automata; Automata; Circuits; Complexity theory; Computational complexity; Computer science; Fasteners; Legged locomotion; Polynomials; Tree graphs; USA Councils; Auxiliary Pushdown Automata; LogCFL; Reversible Computation; Symmetric Computation;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computational Complexity (CCC), 2010 IEEE 25th Annual Conference on
Conference_Location :
Cambridge, MA
ISSN :
1093-0159
Print_ISBN :
978-1-4244-7214-7
Electronic_ISBN :
1093-0159
Type :
conf
DOI :
10.1109/CCC.2010.24
Filename :
5497887
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2834089
بازگشت