文章基本信息

标题：Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata
本地全文：下载
作者：Eric Allender ; Klaus-Jörn Lange
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2014
卷号：10
页码：199-215
出版社：University of Chicago
摘要：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
关键词：complexity theory; complexity classes; circuit complexity; nondeterminism; symmetry; reversibility