We consider the problem of recognizability of some classes of polyominoes in the theory of picture languages. In particular we focus our attention oil the problem posed by Matz of finding a non-recognizable picture language for which his technique for proving the non-recognizability of picture languages fails. We face the problem by studying the family of L-convex polyominoes and some closed families that are similar to the recognizable family of all polyominoes but result to be non-recognizable. Furthermore we prove that the family of L-convex polyominoes satisfies the necessary condition given by Matz for the recognizability and we conjecture that the family of L-convex polyominoes is non-recognizable.
Castiglione G., Vaglica R. (2007). Recognizable picture languages and polyominoes. In S. Bozapalidis, G. Rahonis (a cura di), Algebraic Informatics (pp. 160-171). Springer Verlag [10.1007/978-3-540-75414-5_10].
Recognizable picture languages and polyominoes
Castiglione G.
;Vaglica R.
2007-01-01
Abstract
We consider the problem of recognizability of some classes of polyominoes in the theory of picture languages. In particular we focus our attention oil the problem posed by Matz of finding a non-recognizable picture language for which his technique for proving the non-recognizability of picture languages fails. We face the problem by studying the family of L-convex polyominoes and some closed families that are similar to the recognizable family of all polyominoes but result to be non-recognizable. Furthermore we prove that the family of L-convex polyominoes satisfies the necessary condition given by Matz for the recognizability and we conjecture that the family of L-convex polyominoes is non-recognizable.File | Dimensione | Formato | |
---|---|---|---|
[12] cai2007.pdf
Solo gestori archvio
Tipologia:
Versione Editoriale
Dimensione
444.15 kB
Formato
Adobe PDF
|
444.15 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.