Relating the power of cellular arrays to their closure properties. (English) Zbl 0646.68071

Summary: There are many fundamental open problems concerning cellular arrays (CA’s). For example:
(1) Is the class of real-time CA languages closed under reversal (concatenation)?
(2) Are linear-time CA’s more powerful than real-time CA’s?
(3) Are nonlinear-time CA’s more powerful than linear-time CA’s?
(4) Does one-way communication reduce the computing power of a CA? Although some of these problems appear to be easier to resolve than the others, e.g., problem (1) seems easier than (2), no solution to any of these problems is forthcoming. In this paper, we investigate the relationships among these problems as well as prove some positive results concerning CA’s. We show:
(a) the class of real-time CA languages is closed under reversal if and only if linear-time CA’s are equivalent to real-time CA’s; (b) if CA’s are more powerful than CA’s restricted to one-way data communication (i.e., one-way CA’s), then nonlinear-time CA’s are more powerful than linear-time CA’s;
(c) if the class of real-time CA languages is closed under reversal, then it is also closed under concatenation. In the case of unary CA languages, we show that the class is closed under concatenation.
We also show that the language \(L=\{0^ n1^ m |\) \(m,n>0\), m divides \(n\}\) is a real-time CA language, disproving a conjecture of Bucher and Culik.


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


[1] Bucher, W.; Culik, K., On real-time and linear-time cellular automata, RAIRO Inform. Théor., 18, 4, 307-325 (1984) · Zbl 0547.68050
[2] Chang, J.; Ibarra, O.; Vergis, A., On the power of one-way communication, Proc. 27th IEEE Ann. Symp. on Foundations of Computer Science, 455-464 (1986), also J. ACM, to appear
[3] Choffrut, C.; Culik, K., On real-time cellular automata and trellis automata, Acta Inform., 21, 393-409 (1984) · Zbl 0534.68039
[4] Culik, K.; Gruska, J.; Salomaa, A., Systolic trellis automata, Internat. J. Comput. Math., 15, 195-212 (1984), Part I · Zbl 0571.68041
[5] Dyer, C., One-way bounded cellular automata, Inform. and Control, 44, 54-69 (1980)
[6] Hennie, F., Iterative Arrays of Logical Circuits (1961), MIT Press: MIT Press Cambridge, MA
[7] Kosaraju, S., On some open problems in the theory of cellular automata, IEEE Trans. on Comput., C-23, 561-565 (1974) · Zbl 0285.68027
[8] Ibarra, O.; Palis, M.; Kim, S., Some results concerning linear iterative (systolic) arrays, J. Parallel and Distributed Comput., 2, 182-218 (1985)
[9] Proc. 25th IEEE Symp. on Foundations of Computer Science, 46-55 (1984)
[10] SIAM J., 16, 6, 1135-1154 (1987), Karlsruhe, Fed. Rep. Germany · Zbl 0646.68070
[11] Paterson, M., Tape bounds for time-bounded Turing machines, J. Comput. System Sci., 6, 116-124 (1972) · Zbl 0236.02031
[12] Savitch, W., Relationships between nondeterministic and deterministic complexities, J. Comput. System Sci., 4, 177-192 (1970) · Zbl 0188.33502
[13] Smith, A., Cellular automata and formal languages, Proc. 11th IEEE Ann. Symp. on Switching and Automata Theory, 216-224 (1970)
[14] Smith, A., Cellular automata complexity trade-offs, Inform. and Control, 18, 466-482 (1971) · Zbl 0222.94057
[15] Smith, A., Real-time language recognition by one-dimensional cellular automata, J. Comput. System Sci., 6, 233-253 (1972) · Zbl 0268.68044
[16] Umeo, H.; Morita, K.; Sugata, K., Deterministic one-way simulation of two-way real-time cellular automata and its related problems, Inform. Process. Lett., 14, 159-161 (1982) · Zbl 0488.68041
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.