Recognizable picture languages and polyominoes

Risultato della ricerca: Conference contribution

5 Citazioni (Scopus)

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.
Lingua originaleEnglish
Titolo della pubblicazione ospiteAlgebraic Informatics
Pagine160-171
Numero di pagine12
Stato di pubblicazionePublished - 2007

Serie di pubblicazioni

NomeLECTURE NOTES IN COMPUTER SCIENCE

All Science Journal Classification (ASJC) codes

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1700???

Fingerprint

Entra nei temi di ricerca di 'Recognizable picture languages and polyominoes'. Insieme formano una fingerprint unica.

Cita questo