[en] Partially ordered sets labeled with k labels (k-posets) and their homomorphisms are examined. We give a representation of directed graphs by k-posets; this provides a new proof of the universality of the homomorphism order of k-posets. This universal order is a distributive lattice. We investigate some other properties, namely the infinite distributivity, the computation of infinite suprema and infima, and the complexity of certain decision problems involving the homomorphism order of k-posets. Sublattices are also examined.
Disciplines :
Mathématiques
Identifiants :
UNILU:UL-ARTICLE-2011-256
Auteur, co-auteur :
Kwuida, Léonard; Zurich University of Applied Sciences, Switzerland
LEHTONEN, Erkko ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Langue du document :
Anglais
Titre :
On the homomorphism order of labeled posets
Date de publication/diffusion :
2011
Titre du périodique :
Order: A Journal on the Theory of Ordered Sets and its Applications
