Iterative tree arrays with logarithmic depth†
Karel Čulík, Sheng Yü, Óscar H. Ibarra · International Journal of Computer Mathematics · 1986
An iterative tree array (ITA) is a binary tree-connected systolic network in which each cell is a finite-state machine and the input is provided serially to the root. We present an algorithm for simulating a pushdown stack of size S{n) on an ITA of depth logS(n) in real-time. Some interesting applications are the following: 1) Every linear iterative array operating in (simultaneous) time T(n) and space S(n) can be simulated by an ITA in time T(n) and depth log S(n). 2) S(n)-space bounded on-line TM's are equivalent to log S(n)-depth bounded ITA's. 3) log n depth is a necessary and sufficient condition for an ITA to recognize every context-free language. 4) log log n depth is a necessary condition for an ITA to recognize a nonregular set. 5) Every on-line nondeterministic TM with log n-bounded nondeterminism operating in linear time and space can be simulated by an ITA with O(log n) depth in linear time.