Doubling convex sets in lattices : characterizations and recognition algorithms

Karell Bertet*, LIAFA
Nathalie Caspard, CERMSEM

Résumé. Nous caractérisons les treillis obtenus à partir d'un autre treillis par la duplication d'un ensemble convexe et connexe. Ceci amène à une caractérisation de la classe CN de tous les treillis obtenus par des duplications d'ensembles convexes à partir du treillis à deux éléments et nous dérivons de cette caractérisation un algorithme efficace de reconnaissance. Cet algorithme peut directement être appliqué à la reconnaissance de treillis dans des sous-classes de CN définies en donnant des contraintes supplémentaires sur les ensembles convexes utilisés dans les duplications.
Mots clés : Algorithme, duplications, ensembles ordonnés, relations flèche, treillis.

Abstract. We characterize lattices obtained from another lattice by a doubling of a connected and convex set. This gives rise to a characterization of the class CN of lattices obtained by doublings of connected and convex sets starting from the two-element lattice, and we derive from this characterization result an efficient recognition algorithm. This algorithm can directly be applied to the recognition of lattices in subclasses of CN defined by giving some additionnal constraints on the convex sets used in the doublings.
Keywords : Algorithm, arrow relations, doubling, poset, lattice.

JEL Classification : C60.

*LIAFA, Université Paris 7, 2 Place Jussieu, 75251 Paris Cedex 05, France.