Real-time language recognition by one-dimensional cellular automata. (English) Zbl 0268.68044


68T10 Pattern recognition, speech recognition
68Q45 Formal languages and automata
Full Text: DOI


[1] Arbib, M. A., (Theories of Abstract Automata (1969), Prentice-Hall, Inc.: Prentice-Hall, Inc. Englewood Cliffs, N.J.) · Zbl 0193.32801
[2] Banks, E. R., Information processing and transmission in cellular automata, (Project MAC Report MAC TR81 (January, 1971), M.I.T.: M.I.T. Cambridge, Mass.)
[3] Barzdin, Y. M., Complexity of recognition of symmetry in Turing machines, Problemy Kibernetiki, 15, 245-248 (1965) · Zbl 0255.02039
[4] Beyer, W. T., Recognition of topological invariants by arrays, (Project MAC Report MAC TR-66 (October, 1969), M.I.T.: M.I.T. Cambridge, Mass.)
[5] Book, R. V.; Greibach, S. A., Quasi-realtime languages, Math. Systems Theory, 4, 97-111 (1970) · Zbl 0188.33102
[6] (Burks, A. W., Essays on Cellular Automata (1970), University of Illinois Press: University of Illinois Press Urbana, Ill.) · Zbl 0228.94013
[7] Codd, E. F., (Cellular Automata (1968), Academic Press: Academic Press New York) · Zbl 0213.18301
[8] Cole, S. N., Real-time computation by iterative arrays of finite-state machines, (Ph.D. Dissertation (1964), Harvard University) · Zbl 0172.20804
[9] Cole, S. N., Real-time computation by \(n\)-dimensional iterative arrays of finite-state machines, IEEE Trans. Computers, C-18, 349-365 (1969) · Zbl 0172.20804
[10] Fischer, P. C., Generation of primes by a one-dimensional real-time iterative array, J. Assoc. Comput. Mach., 12, 388-394 (1965) · Zbl 0173.19105
[11] Gardner, M., On cellular automata, self-reproduction, the Garden of Eden and the game “life,” Mathematical Games Department, Sci. Amer., 224, 112-117 (1971)
[12] Hartmanis, J.; Stearns, R. E., On the computational complexity of algorithms, Trans. Amer. Math. Soc., 117, 285-306 (1965) · Zbl 0131.15404
[13] Hennie, F. C., (Iterative Arrays of Logical Circuits (1961), M.I.T. Press: M.I.T. Press Cambridge, Mass.)
[14] Hopcroft, J. E.; Ullman, J. D., (Formal Languages and Their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, Mass.) · Zbl 0196.01701
[15] Kasami, T.; Fujii, M., Some results on capabilities of one-dimensional iterative logical networks, Electronics and Commun. Japan, 51-C, 167-176 (1968)
[16] Kuroda, S. Y., Classes of languages and linear-bounded automata, Information and Control, 7, 207-223 (1964) · Zbl 0199.04002
[17] Kosaraju, S. R., Computations on iterative automata, (Ph.D. Dissertation (August, 1969), University of Pennsylvania)
[18] Moore, F. R.; Langdon, G. C., A generalized firing squad problem, Information and Control, 12, 212-220 (1968) · Zbl 0157.02202
[19] Smith, A. R., Cellular automata theory, (Technical Report No. 2 (January, 1970), Digital Systems Laboratory, Stanford University: Digital Systems Laboratory, Stanford University Stanford, California)
[20] Smith, A. R., Cellular automata and formal languages, (Proceedings of Eleventh Annual IEEE Symposium on Switching and Automata Theory. Proceedings of Eleventh Annual IEEE Symposium on Switching and Automata Theory, Santa Monica, California (1970)), 216-224
[21] Smith, A. R., Cellular automata complexity trade-offs, Information and Control, 18, 466-482 (1971) · Zbl 0222.94057
[22] Smith, A. R., Two-dimensional formal languages and pattern recognition by cellular automata, (Proceedings of Twelfth Annual IEEE Symposium on Switching and Automata Theory. Proceedings of Twelfth Annual IEEE Symposium on Switching and Automata Theory, East Lansing Mich. (1971)), 144-152
[23] Varshavsky, V. I.; Marakhovsky, V. B.; Pechansky, V. A., Synchronization of interacting automata, Math. Systems Theory, 4, 212-230 (1970) · Zbl 0223.94021
[24] Waksman, A., An optimum solution to the firing squad synchronization problem, Information and Control, 9, 66-78 (1966) · Zbl 1111.68527
[25] Yamada, H.; Amoroso, S., Tessellation automata, Information and Control, 14, 299-317 (1969) · Zbl 0182.33403
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.