We study the problem of tiling a rectangular p x n-strip (p is an element of N fixed, n is an element of 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.

Strip Tiling and Regular Grammars / D. MERLINI; R. SPRUGNOLI; M. VERRI. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 242, Issue 1-2:(2000), pp. 109-124. [10.1016/S0304-3975(98)00204-7]

Strip Tiling and Regular Grammars

MERLINI, DONATELLA;SPRUGNOLI, RENZO;VERRI, MARIA CECILIA
2000

Abstract

We study the problem of tiling a rectangular p x n-strip (p is an element of N fixed, n is an element of 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.
2000
242, Issue 1-2
109
124
D. MERLINI; R. SPRUGNOLI; M. VERRI
File in questo prodotto:
File Dimensione Formato  
r7.pdf

Accesso chiuso

Tipologia: Versione finale referata (Postprint, Accepted manuscript)
Licenza: Tutti i diritti riservati
Dimensione 319.79 kB
Formato Adobe PDF
319.79 kB Adobe PDF   Richiedi una copia

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/307285
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 7
social impact