Iterative tree arrays with logarithmic depth^†

^†This work was Supported by the Natural Sciences and Engineering Research Council of Canada under Grant A-7403, and the National Science Foundation MCS83-04756. Research of O. H. Ibarra was also supported by a John Simon Guggenheim Memorial Foundation Fellowship.

Abstract

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.

Keywords:

• Interative Arrays
• Interative Trees Arrays
• Bounded Nondeterminism
• Systolic Systems
• Parellel Computing

C.R. Categories:

• 5.22
• 5.23
• 5.25

^†This work was Supported by the Natural Sciences and Engineering Research Council of Canada under Grant A-7403, and the National Science Foundation MCS83-04756. Research of O. H. Ibarra was also supported by a John Simon Guggenheim Memorial Foundation Fellowship.

^†This work was Supported by the Natural Sciences and Engineering Research Council of Canada under Grant A-7403, and the National Science Foundation MCS83-04756. Research of O. H. Ibarra was also supported by a John Simon Guggenheim Memorial Foundation Fellowship.

Notes

^†This work was Supported by the Natural Sciences and Engineering Research Council of Canada under Grant A-7403, and the National Science Foundation MCS83-04756. Research of O. H. Ibarra was also supported by a John Simon Guggenheim Memorial Foundation Fellowship.