Symmetry coincides with nondeterminism for time-bounded auxiliary pushdown automata

Eric Allender, Klaus Jörn Lange

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We show that every language accepted by a nondeterministic auxiliary pushdown automaton in polynomial time (that is, every language in SAC 1 = Log(CFL)) can be accepted by a symmetric auxiliary pushdown automaton in polynomial time.

Original languageEnglish (US)
Title of host publicationProceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010
Pages172-180
Number of pages9
DOIs
StatePublished - Aug 10 2010
Event25th Annual IEEE Conference on Computational Complexity, CCC 2010 - Cambridge, MA, United States
Duration: Jun 9 2010Jun 11 2010

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity

Other

Other25th Annual IEEE Conference on Computational Complexity, CCC 2010
CountryUnited States
CityCambridge, MA
Period6/9/106/11/10

All Science Journal Classification (ASJC) codes

  • Software
  • Computational Mathematics
  • Theoretical Computer Science

Keywords

  • Auxiliary pushdown automata
  • LogCFL
  • Reversible computation
  • Symmetric computation

Fingerprint Dive into the research topics of 'Symmetry coincides with nondeterminism for time-bounded auxiliary pushdown automata'. Together they form a unique fingerprint.

  • Cite this

    Allender, E., & Lange, K. J. (2010). Symmetry coincides with nondeterminism for time-bounded auxiliary pushdown automata. In Proceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010 (pp. 172-180). [5497887] (Proceedings of the Annual IEEE Conference on Computational Complexity). https://doi.org/10.1109/CCC.2010.24