In dynamical systems such as cellular automata and iterated maps, it is often useful to look at a {\it 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. <p> 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 \geq 2$. We explore the closure properties and computational complexity of these classes, including certain undecidability and {\bf NP}-completeness results. <p> 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 \geq 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.
