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.
2007
Settore INF/01 - Informatica
978-3-540-75413-8
978-3-540-75414-5
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].
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/429757
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 3
social impact