A Kleene Theorem for Regular Picture Languages
We consider the class of regular picture languages, which is the two-dimensional analog to the well-known class of regular (word) languages as defined by regular expressions. We present an automaton model that characterizes the class of regular picture languages, similar to the famous Kleene theorem that characterizes the class of regular picture languages by non-deterministic finite state automata. The two concatenations (called "row"- and "column"-concatenation) for picture languages are partial because they require matching height or width, respectively. However, we show that for the definition of regular picture languages, the partialness of the concatenations is irrelevant in the sense that every regular expression can be converted into a regular expression during whose evaluation no picture gets discarded because of that partialness. We conclude that for every regular picture languages, its "front" (i.e., the set of top rows of its pictures) is a regular word language.