文章基本信息

标题：Searching constant width mazes captures the AC^0 hierarchy
本地全文：下载
作者：David Mix Barrington ; Chi-Jen Lu ; Peter Bro Miltersen 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1997
卷号：1997
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We show that searching a width k maze is complete for \Pi_k, i.e., for the k'th level of the AC^0 hierarchy. Equivalently, st-connectivity for width k grid graphs is complete for \Pi_k. As an application, we show that there is a data structure solving dynamic st-connectivity for constant width grid graphs with time bound O(\log \log n) per operation on a random access machine. The dynamic algorithm is derived from the parallel one in an indirect way using algebraic tools.
关键词：AC^0, aperiodic monoids, dot-depth, dynamic graph algorithms, grid graphs, mazes