pdf icon
Volume 10 (2014) Article 8 pp. 199-215
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata
Received: December 20, 2011
Revised: September 12, 2014
Published: September 17, 2014
Download article from ToC site:
[PDF (275K)] [PS (958K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
Keywords: complexity theory, complexity classes, circuit complexity, nondeterminism, symmetry, reversibility
Categories: complexity theory, complexity classes, circuit complexity, nondeterminism, symmetry, reversibility
ACM Classification: F.1.3, F.1.2, F.1.1
AMS Classification: 68Q15, 68Q10, 68Q45, 68Q05

Abstract: [Plain Text Version]

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.

A preliminary version of this work appeared in Proc. IEEE Conference on Computational Complexity (CCC'10).