Higman's Theorem on Discrete Sets

Issue title: SPECIAL ISSUE MCU2004

Article type: Research Article

Authors: Burderi, Fabio | Castiglione, Giuseppa | Restivo, Antonio

Affiliations: Dipartimento di Matematica e Applicazioni Universitá di Palermo Via Archirafi 34, 90123 Palermo, Italy. E-mail: {burderi,giusi,restivo}@math.unipa.it

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 well-partial-ordering

Journal: Fundamenta Informaticae, vol. 74, no. 4, pp. 435-446, 2006