𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Strip tiling and regular grammars

✍ Scribed by Donatella Merlini; Renzo Sprugnoli; M.Cecilia Verri

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
320 KB
Volume
242
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

We study the problem of tiling a rectangular p Γ— n-strip (p ∈ N ΓΏxed, n ∈ N) with pieces, i.e., sets of simply connected cells. Some well-known examples are strip tilings with dimers (dominoes) and=or monomers. We prove, in a constructive way, that every tiling problem is equivalent to a regular grammar, that is, the set of possible tilings constitutes a regular language. We propose a straightforward algorithm to transform the tiling problem into its corresponding grammar. By means of some standard methods, we are then able to obtain some counting generating functions that are rational. We go on to give some examples of our method and indicate some of its applications to a number of problems treated in current literature.

πŸ“œ SIMILAR VOLUMES

Tilings: recursivity and regularity
Tilings: recursivity and regularity
✍ Julien Cervelle; Bruno Durand πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 279 KB

We establish a ΓΏrst step towards a "Rice theorem" for tilings: for non-trivial sets, it is undecidable to know whether two di erent tile sets produce the same tilings of the plane. Then, we study quasiperiodicity functions associated with tilings. This function is a way to measure the regularity of

Tiling Rectangles and Half Strips with C
Tiling Rectangles and Half Strips with Congruent Polyominoes
✍ Michael Reid πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 322 KB

In the second edition of Golomb's classic ``Polyominoes'' [9], several infinite families of rectifiable polyominoes are given, but only nine sporadic examples are known. Curiously, two of these sporadic examples are related by a 2\_1 affine transformation (Fig. 1). This led us to consider the image