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 originale | English |
---|

Titolo della pubblicazione ospite | Algebraic Informatics |
---|

Pagine | 160-171 |
---|

Numero di pagine | 12 |
---|

Stato di pubblicazione | Published - 2007 |
---|

Nome | LECTURE NOTES IN COMPUTER SCIENCE |
---|

- ???subjectarea.asjc.2600.2614???
- ???subjectarea.asjc.1700.1700???