Affordable Access

Publisher Website

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.