We consider some problems concerning two relevant classes of two-dimensional languages, i.e., the tiling recognizable languages, and the 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
On the tiling recognizability of various classes of convex polyominoes / F. De Carli; A. Frosini; S. Rinaldi; L. Vuillon. - In: ANNALS OF COMBINATORICS. - ISSN 0218-0006. - STAMPA. - 13 - issue 2:(2009), pp. 169-191. [10.1007/s00026-009-0018-9]
On the tiling recognizability of various classes of convex polyominoes
FROSINI, ANDREA;
2009
Abstract
We consider some problems concerning two relevant classes of two-dimensional languages, i.e., the tiling recognizable languages, and the 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-finiteI documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.