Doubling Convex Sets in Lattices: Characterizations and Recognition Algorithms

被引：0

作者：

Karell Bertet

Nathalie Caspard

机构：

[1] Université de la Rochelle,L3I Laboratoire d'Informatique et d'Imagerie Industrielle

[2] Université Paris 12,LACL Laboratoire d'Algorithmique, Complexité et Logique

[3] Val-de-Marne,undefined

来源：

Order | 2002年 / 19卷

关键词：

algorithm; arrow relations; doublings; lattice; poset; recognition;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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

引用

页码：181 / 207

页数：26

共 15 条

[1]

Blair C.(1984)Every finite distributive lattice is a set of stable matchings J. Combin. Theory (A) 37 353-356

[2]

Day A.(1970)A simple solution of the word problem for lattices Canad. Math. Bull. 13 253-254

[3]

Day A.(1977)Splitting lattices generate all lattices Algebra Universalis 7 163-170

[4]

Day A.(1979)Distributive lattices with finite projective covers Pacific J. Math. 81 45-59

[5]

Day A.(1979)Characterizations of finite lattices that are bounded-homomorphic images or sublattices of free lattices Canad. J. Math. 31 69-78

[6]

Day A.(1989)Doubling convex sets in lattices and a generalized semidistributivity condition Order 6 175-180

[7]

Nation J. B.(1992)Doubling constructions in lattice theory Canad. J. Math. 44 252-269

[8]

Tschanz S.(1994)Congruence normality: The characterization of the doubling class of convex sets Algebra Universalis 31 397-406

[9]

Day A.(1985)Covers in free lattices Trans. Amer. Math. Soc. 228 1-42

[10]

Day A.(1993)Generalizing semidistributivity Order 10 77-92

← 1 2 →