We consider some problems relative to two relevant classes of two-dimensional languages, i.e., the tiling recognizable languages (abbreviated by TS), and the local languages, (abbreviated by LOC), 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. We then investigate some decidability/undecidability properties of TS and LOC.
De Carli, F., Frosini, A., Rinaldi, S., Sorbi, A. (2005). Some remarks on tiling recognizable languages. PURE MATHEMATICS AND APPLICATIONS, 16(1-2), 69-80.
Some remarks on tiling recognizable languages
RINALDI, SIMONE;SORBI, ANDREA
2005-01-01
Abstract
We consider some problems relative to two relevant classes of two-dimensional languages, i.e., the tiling recognizable languages (abbreviated by TS), and the local languages, (abbreviated by LOC), 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. We then investigate some decidability/undecidability properties of TS and LOC.
| File | Dimensione | Formato | |
|---|---|---|---|
|
tiling-recognizable.pdf
non disponibili
Descrizione: Articolo
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
6.27 MB
Formato
Adobe PDF
|
6.27 MB | 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/506545