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.

Statistics

Seen <100 times
0 Comments

More articles like this

A characterization of recognizable picture languag...

on Theoretical Computer Science Jan 01, 1999

Tiling pictures of the plane with dominoes

on Discrete Mathematics Jan 01, 1997

A computational model for tiling recognizable two-...

on Theoretical Computer Science Jan 01, 2009
More articles like this..