Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata

Eric Allender; Klaus-Jörn Lange

doi:10.7282/T3NZ89F7

Back

Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata

Journal article

Open access

Peer reviewed

Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata

Eric Allender and Klaus-Jörn Lange

Theory of Computing, Vol.10(8), pp.199-215

2014

DOI:

https://doi.org/10.7282/T3NZ89F7

Abstract

Complexity theory

Complexity classes

Circuit complexity

Nondeterminism

Symmetry (Mathematics)

Reversible computing

Computational complexity

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.

Files and links (3)

pdf

v010a008283.69 kBDownload View

Version of Record (VoR) Journal Article Open Access

url

http://dx.doi.org/10.4086/toc.2014.v010a008View

Version of Record (VoR) Theory of Computing

url

Report an accessibility issueView

Please complete a content remediation request to report an accessibility issue with a library electronic resource, website, or service.

Metrics

518 File downloads

83 Record Views

Details

Title: Subtitle: Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata
Creators: Eric Allender (Author) - Computer Science (New Brunswick), Rutgers University
Klaus-Jörn Lange (Author) - Universität Tübingen
Publication Details: Theory of Computing, Vol.10(8), pp.199-215
Date published: 2014
Publisher: theoryofcomputing.org
Number of pages: 17 p.
Grant note: National Science Foundation - CCF-1064785 ; National Science Foundation - CCF-0832787
Academic Unit: School of Arts and Sciences; Computer Science (SAS)
Language: English
Resource Type: Journal article
Comment: Licensed under a Creative Commons Attribution License (CC-BY) http://creativecommons.org/licenses/by/3.0/
Identifiers: 991031549928104646