Real time recognition with cellular automata: A meaningful example. (English) Zbl 0776.68089

Let \(L\) be the language of all strings over the alphabet \(\{0,1\}\) such that the number of 1’s (in the string) equals the number of 1’s is the binary representation of the length (of the string). O. Ibarra, S. Kim, and S. Moran showed that \(L\) can be recognized (accepted) by a 1-dimensional cellular automaton (CA) in linear time, and they conjectured that it cannot be recognized by a CA in real time. This conjecture was disproved by the reviewer using a sequential machine model, the full scan Turing machine, which is equivalent to CA’s with respect to time complexity. The present paper gives an alternative, self-contained solution by a CA algorithm recognizing \(L\) in real time. This demonstrates the abilities of CA’s in signal processing and information management.


68Q80 Cellular automata (computational aspects)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI EuDML


[1] 1. W. BUCHER and K. CULIK, On real time and linear time cellular automata, RAIRO Inform. Théor., 18, (4), 1984, pp. 307-325. Zbl0547.68050 MR775835 · Zbl 0547.68050
[2] 2. C. CHOFFRUT, K. CULIK II, On real-time cellular automata and trellis automata, Acta Inform., 21, 1984, pp. 393-407. Zbl0534.68039 MR767316 · Zbl 0534.68039 · doi:10.1007/BF00264617
[3] 3. S. N. COLE, Real-time computation by n-dimensional iterative arrays of finite-state machine, IEEE Trans. Comput., C-18, 1969, pp. 349-365. Zbl0172.20804 MR250518 · Zbl 0172.20804 · doi:10.1109/T-C.1969.222663
[4] 4. K. CULIK, Variations of the fïring squad problem and applications, Information Processing Letters, 30, 1989, pp. 153-157, North-Holland. Zbl0665.68043 MR983761 · Zbl 0665.68043 · doi:10.1016/0020-0190(89)90134-8
[5] 5. P. C. FISCHER, Generation of primes by a one-dimensional real-time itérative array, J. ACM, 12, 1965, pp. 388-394. Zbl0173.19105 MR186506 · Zbl 0173.19105 · doi:10.1145/321281.321290
[6] 6. A. HEMMERLING, Real-time recognition of some language by trellis and cellular automata and full scan Turing machines; EATCS, n^\circ 29, June 1986, pp. 35-39. Zbl1022.68572 · Zbl 1022.68572
[7] 7. O. IBARRA and T.I. JIANG I., Relating the power of cellular arrays to their closure properties, TCS 57, 1988, pp. 225-238. Zbl0646.68071 MR960105 · Zbl 0646.68071 · doi:10.1016/0304-3975(88)90040-0
[8] 8. O. IBARRA, S. M. KIM, S. MORAN, Sequential machine characterizations of trellis automata and applications, SIAM J Comput., Vol. 14, 1985, n^\circ 2, pp. 426-447. Zbl0574.68044 MR784748 · Zbl 0574.68044 · doi:10.1137/0214033
[9] 9. A. R. SMITH, Cellular automata theory, Technical Report 2, Standford University, 1969.
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.