×
Culik, K. II; Hurd, L. P.; Yu, S.

Computation theoretic aspects of cellular automata. (English) Zbl 0729.68052

Physica D 45, No. 1-3, 357-378 (1990).
Summary: Cellular automata may be viewed as computational models of complex systems. They also can be seen as continuous functions on a particular faily of compact metric spaces. This paper surveys results largely motivated by an attempt to answer questions posed by the latter approach by means of techniques from the former.

Cited in 21 Documents

MSC:

68Q80 Cellular automata (computational aspects)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)

Keywords:

Cellular automata; computational models; complex systems
PDF BibTeX XML Cite
\textit{K. Culik II} et al., Physica D 45, No. 1--3, 357--378 (1990; Zbl 0729.68052)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] von Neumann, J., ()
[2] Wolfram, S., Universality and complexity in cellular automata, Physica D, 10, 1, (1984)
[3] Culik, K.; Yu, S., Undecidability of CA classification schemes, Complex systems, 2, 177, (1988) · Zbl 0657.68054
[4] Hurd, L.P., Formal language characterizations of cellular automaton limit sets, Complex systems, 1, 69, (1987) · Zbl 0655.68105
[5] Ginsburg, S., Algebraic and automata-theoretic properties of formal languages, (1975), North-Holland Amsterdam · Zbl 0325.68002
[6] Kelley, J.L., General topology, (1955), Van Nostrand New York · Zbl 0066.16604
[7] Hedlund, G.A., Endomorphisms and automorphisms of the shift dynamical system, (), Math. syst. theor., 3, 320, (1969) · Zbl 0182.56901
[8] Arbib, M.A., Simple self-reproducing universal automata, Information control, 9, 177, (1966) · Zbl 0143.02102
[9] Buening, H.Kleine; Ottmann, Th., Kleine universale mehrdimensionale turingmaschinen, Elektron. informationsverarbeitung kybern., 13, 179, (1977) · Zbl 0363.02041
[10] Minsky, M., Computation: finite and infinite machines, (1967), Prentice Hall Englewood Cliffs, NJ · Zbl 0195.02402
[11] Priese, L., Towards a precise characterization of the complexity of universal and nonuniversal Turing machines, SIAM J. comput., 8, 508, (1979) · Zbl 0426.68024
[12] Smith, A.R., Simple computation-universal cellular spaces, J. ACM, 18, 339, (1971) · Zbl 0221.94071
[13] Albert, J.; Culik, K., A simple universal cellular automaton and its one-way and totalistic version, Complex systems, 1, 1, (1987) · Zbl 0655.68065
[14] Dyer, C.R., One way bounded cellular automata, Information control, 44, 261, (1980) · Zbl 0442.68082
[15] Culik, K.; Fris, I., Topological transformations as a tool in the design of systolic networks, J. theoret. computer sci., 37, 183, (1985) · Zbl 0584.68068
[16] Culik, K.; Yu, S., Translation of systolic algorithms between systems of different topology, (), 756
[17] Umeo, H.; Morita, K.; Sugato, K., Deterministic one-way simulation of two-way real-time cellular automata and its related problems, Information processing lett., 14, 158, (1982) · Zbl 0488.68041
[18] Wolfram, S., Statistical mechanics of cellular automata, Rev. mod. phys., 55, 601, (1983) · Zbl 1174.82319
[19] D. Gordon, On the computational power of totalistic cellular automata, manuscript. · Zbl 0627.68049
[20] Culik, K.; Karhumäki, J., On totalistic systolic networks, Information processing lett., 26, 231, (1987/1988) · Zbl 0654.68058
[21] Berlekamp, E.R.; Conway, J.H.; Guy, R.K.; Gardner, M., Wheels, life and other mathematical amusements, (), (1983), Freeman San Francisco, ch. 25 · Zbl 0537.00002
[22] Wolfram, S., Twenty problems in the theory of cellular automata, Physica scripta, T9, 170, (1985) · Zbl 0966.68517
[23] Sutner, K., The computational complexity of cellular automata, (), 451 · Zbl 0756.68081
[24] Gutowitz, H.A., A hierarchical classification of cellular automata, Physica D, 45, 136-156, (1990), these Proceedings · Zbl 0729.68056
[25] Gutowitz, H.A.; Victor, J.D.; Knight, B.W., Local structure theory of cellular automata, Physica D, 28, 18, (1987) · Zbl 0634.92022
[26] Bays, C., Classification of semitotalistic cellular automata in three dimensions, Complex systems, 2, 235, (1988) · Zbl 0657.68055
[27] Gilman, R., Classes of linear automata, Ergodic theor. dynam. systems, 7, 105, (1987) · Zbl 0588.68029
[28] Gilman, R., Periodic behavior of linear automata, (), 216
[29] Culik, K.; Pachl, J.; Yu, S., On the limit sets of cellular automata, SIAM J. computing, 18, 831, (1989) · Zbl 0691.68060
[30] Sutner, K., A note on culik-yu classes, Complex systems, 3, 107, (1989) · Zbl 0732.68082
[31] Rogers, H., Theory of recursive functions and effective computability, (1987), MIT Press Cambridge, MA · Zbl 0183.01401
[32] Wolfram, S., Computation theory of cellular automata, Commun. math. phys., 96, 15, (1984) · Zbl 0587.68050
[33] Harrison, M.A., Introduction to formal language theory, (1978), Addison-Wesley Reading, MA · Zbl 0411.68058
[34] Cole, S.N., Real-time computation by n-dimensional iterative arrays of finite-state machines, IEEE trans. comp., C18, 4, 349, (1969) · Zbl 0172.20804
[35] Smith, A.R., Real-time language recognition by one-dimensional cellular automata, J. computer system sci., 6, 233, (1972) · Zbl 0268.68044
[36] Culik, K.; Yu, S., Iterative tree automata, Theor. computer sci., 32, 227, (1984) · Zbl 0544.68055
[37] Yu, S., On systolic automata, ()
[38] K. Culik II and S. Yu, Cellular automata, ωω-regular sets, and sofic systems, Discrete Appl. Math., to appear. · Zbl 0743.68085
[39] Hurd, L.P., The application of formal language theory to the dynamical behavior of cellular automata, ()
[40] Weiss, B., Subshifts of finite type and sofic systems, Monatsh. math., 77, 462, (1973) · Zbl 0285.28021
[41] Beauquier, D., Ensembles reconnaissables de mots bi-infinis limite et déterminisme, (), 28 · Zbl 0613.68031
[42] Nivat, M.; Perrin, D., Ensembles reconnaissables de mots bi-infinis, (), 47
[43] Berstel, J., Transductions and context-free languages, (1979), Teubner Stuttgart · Zbl 0424.68040
[44] Nivat, M.; Perrin, D., Ensembles reconnaisables de mots bi-infinis, Can. J. math., 39, 513, (1986)
[45] Nivat, M., Sur LES ensembles de mots infinis engendrés par une grammaire algébrique, RAIRO informatique théorique, 12, 259, (1978) · Zbl 0387.68050
[46] Restivo, A., Finitely generated sofic systems, () · Zbl 0688.68076
[47] Culik, K.; Hurd, L.P.; Yu, S., Formal languages and global cellular automaton behavior, Physica D, 45, 396-403, (1990), these Proceedings · Zbl 0729.68053
[48] Lind, D., Applications of ergodic theory and sofic systems to cellular automata, Physica D, 10, 36, (1984) · Zbl 0562.68038
[49] M. Hurley, Attractors in cellular automata, Ergodic Theor. Dynam. Systems, to appear.
[50] M. Hurley, Ergodic aspects of cellular automata, to appear. · Zbl 0695.58019
[51] Hurd, L.P., The non-wandering set of a CA map, Complex systems, 2, 549, (1988) · Zbl 0667.68067
[52] Conley, C., Isolated invariant sets and the Morse index, () · Zbl 0397.34056
[53] L.P. Hurd, Recursive cellular automata invariant sets, Complex Systems, to appear. · Zbl 0722.68083
[54] L.P. Hurd, Non-recursive cellular automata invariant sets, Complex Systems, to appear. · Zbl 0722.68083
[55] Walters, P., An introduction to ergodic theory, (1982), Springer Berlin · Zbl 0475.28009
[56] Podkolzin, A.S., On the behavior of homogeneous structures, Problemy kibernetiky, 31, 133, (1976) · Zbl 0417.68037
[57] Berger, R., The undecidability of the domino problem, Mem. am. math. soc., 66, (1966) · Zbl 0199.30802
[58] Robinson, R.M., Undecidability and nonperiodicity of tilings of the plane, Inventiones math., 12, 177, (1967) · Zbl 0197.46801
[59] J. Kari, The nilpotency problem of one-dimensional cellular automata, to appear. · Zbl 0761.68067
[60] Moore, E.F., Machine models of self-reproduction, (), 17
[61] Myhill, J., The converse to Moore’s garden-of-Eden theorem, (), 685 · Zbl 0126.32501
[62] S. Amoroso and Y.N. Patt, Decision Procedures for Surjectivity and Injectivity of Parallel Maps for Tessellation Structures. · Zbl 0263.94019
[63] Kari, J., Decision problems concerning cellular automata, ()
[64] J. Kari, Reversibility and surjectivity problems of cellular automata, submitted to J. Computer System Sci. · Zbl 0802.68090
[65] Richardson, D., Tessellation with local transformations, J. computer system sci., 6, 373, (1972) · Zbl 0246.94037
[66] Maruoka, A.; Kimura, M., Injectivity and surjectivity of parallel maps for cellular automata, J. computer system sci., 18, 47, (1979) · Zbl 0411.68047
[67] Toffoli, T., Computation and construction universality of reversible automata, J. computer system sci., 15, 213, (1977) · Zbl 0364.94085
[68] Culik, K., On invertible cellular automata, Complex systems, 1, 1035, (1987) · Zbl 0657.68053
[69] Dube, S., An investigation of cellular automata, ()
[70] Green, F., NP-complete problems in cellular automata, Complex systems, 1, 453, (1987) · Zbl 0648.68067
[71] K. Sutner, The complexity of finite cellular automata, manuscript in preparation. · Zbl 0827.68078
[72] J. Kari, Rice’s theorem for limit sets of cellular automata, submitted to Theor. Computer Sci. · Zbl 0824.68078
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.