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.

F., D.C., A., F., Rinaldi, S., & L., V. (2009). On the Tiling System Recognizability of Various Classes of Convex Polyominoes. ANNALS OF COMBINATORICS, 13(2), 169-191 [10.1007/s00026-009-0018-9].

On the Tiling System Recognizability of Various Classes of Convex Polyominoes

RINALDI, SIMONE;
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-finite.
F., D.C., A., F., Rinaldi, S., & L., V. (2009). On the Tiling System Recognizability of Various Classes of Convex Polyominoes. ANNALS OF COMBINATORICS, 13(2), 169-191 [10.1007/s00026-009-0018-9].
File in questo prodotto:
File Dimensione Formato  
tiling_rec.pdf

non disponibili

Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 336.71 kB
Formato Adobe PDF
336.71 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11365/10580
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo