# Recognizable picture languages and domino tiling

- Authors
- Journal
- Theoretical Computer Science 0304-3975
- Publisher
- Elsevier
- Publication Date
- Volume
- 178
- Identifiers
- DOI: 10.1016/s0304-3975(96)00283-6

## Abstract

Abstract In [2], Giammarresi and Restivo define the notion of local picture languages by giving a set of authorized 2 × 2 tiles over ∑ ∪ {#} where # is a boundary symbol which surrounds the pictures. Then they define the class of recognizable picture languages as the set of languages which can be obtained by projection of a local one. This class is of interest since it admits several quite different characterizations [3]. Here, we define the hv-local picture languages where 2 × 2 tiles are replaced by horizontal and vertical dominoes. So the horizontal and the vertical scanning can be done separately. However, we prove that every recognizable picture language can be obtained as a projection of a hv-local language.

## There are no comments yet on this publication. Be the first to share your thoughts.