Geodesic
Estimating the Size of Context-Free Tiling Languages
Canadian journal of mathematics, Tome 39 (1987) no. 6, pp. 1413-1433

Voir la notice de l'article provenant de la source Cambridge University Press

The problem of counting polyominoes motivates this paper. We will develop a general question for study that has counting polyominoes as a special case. We generalize in two ways. Polyominoes are shapes on the tiling made of square tiles. We will consider shapes on other tilings. The set of all polyominoes can be generated by a context-free array grammar, but the size of this set is estimated by counting the words of certain subsets and supersets that are generated by more convenient grammars. Our general question is the problem of counting the words of a context-free array language on a periodic tiling.Counting polyominoes is a difficult problem that has not been completely solved yet. There are various techniques for roughly estimating the number of polyominoes of a given size. We will extend some of these techniques to our general question. 
Holladay, Kenneth. Estimating the Size of Context-Free Tiling Languages. Canadian journal of mathematics, Tome 39 (1987) no. 6, pp. 1413-1433. doi: 10.4153/CJM-1987-066-4
@article{10_4153_CJM_1987_066_4,
     author = {Holladay, Kenneth},
     title = {Estimating the {Size} of {Context-Free} {Tiling} {Languages}},
     journal = {Canadian journal of mathematics},
     pages = {1413--1433},
     year = {1987},
     volume = {39},
     number = {6},
     doi = {10.4153/CJM-1987-066-4},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1987-066-4/}
}
TY  - JOUR
AU  - Holladay, Kenneth
TI  - Estimating the Size of Context-Free Tiling Languages
JO  - Canadian journal of mathematics
PY  - 1987
SP  - 1413
EP  - 1433
VL  - 39
IS  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1987-066-4/
DO  - 10.4153/CJM-1987-066-4
ID  - 10_4153_CJM_1987_066_4
ER  - 
%0 Journal Article
%A Holladay, Kenneth
%T Estimating the Size of Context-Free Tiling Languages
%J Canadian journal of mathematics
%D 1987
%P 1413-1433
%V 39
%N 6
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1987-066-4/
%R 10.4153/CJM-1987-066-4
%F 10_4153_CJM_1987_066_4

[1] 1. Bourbaki, N., Algebra I, (Addison-Wesley, Reading, 1973), 532. Google Scholar

[2] 2. Cook, C. R. and Wang, P. S. P., A Chomsky hierarchy of isotonic array grammars and languages, Computer Graphics and Image Processing, Vol. 8, (1978), 144–152. Google Scholar

[3] 3. Gr¨nbaum, B. and Shephard, G. C., The eight-one types of isohedral tilings in the plane, Math. Proc. Camb. Phil. Soc. 82 (1977), 177–196. Google Scholar

[4] 4. Gr¨nbaum, B. and Shephard, G. C., Isohedral tilings of the plane by polygons, Comment. Math. Helvetici 53 (1978), 542–571. Google Scholar

[5] 5. Hall, M., Combinatorial theory, (Blaisdell, Waltham, 1967), 22. Google Scholar

[6] 6. Harrison, M. A., Introduction to formal language theory, (Addison-Wesley, Reading, 1978), 101. Google Scholar

[7] 7. Holladay, K. W., On some classes of context-free array grammars, Proc. 13 th S.E. Conf. on Comb., Graph Theory and Computing, Boca Raton, Feb. 15-19, 1982, Congressus numerantium 36, (1982), 325–332. Google Scholar

[8] 8. Klarner, D. A., Cell growth problems, Can. J. Math. 19 (1967), 851–863. Google Scholar

[9] 9. Klarner, D. A. and Rivest, R. L., A procedure for improving the upper bowidfor the number ofn-ominoes, Can. J. Math. 25 (1973), 585–602. Google Scholar

[10] 10. Rosenfeld, A., Isotonic grammars, parallel grammars and picture grammars, in Machine intelligence 6, (Univ. of Edinburgh Press, Edinburgh, 1971), 281–294. Google Scholar

[11] 11. Rosenfeld, A., Picture languages, (Academic Press, New York 1979). Google Scholar

Cité par Sources :