Higman's Theorem on Discrete Sets

• Autorzy: Burderi F. , Castiglione G. , Restivo A.
• Języki publikacji: EN

Abstrakty

EN

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 theorem to 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.

Słowa kluczowe

EN

discrete sets; polyominoes and L-convex polyominoes; subpicture order and wellpartial-ordering

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 74, nr 4
• Strony: 435--446
• Opis fizyczny: bibliogr. 17 poz.

Twórcy

autor

Burderi F.

autor

Castiglione G.

autor

Restivo A.

• Dipartimento di Matematica ed Applicazioni, University of Palermo, Via Archirafi 34, 90123 Palermo, Italy,

Bibliografia

• [1] Barcucci, E., Del Lungo, A., Nivat, M., Pinzani, R.:Reconstructing convex polyominoes from horizontal and vertical projections. Theoret. Comput. Sci. 155 (1996) 321-347.
• [2] Bousquet-Mélou, M.: A method for the enumeration of various classes of column-convex polygons. Discrete Math. 155 (1996) 1-25.
• [3] Castiglione, G., Restivo, A.: Reconstruction of L-convex Polyominoes. Electronic Notes in Discrete Math.12, Elsevier Science (2003).
• [4] Castiglione, G., Frosini, A., Restivo, A., Rinaldi, S.: Enumeration of L-convex Polyominoes by Rows and Columns, Dipartimento di Matematica e Applicazioni, Universitá degli Studi di Palermo, 347 (2005) 336-352.
• [5] Castiglione, G., Frosini, A., Restivo, A., Rinaldi, S.:Enumeration of L-convex Polyominoes, II. Bijection and area. Proceedings of 17-th FPSAC (2005), 531-541.
• [6] Castiglione, G., Frosini, A., Restivo, A., Rinaldi, S.: Tomographical Characterization of L-convex Polyominoes, accepted at: Discrete Geometry for Computer Imagery (DGCI 2005), Poitiers, France, April 13-15, 2005.
• [7] D'Alessandro, F., Varricchio, S.: Well quasi-orders on languages. Lecture Notes in Comp. Sci. 2710 (2003) 230-241.
• [8] Delest, M., Viennot, X. G.: Algebraic languages and polyominoes enumeration. Theor. Comp. Sci. 34 (1984) 169-206.
• [9] Ehrenfencht, A., Haussler, D., Rozenberg, G.: On regularity of context-free languages. Theoret. Comput. Sci.27 (1983) 311-332.
• [10] Finkel, A.: Une Généralisation des théorèmes de Higman et de Simon aux Mots Infinis. Theoret. Comput. Sci. 38 (1985) 137-142
• [11] Golomb, S.W.: Polyominoes. Scribner, New York (1965)
• [12] Higman, G.H.: Ordering by divisibility in abstract algebra. Proc. London Math. Soc. 2 (1952) 326-336
• [13] Kruskal, J.B.: Well-quasi-ordering, the Tree Theorem, and Vazsonyi's conjecture. Trans. Amer. Math. Soc. 95 (1960) 210-225
• [14] Kruskal, J.B.: The Theory of Well-Quasi-Ordering: A Frequently Discovered Concept. J. Combin. Theory Ser. A 13 (1972) 297-305
• [15] Kuba, A., Balogh, E.: Reconstruction of convex 2D discrete sets in polynomial time, Theoret. Comput. Sci. 283 (2002) 223-242.
• [16] Lothaire, M.: Combinatorics on Words. Encyclopedia of Mathematics and its Applications, 17, Addison-Wesley, Reading, MA, (1983)
• [17] Matz, O.: On piecewise testable, starfree, and recognizable picture languages. Foundations of Software Science and Computation Structures 1378 (1998).