<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 2" %>
On the Tiling System Recognizability of Various Classes of Convex Polyominoes
F. De Carli1, A. Frosini1, S. Rinaldi1, and L. Vuillon2
1Dipartimento di Scienze Matematiche e Informatiche, Universit\`a di Siena, Pian dei Mantellini, 44 53100, Siena, Italy
{frosini, rinaldi}@unisi.it
2Laboratoire de Math\'ematiques, UMR 5127 CNRS, Universit\'e de Savoie, 73376 Le Bourget du Lac, France
Annals of Combinatorics 13 (2) pp.169-191 June, 2009
AMS Subject Classification: 52C45, 68R15, 68R05
We consider some problems concerning two relevant classes of two-dimensional languages, i.e., the {\em tiling recognizable languages}, and the {\em local languages}, recently introduced by Giammarresi and Restivo and already extensively studied. We show that various classes of convex and column-convex polyominoes can be naturally represented as two-dimensional words of tiling recognizable languages. Moreover, we investigate the nature of the generating function of a tiling recognizable language, providing evidence that such a generating function need not be D-finite.
Keywords: convex polyominoes, two-dimensional languages, tiling systems, generating functions


1. D. Beauquier and M. Nivat, Tiling the plane with one tile, In: Proc. of The 6th Annual Symposium on Computational geometry (SGC'90), ACM press, Berkeley, (1990) pp. 128-–138.

2. M. Bousquet-M´elou, A method for the enumeration of various classes of column-convex polygons, Discrete Math. 154 (1-3) (1996) 1-–25.

3. M. Bousquet-M´elou and M. Petkovsek, Walks conned in a quadrant are not always D- nite, Theoret. Comput. Sci. 307 (2) (2003) 257-–276.

4. M. Bousquet-M´elou and A. Rechnitzer, The site-perimeter of bargraphs, Adv. Appl. Math. 31 (1) (2003) 86-–112.

5. G. Castiglione, A. Frosini, E. Munarini, A. Restivo, and S. Rinaldi, Enumeration of Lconvex polyominoes II. Bijection and area, In: 17th Formal Power Series and Algebraic Combinatorics, Taormina, Italy, 2005.

6. G. Castiglione, A. Frosini, A. Restivo, and S. Rinaldi, A tomographical characterization of L-convex polyominoes, In: Proceedings of Discrete Geometry for Computer Imagery 12th International Conference, Lecture Notes in Comput. Sci., Vol. 3429, Springer, Berlin, (2005) pp. 115-–125.

7. G. Castiglione, A. Frosini, A. Restivo, and S. Rinaldi, Enumeration of L-convex polyominoes by rows and columns, Theoret. Comput. Sci. 347 (1-2) (2005) 336–-352.

8. G. Castiglione and A. Restivo, Reconstruction of L-convex Polyominoes, Electron. Notes Discrete Math. 12 (2003) 290-–301.

9. G. Castiglione and A. Restivo, Ordering and convex polyominoes, In: Proceedings of Machines, Computations, and Universality, Lecture Notes in Comput. Sci., Vol. 3354, Springer-Verlag, Berlin, (2005) pp. 128-–139.

10. N. Chomsky and M.P. Sch¨utzenberger, The algebraic theory of context-free languages, In: Computer Programming and Formal Systems, P. Braffort and D. Hirschberg, Eds., North-Holland, Amsterdam, (1963) pp. 118-–161.

11. M. Delest and X. Viennot, Algebraic languages and polyominoes enumeration, Theoret. Comput. Sci. 34 (1-2) (1984) 169–-206.

12. P. Flajolet, Analytic models and ambiguity of context-free languages, Theoret. Comput. Sci. 49 (2-3) (1987) 283-–309.

13. M. Gardner, Mathematical games, Scientic American, (1958) September 182–192; November 136-–142.

14. P.G. de Gennes, Scaling Concepts in Polymers Physics, Cornell University Press, New York, 1979.

15. D. Giammarresi and A. Restivo, Two-dimensional languages, In: Handbook of Formal Languages, Vol. 3, A. Salomaa and G. Rozenberg, Eds., Springer, Berlin, (1997) pp. 215–- 267.

16. D. Giammarresi, A. Restivo, S. Seibert, and W. Thomas, Monadic second-order logic over rectangular pictures and recognizability by tiling system, Inform. and Comput. 125 (1) (1996) 32-–45.

17. S.W. Golomb, Polyominoes: Puzzles, Patterns, Problems, and Packings, 2nd Ed., Princeton Academic Press, Princeton, 1996.

18. S.W. Golomb, Checker boards and polyominoes, Amer. Math. Monthly 61 (10) (1954) 675-–682.

19. A.J. Guttmann, Indicators of solvability for lattice models, Discrete Math. 217 (1-3) (2000) 167–-189.

20. K. Inoue and I. Takanami, A survey of two-dimensional automata theory, In: Lecture Notes in Comput. Sci., Vol. 381, Springer, Berlin, (1989) pp. 72–-91.

21. K. Inoue and A. Nakamura, Some properties on two-dimensional on-line tessellation acceptors, Inform. Sci. 13 (2) (1977) 95–-121.

22. K. Inoue and I. Takanami, A characterization of recognizable picture languages, In: Lecture Notes in Comput. Sci., Vol. 654, Springer-Verlag, Berlin, (1992) pp. 133-–143.

23. V. Privman and N.M. Svrakic, Difference equations in statistical mechanics. II. Solid-onsolid models in two dimensions, J. Statist. Phys. 51 (5-6) (1988) 1111-–1126.

24. A. Rechnitzer, Haruspicy and anisotropic generating functions, Adv. Appl. Math. 30 (1-2) (2003) 228-–257.

25. A. Rechnitzer, Haruspicy 2: the self-avoiding polygon generating function is not D-finite, J. Combin. Theory Ser. A 113 (3) (2006) 520–-546.

26. R.P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999.