Strip tiling and regular grammars.pdf

[7] D. Klarner and J. Pollack. Domino tilings of rectangles with xed width. DiscreteMathematics, 32:45{52, 1980.[8] E. H. Lieb. Exactly soluble models. Physica, 73:226{236, 1974.[9] W. R. Marshall. Packing rectangles with congruent polyominoes. Journal of Combina-torial Theory, series A, 77:181{192, 1997.[10] D. G. Rogers and S. Zaks. Combinatorial proofs of recurrence relations for matchingsin rectangular grids. Private communication.[11] M. P. Schutzenberger. Context-free language and pushdown automata. Informationand Control, 6:246{264, 1963.[12] R. P. Stanley. On dimer coverings of rectangles of xed width. Discrete Applied Math-ematics, 12:81{87, 1985.[13] H. N. V. Temperley and M. E. Fisher. Dimer problem in statistical mechanics, an exactresult. Philosophical Magazine, 6:1061{1063, 1961.[14] W. J. Woan, D. Rogers, and L. Shapiro. The catalan numbers, the Lebesque integraland 4n2. American Mathematical Monthly (to appear). 15 5 Concluding remarksWe think that our approach can be useful in several ways to anyone interested in tilingproblems. First of all because it proposes an automatic way of solving medium-sized problemsin a constructive manner. Once the grammar for the problem has been determined, thereare some simple programs able to generate all the tilings of a p n-strip (i.e., all the wordsof length n belonging to the language). It is also possible to derive procedures that generatea random tiling in a uniform way and in linear time; this is true for any regular language.Moreover, our method proposes a systematic way of approaching some more dicultproblems. The reader is referred to Fig. 12 in Marshalls paper [9] for an example of howconstructive arguments can be used for obtaining some negative results.We wish to point out that a systematic study of our programs complexity could be veryuseful in deciding whether or not a specic problem can be solved by computer. As far aswe know, our method represents the rst attempt to furnish a systematic appro