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-01-01
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.
| 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.
https://hdl.handle.net/11365/10580
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo