TY - JOUR
T1 - Highmann's Theorem on Discrete Sets
AU - Restivo, Antonio
AU - Castiglione, Giuseppa
AU - Burderi, Fabio
PY - 2006
Y1 - 2006
N2 - In this paper we investigate properties of different classes of discrete sets with respect tothe partial-order of subpicture. In particular we take in consideration the classes of convex polyominoesand L-convex polyominoes. In the first part of the paper we study closure properties of theseclasses with respect the order and we give a new characterization of L-convex polyominoes. In thesecond part we pose the question to extend Higman’s theoremto discrete sets. We give a negative answerin the general case and we prove that the set of L-convex polyominoes is well-partially-orderedby using a representation of L-convex polyominoes in terms of words of a regular language.
AB - In this paper we investigate properties of different classes of discrete sets with respect tothe partial-order of subpicture. In particular we take in consideration the classes of convex polyominoesand L-convex polyominoes. In the first part of the paper we study closure properties of theseclasses with respect the order and we give a new characterization of L-convex polyominoes. In thesecond part we pose the question to extend Higman’s theoremto discrete sets. We give a negative answerin the general case and we prove that the set of L-convex polyominoes is well-partially-orderedby using a representation of L-convex polyominoes in terms of words of a regular language.
KW - Discrete sets
KW - polyominoes and L-convex polyominoes; subpicture order and wellpartial-ordering.
KW - Discrete sets
KW - polyominoes and L-convex polyominoes; subpicture order and wellpartial-ordering.
UR - http://hdl.handle.net/10447/40019
M3 - Article
VL - 74(4)
SP - 435
EP - 446
JO - Fundamenta Informaticae
JF - Fundamenta Informaticae
SN - 0169-2968
ER -