Deterministic one-way simulation of two-way real-time cellular automata and its related problems. (English) Zbl 0488.68041


68Q80 Cellular automata (computational aspects)
68Q25 Analysis of algorithms and problem complexity
68N25 Theory of operating systems


Zbl 0442.68082
Full Text: DOI


[1] Beyer, W. T., Recognition of topological invariants by iterative arrays, (Project MAC Tech. Rept. TR-66 (1969), MIT: MIT Cambridge, MA)
[2] Dyer, C. R., One-way bounded cellular automata, Inform. and Control, 44, 261-281 (1980) · Zbl 0442.68082
[3] Calikoglu, D., On the computational properties of a class of cellular automata, (Tech. Rept. 73-11 (1973), Department of Computer Science, University of Iowa)
[4] Kobayashi, K., The firing squad synchronization problem for a class of polyautomata networks, Studies on Polyautomata, 189-207 (1977)
[5] Seidel, S. R., Language recognition and the synchronization of cellular automata, (Tech. Rept. 79-02 (1979), Department of Computer Science, University of Iowa)
[6] Smith, A. R., Real-time language recognition by one-dimensional cellular automata, J. Comput. System Sci., 6, 233-253 (1972) · Zbl 0268.68044
[7] Umeo, H.; Morita, K.; Sugata, K., A generalized firing squad synchronization problem, Language and Automata Symposium at Tokai University (1981), (in Japanese)
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.