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.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.