![Sample our Bioscience journals, sign in here to start your access, Latest two full volumes FREE to you for 14 days]({"type":"image" , "src" : "/sda/5925/TOC-Subject-Sample-2021-Bioscience.jpg"})
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.
†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.