Highmann's Theorem on Discrete Sets

Antonio Restivo, Fabio Burderi, Giuseppa Castiglione

Risultato della ricerca: Article

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.
Lingua originaleItalian
pagine (da-a)435-446
Numero di pagine12
RivistaFundamenta Informaticae
Volume74(4)
Stato di pubblicazionePublished - 2006

Cita questo

Highmann's Theorem on Discrete Sets. / Restivo, Antonio; Burderi, Fabio; Castiglione, Giuseppa.

In: Fundamenta Informaticae, Vol. 74(4), 2006, pag. 435-446.

Risultato della ricerca: Article

Restivo, A, Burderi, F & Castiglione, G 2006, 'Highmann's Theorem on Discrete Sets', Fundamenta Informaticae, vol. 74(4), pagg. 435-446.
Restivo A, Burderi F, Castiglione G. Highmann's Theorem on Discrete Sets. Fundamenta Informaticae. 2006;74(4):435-446.
Restivo, Antonio ; Burderi, Fabio ; Castiglione, Giuseppa. / Highmann's Theorem on Discrete Sets. In: Fundamenta Informaticae. 2006 ; Vol. 74(4). pagg. 435-446.
@article{d86a306f4040403486f17a05ecbe5e08,
title = "Highmann's Theorem on Discrete Sets",
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.",
keywords = "Discrete sets, polyominoes and L-convex polyominoes; subpicture order and wellpartial-ordering.",
author = "Antonio Restivo and Fabio Burderi and Giuseppa Castiglione",
year = "2006",
language = "Italian",
volume = "74(4)",
pages = "435--446",
journal = "Fundamenta Informaticae",
issn = "0169-2968",
publisher = "IOS Press",

}

TY - JOUR

T1 - Highmann's Theorem on Discrete Sets

AU - Restivo, Antonio

AU - Burderi, Fabio

AU - Castiglione, Giuseppa

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

KW - Discrete sets, 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 -

Accesso al documento