Iterative tree arrays with logarithmic depthFootnote^†

^†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.

References

• Atallah , M. and Kosaraju , S. 1985 . A generalized dictionary machine for VLSI . IEEE Trans. Comp , 34 ( 2 ) : 151 – 155 .
   Web of Science ®Google Scholar
• Choffrut , C. and Culik II , K. 1984 . On real-time cellular automata and trellis automata . Acta Informatica , 21 ( 2 ) : 393 – 407 .
   Google Scholar
• Cole , S.N. 1969 . Real-time computation by n-dimensional iterative arrays of finite-state machines . IEEE Trans. Comp , 18 ( 2 ) : 349 – 365 .
   Web of Science ®Google Scholar
• Culik II , K. and Yu , S. 1984 . Iterative tree automata . Theoretical Computer Science , 32 ( 2 ) : 227 – 247 .
   Web of Science ®Google Scholar
• Fischer , P.C. 1965 . Generation of primes by a one-dimensional real-time iterative array . JACM , 12 ( 2 ) : 388 – 394 .
   Web of Science ®Google Scholar
• Fischer , P.C. and Kintala , C.M.R. . Computations with a restricted number of nondeterministic steps . Ninth ACM Symposium on Theory of Computing . May ,
   Google Scholar
• Harrison , M. 1978 . Introduction to Formal Language Theory , Addison-Wesley .
   Google Scholar
• Hopcroft , J. and Ullman , J. 1969 . Formal Languages and Their Relation to Automata , Addison-Wesley .
   Google Scholar
• 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 .
   Google Scholar
• Kosaraju , S. 1975 . Speed of recognition of contexi free languages for array automata . SIAM J. of Comp , 4 : 331 – 340 .
   Google Scholar
• Ottmann , T.A. , Rosenberg , A.L. and Stockmeyer , L.J. 1982 . A dictionary machine (for VLSI) . IEEE Trans. Comp , 4 : 892 – 897 .
   Google Scholar