Others have studied the following question: given a set of words $w_1,w_2,\dots \in \Sigma^*$, find a regular grammar (or a context-free grammar) that generates all of those words, is "natural" in some sense, and is as small as possible. In the special case where we have a single word $w \in \Sigma^*$, if the grammar generates exactly the word $w$, we can think of this as a compression algorithm that compresses the word $w$ to the grammar produced by this inference algorithm. Of course, each word is a one-dimensional sequence of symbols.
Now consider a two-dimensional array of symbols, say an array $A[1\ldots m, 1\ldots n]$ where each $A[i,j] \in \Sigma$. Is there any corresponding algorithm that could be used to find a grammar of some sort that generates $A$? Could this be used as a compression algorithm for compressing images, i.e., one that compresses a two-dimensional image to its corresponding grammar?
I'm not even sure what kind of grammar would be suitable. Is there an analog of regular or context-free grammars that generates a two-dimensional output instead of a one-dimensional output? I've done some searching, and haven't found anything obvious.
Of course we could linearize the image, by concatenating the rows of the array, to get a one-dimensional sequence, and then apply any of the above techniques -- but this does not preserve locality. In other words, elements that are vertically adjacent will no longer be near each other after this transformation. So this transformation does not seem useful.
Perhaps we could build a quad-tree over the array and then consider tree automata over that quad-tree? Is there a grammar inference algorithm for such tree automata over quad-trees?
Alternatively, it seems like there might be a natural extension of context-free grammars to two-dimensional output: just make the right-hand side of each rule be a two-dimensional array of terminals and non-terminals of arbitrary size, and then apply the obvious generation algorithm. Do such grammars have a standard name? Is there a grammar inference algorithm for such grammars?