Towards Antichain Algebra

摘要

We use an algebra of preference strict-orders to give a formal derivation of the standard Block-Nested Loop (BNL) algorithm for computing the best or maximal objects w.r.t. such an order. This derivation is presented in terms of antichains, i.e., sets of mutually incomparable objects. We define an approximation relation between antichains that reflects the steps taken by the BNL algorithm. This induces a semilat-tice and the operator computing the maximal objects of a subset can be viewed as a closure operator in an associated pre-ordered set and hence yields a characterisation of antichains in terms of a Galois connection.