Time and Space Efficient Representations of Distributive Lattices
J. Ian Munro, Corwin Sinnamon · Society for Industrial and Applied Mathematics eBooks · 2018
We present a space-efficient data structure using O(n log n) bits that represents a distributive lattice on n elements and supports finding meets and joins in O(log n) time. Our data structure extends the ideal tree structure of Habib and Nourine which occupies O(n log n) bits of space and requires O(m) time to compute a meet or join, where m depends on the specific lattice and may be as large as n – 1. We also give an encoding of a distributive lattice using bits, which is very close to the information theoretic lower bound. This encoding can be created or decompressed in O(n log n) time.