Abstract
In dynamical systems such as cellular automata and iterated maps, it is often useful to look at a language or set of symbol sequences produced by the system. There are well-established classification schemes, such as the Chomsky hierarchy, with which we can measure the complexity of these sets of sequences, and thus the complexity of the systems which produce them. In this paper, we look at the first few levels of a hierarchy of complexity for two-or-more-dimensional patterns. We show that several definitions of “regular language” or “local rule” that are equivalent in d=1 lead to distinct classes in d≥2. We explore the closure properties and computational complexity of these classes, including undecidability and L, NL, and NP-completeness results. We apply these classes to cellular automata, in particular to their sets of fixed and periodic points, finite-time images, and limit sets. We show that it is undecidable whether a CA in d≥2 has a periodic point of a given period, and that certain “local lattice languages” are not finite-time images or limit sets of any CA. We also show that the entropy of a d-dimensional CA's finite-time image cannot decrease faster than t −d unless it maps every initial condition to a single homogeneous state.
Similar content being viewed by others
REFERENCES
R. Artuso, E. Aurell, and P. Cvitanović, Recycling strange sets, Nonlinearity 3:325 (1990).
F. Barahona, J. Phys. A: Math. Gen. 15:3241 (1982).
Y. Bargury and J. Makowsky, The expressive power of transitive closure and 2-way multihead automata, in Lecture Notes in Computer Science, Vol. 626 (Springer-Verlag, 1992), pp. 1–14.
R. J. Baxter, Exactly Solved Models in Statistical Mechanics (Academic Press, London, 1982).
R. Berger, The undecidability of the domino problem, Memoirs Amer. Math. Soc. 66:1–72 (1966).
M. Blum and C. Hewitt, Automata on a 2-dimensional tape, 8th IEEE Symp. on Switching and Automata Theory, pp. 155–160 (1967).
S. A. Cook, Linear time simulation of deterministic two-way pushdown automata, Proc. 1971 IFIP Congress, pp. 75–80.
W. Coy, Automata in labyrinths, in Lecture Notes in Computer Science, Vol. 56 (Springer-Verlag, 1977), pp. 65–71.
J. P. Crutchfield and K. Young, Computation at the onset of chaos, in Complexity, Entropy, and the Physics of Information, W. H. Zurek, ed. (Addison-Wesley, 1990).
J. P. Crutchfield, Unreconstructible at any radius, Physics Letters A 171:52–60 (1992).
S. Finch, Hard square entropy constant. http://www.mathsoft.com/asolve/constant/square/square.html.
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, San Francisco, 1979).
D. Giammarresi and A. Restivo, Recognizable picture languages, Int. J. of Pattern Recognition and Artificial Intelligence 6(2–3):241–256 (1992).
D. Giammarresi, A. Restivo, S. Seibert, and W. Thomas, Monadic second order logic over rectangular pictures and recognizability by tiling systems, Information and Computation 125(1):32–45 (1996).
D. Giammarresi and A. Restivo, Two-dimensional languages. To appear in Handbook of Formal Languages, G. Rosenberg and A. Salomaa, eds. (Springer-Verlag, 1996).
P. Goralcik, A. Goralcikova, and V. Koubek, Alternation with a pebble, Information Processing Letters 38(1):7–13 (1991).
R. Greenlaw, H. J. Hoover, and W. L. Russo, Limits to Parallel Computation: P-Completeness Theory (Oxford University Press, 1995).
B. Grünbaum and G. C. Shepard, Tilings and Patterns (W. H. Freeman, San Fiancisco, 1987).
V. Guillemin and A. Pollack, Differential Topology (Prentice-Hall, 1974).
See for instance Chap. 5 of J. Guckenheimer and P. Holmes, Nonlinear Oscillations, Dynamical Systems and Bifurcations of Vector Fields (Springer-Verlag, 1983).
Silas Haslam, A General History of Labyrinths (Vienna, 1888).
G. A. Hedlund, Endomorphisms and automorphisms of the shift dynamical system, Mathematical Systems Theory 3:320–375 (1969).
J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation (Addison-Wesley, 1979).
L. P. Hurd, Formal language characterization of cellular automaton limit sets, Complex Systems 1:69–80 (1987).
L. P. Hurd, Recursive cellular automata invariant sets, Complex Systems 4:119–129 (1990).
K. Inoue and A. Nakamura, Some properties of two-dimensional on-line tesselation acceptors, Information Sciences 13:95–121 (1977).
K. Inoue, A. Nakamura, and I. Takanami, A note on two-dimensional finite automata, Information Processing Letters 7(1):48–53 (1978).
K. Inoue and A. Nakamura, Two-dimensional finite automata and unacceptable functions, Int. J. Comput. Math. A 7:207–213 (1979).
K. Inoue and I. Takanami, A survey of two-dimensional automata theory, Information Sciences 55:99–121 (1991).
E. Jen, Global properties of cellular automata, Journal of Statistical Physics 43:219–242 (1986).
B. Kitchens and K. Schmidt, Periodic points, decidability, and Markov subgroups, in Lecture Notes in Mathematics, Vol. 1042, pp. 440–454 (Springer-Verlag, 1988).
D. Lind and B. Marcus, Symbolic Dynamics and Coding (Cambridge University Press, 1995).
A. Lindenmayer, Developmental systems without cellular interaction, their languages and grammars, Journal of Theoretical Biology 30:455–484 (1971).
K. Lindgren, Correlations and random information in cellular automata, Complex Systems 1:529–543 (1987).
K. Lindgren and M. G. Nordahl, Universal computation in simple one-dimensional cellular automata, Complex Systems 4:299–318 (1990).
K. Lindgren, C. Moore, and M. G. Nordahl, Complexity of two-dimensional patterns, J. Unpub. Res. 1:1–32 (1990).
A. de Luca and S. Varrichio, A positive pumping condition for regular sets, Bulletin of the ETACS 39:171–175 (1989).
J. Mikiesz, The global minimum of energy is not always a sum of local minima—a note on frustration, Journal of Statistical Physics 71:425–434 (1993).
D. L. Milgram, A region crossing problem for array-bounded automata, Information and Control 31:147–152 (1976).
S. Milošević, B. Stošić, and T. Stošić, Towards finding exact residual entropies of the Ising antiferromagnets, Physica A 157:899–906 (1989).
M. Minsky, Computation: Finite and Infinite Machines (Prentice-Hall, 1967).
B. Monien, Transformational methods and their application to complexity problems, Acta Informatica 6:95–108 (1976); and Corrigenda, 8:383–384 (1977).
C. Moore, Unpredictability and undecidability in dynamical systems, Phys. Rev. Lett. 64:2354–2357 (1990); and Nonlinearity 4:199–230 (1991).
M. G. Nordahl, Formal languages and finite cellular automata, Complex Systems 3:63–78 (1989).
A. Nakamura, Three-dimensional connected pictures are not recognizable by finite-state acceptors, Information Sciences 66:225–234 (1992).
G. Y. Onoda, P. J. Steinhardt, D. P. DiVincenzo, and J. E. S. Socolar, Growing perfect quasicrystals, Physical Review Letters 60:2653–2656 (1988).
N. Packard and S. Wolfram, Two-dimensional cellular automata, Journal of Statistical Physics 38:901–946 (1985).
C. H. Papadimitriou, Computational Complexity (Addison-Wesley, 1994).
R. J. Parikh, On context-free languages, Journal of the ACM 4:570–581 (1966).
R. M. Robinson, Undecidability and nonperiodicity of tilings of the plane, Inventiones Math. 12:177 (1971).
A. Rosenfeld, Picture Languages: Formal Models for Picture Recognition (Academic Press, 1979).
A. Salomaa and M. Soittola, Automata-Theoretic Aspects of Formal Power Series (Springer-Verlag, New York, 1978).
A. G. Schlijper, Tiling problems and undecidability in the cluster variation method, Journal of Statistical Physics 50:689–714 (1988).
J. D. Shore, M. Holzer, and J. P. Sethna, Logarithmically slow domain growth in nonrandomly frustrated systems: Ising models with competing interactions, Physical Review B 46:376–404 (1992).
M. Sipser, Halting space-bounded computations, Theoretical Computer Science 10:335–338 (1980).
A. Szepietowski, Two-dimensional on-line tesselation acceptors are not closed under complement, Information Sciences 64:115–120 (1992).
H. Wang, Proving theorems by pattern recognition II, Bell System Tech. J. 40:1–42 (1961).
B. Weiss, Subshifts of finite type and sofic systems, Monatsh. Math. 77:462 (1973).
S. Willson, On the ergodic theory of cellular automata, Mathematical Systems Theory 9:132–141 (1975).
S. Wolfram, Computation theory of cellular automata, Communications in Mathematical Physics 96:15–57 (1984).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Lindgren, K., Moore, C. & Nordahl, M. Complexity of Two-Dimensional Patterns. Journal of Statistical Physics 91, 909–951 (1998). https://doi.org/10.1023/A:1023027932419
Issue Date:
DOI: https://doi.org/10.1023/A:1023027932419