×

zbMATH — the first resource for mathematics

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

MSC:
68T10 Pattern recognition, speech recognition
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arbib, M.A., ()
[2] Banks, E.R., Information processing and transmission in cellular automata, ()
[3] Barzdin, Y.M., Complexity of recognition of symmetry in Turing machines, Problemy kibernetiki, 15, 245-248, (1965)
[4] Beyer, W.T., Recognition of topological invariants by arrays, ()
[5] Book, R.V.; Greibach, S.A., Quasi-realtime languages, Math. systems theory, 4, 97-111, (1970) · Zbl 0188.33102
[6] ()
[7] Codd, E.F., ()
[8] Cole, S.N., Real-time computation by iterative arrays of finite-state machines, () · 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., ()
[14] Hopcroft, J.E.; Ullman, J.D., ()
[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, ()
[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, ()
[20] Smith, A.R., Cellular automata and formal languages, (), 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, (), 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.