𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An incremental algorithm to construct a lattice of set intersections

✍ Scribed by Derrick G. Kourie; Sergei Obiedkov; Bruce W. Watson; Dean van der Merwe

Publisher
Elsevier Science
Year
2009
Tongue
English
Weight
864 KB
Volume
74
Category
Article
ISSN
0167-6423

No coin nor oath required. For personal study only.

✦ Synopsis

a b s t r a c t An incremental algorithm to construct a lattice from a collection of sets is derived, refined, analyzed, and related to a similar previously published algorithm for constructing concept lattices. The lattice constructed by the algorithm is the one obtained by closing the collection of sets with respect to set intersection. The analysis explains the empirical efficiency of the related concept lattice construction algorithm that had been observed in previous studies. The derivation highlights the effectiveness of a correctness-byconstruction approach to algorithm development.

πŸ“œ SIMILAR VOLUMES

An Optimal Algorithm for the Intersectio
An Optimal Algorithm for the Intersection Radius of a Set of Convex Polygons
✍ Shreesh Jadhav; Asish Mukhopadhyay; Binay Bhattacharya πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 224 KB

The intersection radius of a finite collection of geometrical objects in the plane is the radius of the smallest closed disk that intersects all the objects in the collection. Bhattacharya et al. showed how the intersection radius can be found in linear time for a collection of line segments in the

An algebraic approach to the prefix mode
An algebraic approach to the prefix model analysis of binary trie structures and set intersection algorithms
✍ Pilar de la Torre; David T. Kao πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 861 KB

The trie, or digital tree, is a standard data structure for representing sets of strings over a given finite alphabet. Since Knuth's original work (1973), these data structures have been extensively studied and analyzed. In this paper, we present an algebraic approach to the analysis of average stor

Constructibility of the Set of Polynomia
Constructibility of the Set of Polynomials with a Fixed Bernstein–Sato Polynomial: an Algorithmic Approach
✍ Anton Leykin πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 279 KB

Let n and d be positive integers, let k be a field and let P(n, d; k) be the space of the non-zero polynomials in n variables of degree at most d with coefficients in k. Let B(n, d) be the set of the Bernstein-Sato polynomials of all polynomials in P(n, d; k) as k varies over all fields of character