Extending Formal Languages Hierarchies to Higher Dimensions

n a formula expressing how a specific picture language can be obtained from elementary languages by regular operations. Different families of languages can be defined, depending on the choice of operations allowed to be used in the expression. Regarding finite-state machines, several models of them have been designed to recognize picture languages ([3]). As to concerns sequential models, many researches have been devoted to four-way finite automata (4FA), which are the natural generalization of two-way finite automata over strings. Actually these models have a weak computational power, since they operate, more or less explicitely, on some linear coding of a picture and do not capture its true bidimensional features. A more interesting approach considers cellular automata and introduces, in particular, the notion of two-dimensional on-line tessellation automaton (2-OTA). This model can be easily identified to a conventional automaton when restricted to o