Stepwise construction of the Dedekind-MacNeille completion

DOI10.1007/BFB0054922MaRDI QIDQ4218274zbMATH OpenFDO

Authors Bernhard Ganter, Sergei O. Kuznetsov

Publication date 12 January 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0054922

algorithm complexity of inserting an element concept lattice finite ordered set incremental construction of lattices one-element extension preconcept

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Complete lattices, completions (06B23) Analysis of algorithms and problem complexity (68Q25)

Review text

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,\leq)\) and its completion \((L,\leq)\), constructs the completion of any one-element extension of \((P,\leq)\) in \(O(| L|\cdot| P|\cdot\omega(P))\) steps, where \(\omega(P)\) denotes the width of \((P,\leq)\). They obtain that the complexity of inserting an element into a lattice \((L,\leq)\) and then forming its completion is bounded by \(O(| L|^2\cdot\omega(L))\). For the entire collection see [Zbl 0895.00048].

Recommendations

Cited in

(5)

This page was built for publication: Stepwise construction of the Dedekind-MacNeille completion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4218274)