On real time and linear time cellular automata. (English) Zbl 0547.68050

Summary: The recognition power of one-way and two-way cellular automata under various time restrictions is compared. Generalized cellular automata (GCA) are introduced and it is shown that real time GCA are equivalent to 2n-time cellular automata. Various restricted classes of GCA are shown to be equivalent to GCA.


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


[1] 1. C. CHOFFRUT, K. CULIK II, On real-time cellular automata and trellis automata, Research Report F 114, Institute für Informationsverarbeitung, Technical University of Graz, 1983. MR767316 · Zbl 0512.68065
[2] 2. K. CULIK II, J. GRUSKA & A. SALOMMAA, Systolic trellis automata (for VLSI), Research Report CS-81-34, Dept. of Comp. Sci., University of Waterloo, 1981.
[3] 3. K. CULIK II, J. GRUSKA & A. SALOMAA, Systolic trellis automata: Stability Decidability and Complexity, Res. Rep. CS-82-04, Dept. of Comp. Sci., University of Waterloo, 1982. · Zbl 0626.68048
[4] 4. S.N. COLE, Real-time computation by n-dimensional iterative arrays of finite-state machines, I.E.E.E. Trans. on Comp., Vol. 18 1969, pp. 349-365. Zbl0172.20804 MR250518 · Zbl 0172.20804 · doi:10.1109/T-C.1969.222663
[5] 5. K. CULIK II, J. PACHL, Folding and Unrolling Systolic Arrays, ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Ottawa, August 1982.
[6] 6. C. R. DYER, One Way Bounded Cellular Automata, Inform. and Control, Vol. 44, 1980, pp. 261-281. Zbl0442.68082 MR574487 · Zbl 0442.68082 · doi:10.1016/S0019-9958(80)90164-3
[7] 7. P. C. FISCHER, Generation of primes by a one-dimensional real-time iterative array, J. Assoc. Comput. Mach., Vol. 12, 1965, pp. 388-394. Zbl0173.19105 MR186506 · Zbl 0173.19105 · doi:10.1145/321281.321290
[8] 8. F. C. HENNIE, Iterative Arrays of Logical Circuits, MIT Press, Cambridge Mass., 1961.
[9] 9. S. P. KOSARAJU, On some open problems in the theory of cellular automata, I.E.E.E. Trans. Computers, Vol. C-23, 1974, pp. 561-565. Zbl0285.68027 MR434666 · Zbl 0285.68027 · doi:10.1109/T-C.1974.223995
[10] 10. H. T. KUNG, Why Systolic Architecture? Computer Magazine, January 1982.
[11] 11. A. R. SMITH III, Real-time language recognition by one-dimensional cellular automata, J. Comput. System Sci., Vol. 6, 1972, pp. 233-253. Zbl0268.68044 MR309383 · Zbl 0268.68044 · doi:10.1016/S0022-0000(72)80004-7
[12] 12. H. UMEO, K. MORITA, K. SUGATA, Deterministic one-waysimulation of two-way real-time cellular automata and its related problems, Vol. 14, 1982, pp. 158-161. Zbl0488.68041 MR664485 · Zbl 0488.68041 · doi:10.1016/0020-0190(82)90028-X
[13] 13. A. WAKSMAN, An optimum solution to the firing squad synchronization problem, Inform. and Control, Vol. 9, 1966, pp. 66-78. Zbl1111.68527 MR191766 · Zbl 1111.68527 · doi:10.1016/S0019-9958(66)90110-0
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.