Doubling convex sets in lattices: Characterizations and recognition algorithms (Q698449)

The doubling of an interval \(I\) in a lattice \(L\) consists in replacing in \(L\) the interval \(I\) by the direct product \(I\times \{0,1\}\) and considering the naturally induced order. This construction was introduced by A. Day (1970). This construction may be applied to convex sets, obtaining the class CN (congruence normal) of all the lattices attainable from \(\{0,1\}\) by a finite sequence of doubling by using convex sets. There are several characterizations of this class, e.g. the one given by W. Geyer: a finite lattice \(L\) is in CN if there are no proper quotients \(a/b\) and \(c/d\) in \(L\) which are comparable and weakly projective to each other. The recognition algorithm that one derives from Geyer's constructive characterization has an exponential time complexity. The main theorem: A lattice \(L\) is obtained by convex doubling if and only if the \(A\)-table of the lattice admits a tableau \(T\) of a certain form satisfying three conditions (AR, BL and BR). Corollary: A lattice \(L\) is in CN if and only if admits a CN-tableau. With the \(A\)-table of the lattice as input, instead of the lattice itself, a satisfactory time complexity in \(O(\left|J\right|\times \left|M\right|)\) (\(J\), \(M\) the irreducible elements) is obtained.