Iterative tree automata. (English) Zbl 0544.68055

Summary: The iterative tree automaton is introduced as a binary tree-connected network with sequential input and output at the root of the tree. The real and linear time computational power of this type of systolic system as a language acceptor is studied. It is shown that for real-time computations the arity of the tree is essential while this is not the case for linear-time computations. Our main result is that every T(n)- time nondeterministic Turing machine can be simulated by an ITA in (deterministic) cT(n)-time. A number of properties of real- and linear- time ITA are proved.


68Q45 Formal languages and automata
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI


[1] Bentley, J.I.; Kung, H.T., A tree machine for searching problems, ()
[2] Choffrut, C.; Culik, K., On real-time cellular automata and Trellis automata, (), Acta Informatica, to appear. · Zbl 0534.68039
[3] Culik, K.; Gruska, J.; Salomaa, A., Systolic automata for VLSI on balanced trees, Acta informat., 18, 335-344, (1983) · Zbl 0493.68054
[4] Cole, S.N., Real-time computation by n-dimensional iterative arrays of finite-state machines, IEEE trans. comput., 18, 349-365, (1969) · Zbl 0172.20804
[5] Culik, K.; Pachl, J., Folding and unrolling systolic arrays, ACM SIGACT-SIGOPS symposium on principles of distributed computing, 254-261, (1982), Ottawa
[6] Culik, K.; Salomaa, A.; Wood, D., Systolic tree acceptors, RAIRO theoret. inform., 18, 53-69, (1984) · Zbl 0571.68043
[7] Dyer, C.R.; Rosenfeld, A., Triangle cellular automata, Inform. and control, 48, 54-69, (1981) · Zbl 0459.68023
[8] Fischer, P.C., Generation of primes by a one-dimensional real-time iterative array, J. ACM, 12, 388-394, (1965) · Zbl 0173.19105
[9] Garey, M.R.; Johnson, D.S., Computers and intractability, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[10] Guibas, L.J.; Liang, F.M., Systolic stacks, queues and counters, ()
[11] Harrison, M.A., Introduction to formal language theory, (1970), Addison-Wesley Reading, MA
[12] Hopcroft, J.; Ullman, J., Introduction to automata theory, languages, and computations, (1979), Addison-Wesley Reading, MA
[13] Kung, H.T.; Leiserson, C.E., Systolic arrays (for VLSI), (), 256-282 · Zbl 0404.68037
[14] Kung, H.T., Why systolic architecture?, Computer magazine, (1982)
[15] Leiserson, C.E.; Saxe, J.B., Optimizing synchronous systems, (), 23-36
[16] Ottmann, T.A.; Rosenberg, A.L.; Stockmeyer, L.J., A dictionary machine (for VLSI), IEEE trans. comput., 31, 9, 892-897, (1982)
[17] Smith, A.R., Real-time language recognition by one-dimensional cellular automata, J. comput. system sci., 6, 233-253, (1972) · Zbl 0268.68044
[18] Salomaa, A., Formal languages, (1973), Academic Press New York · Zbl 0262.68025
[19] S. Yu, Doctoral thesis, in preparation.
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.