@inproceedings{2113150dd6a941d8acbba4da6e1e9e42,
title = "Symmetry coincides with nondeterminism for time-bounded auxiliary pushdown automata",
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.",
keywords = "Auxiliary pushdown automata, LogCFL, Reversible computation, Symmetric computation",
author = "Eric Allender and Lange, {Klaus J{\"o}rn}",
year = "2010",
doi = "10.1109/CCC.2010.24",
language = "English (US)",
isbn = "9780769540603",
series = "Proceedings of the Annual IEEE Conference on Computational Complexity",
pages = "172--180",
booktitle = "Proceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010",
note = "25th Annual IEEE Conference on Computational Complexity, CCC 2010 ; Conference date: 09-06-2010 Through 11-06-2010",
}