Since 2014
Searching Constant Width Mazes Captures the AC0 Hierarchy
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
Searching Constant Width Mazes Captures the AC0 Hierarchy
|
|
| Creator |
Barrington, David A. Mix
Lu, Chi-Jen Miltersen, Peter Bro Skyum, Sven |
|
| Description |
We show that searching a width k maze is complete for Pi_k, i.e.,for the k'th level of the AC0 hierarchy. Equivalently, st-connectivityfor width k grid graphs is complete for Pi_k. As an application, weshow 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.
|
|
| Publisher |
Aarhus University
|
|
| Date |
1997-01-25
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/18951
10.7146/brics.v4i25.18951 |
|
| Source |
BRICS Report Series; No 25 (1997): RS-25 Searching ConstantWidth Mazes Captures the AC0 Hierarchy
BRICS Report Series; Nr. 25 (1997): RS-25 Searching ConstantWidth Mazes Captures the AC0 Hierarchy 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/18951/16590
|
|