Iterative tree arrays with logarithmic depth. (English) Zbl 0655.68056

An iterative tree array (ITA) is a binay 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 log S(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.


68Q80 Cellular automata (computational aspects)
68Q45 Formal languages and automata
Full Text: DOI


[1] DOI: 10.1109/TC.1985.1676551 · Zbl 0555.68011
[2] DOI: 10.1007/BF00264617 · Zbl 0534.68039
[3] DOI: 10.1109/T-C.1969.222663 · Zbl 0172.20804
[4] DOI: 10.1016/0304-3975(84)90043-4 · Zbl 0544.68055
[5] DOI: 10.1145/321281.321290 · Zbl 0173.19105
[6] Fischer, P.C. and Kintala, C.M.R. Computations with a restricted number of nondeterministic steps. Ninth ACM Symposium on Theory of Computing. May,
[7] Harrison M., Introduction to Formal Language Theory (1978) · Zbl 0411.68058
[8] Hopcroft J., Formal Languages and Their Relation to Automata (1969) · Zbl 0196.01701
[9] Ibarra, O.H., Palis, M.A. and Kim, S.M. Designing Systolic Algorithms Using Sequential Machines. Proceedings of the 25th Ann. Symposium on Foundations of Computer Science. pp.46–55.
[10] DOI: 10.1137/0204028 · Zbl 0311.68052
[11] DOI: 10.1109/TC.1982.1676104
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.