RECOGNIZABLE PICTURE LANGUAGES AND DOMINO TILING

In [2], Giammarresi and Restive define the notion of local picture lan guages by giving a set of authorized 2 x 2 tiles over Sigma boolean OR {#} where # is a boundary symbol which surrounds the pictures. Then th ey define the class of recognizable picture languages as the set of la nguages which can be obtained by projection of a local one. This class is of interest since it admits several quite different characterizati ons [3]. Here, we define the hv-local picture languages where 2 x 2 ti les are replaced by horizontal and vertical dominoes. So the horizonta l and the vertical scanning can be done separately. However, we prove that every recognizable picture language can be obtained as a projecti on of a hv-local language.