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\left(\right|L|\xb7|P|\xb7\omega (P\left)\right)$ steps, where

$\omega \left(P\right)$ 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\left(\right|L{|}^{2}\xb7\omega \left(L\right))$.

##### MSC:

06B23 | Complete lattices, completions |

06A07 | Combinatorics of partially ordered sets |

68Q25 | Analysis of algorithms and problem complexity |