Paper Info
Title
Polyomino tilings, cellular automata and codicity
Abstract
As usual, a 4-connex finite part of Z 2 is called a polyomino. Recognizing whether a given polyomino can be tiled by translated copies of tiles taken from a given family of polyominoes is obviously decidable. On the contrary, deciding whether a given set of polyominoes is a code has been shown to be undecidable (Beauquier and Nivat, 1993). In this paper, we define various classes of codes and study the complexity of tiling recognition for these classes and their mutual relations. Specially, we study the class of polyominoe families, which we call neighbourhood codes, which generate tilings which are recognizable by cellular automata using only neighbourhood relations. We prove that there exist codes which are not neighbourhood codes, and we give an example of such a code.
Year
DOI
Venue
1995
10.1016/0304-3975(94)00201-S
Theor. Comput. Sci.
Keywords
DocType
Volume
cellular automaton,Polyomino tilings
Journal
147
Issue
ISSN
Citations 
1-2
Theoretical Computer Science
20
PageRank 
References 
Authors
1.76
3
2
Name
Order
Citations
PageRank
Philippe Aigrain129546.15
Dani&#232/le Beauquier2201.76