Stepwise construction of the Dedekind-MacNeille completion. (English) Zbl 0928.06004
Mugnier, Marie-Laure (ed.) et al., Conceptual structures: theory, tools and applications. 6th international conference, ICCS ’98, Montpellier, France, August 10--12, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1453, 295-302 (1998).
The authors deal with the problem of incremental construction of lattices. They show that, with a rather general approach, this problem becomes well structured. They give a simple algorithm that, given a finite ordered set $(P,\le)$ and its completion $(L,\le)$, constructs the completion of any one-element extension of $(P,\le)$ in $O(| L|\cdot| P|\cdot\omega(P))$ steps, where $\omega(P)$ denotes the width of $(P,\le)$. They obtain that the complexity of inserting an element into a lattice $(L,\le)$ and then forming its completion is bounded by $O(| L|^2\cdot\omega(L))$. For the entire collection see [Zbl 0895.00048
|06B23||Complete lattices, completions|
|06A07||Combinatorics of partially ordered sets|
|68Q25||Analysis of algorithms and problem complexity|