Salta al contenuto principale
Passa alla visualizzazione normale.

GIUSEPPA CASTIGLIONE

Highmann's Theorem on Discrete Sets

  • Autori: Burderi, F.; Castiglione, G.; Restivo, A.
  • Anno di pubblicazione: 2006
  • Tipologia: Articolo in rivista (Articolo in rivista)
  • Parole Chiave: Discrete sets, polyominoes and L-convex polyominoes; subpicture order and wellpartial-ordering.

Abstract

In this paper we investigate properties of different classes of discrete sets with respect to the partial-order of subpicture. In particular we take in consideration the classes of convex polyominoes and L-convex polyominoes. In the first part of the paper we study closure properties of these classes with respect the order and we give a new characterization of L-convex polyominoes. In the second part we pose the question to extend Higman’s theoremto discrete sets. We give a negative answer in the general case and we prove that the set of L-convex polyominoes is well-partially-ordered by using a representation of L-convex polyominoes in terms of words of a regular language.