A SPACE-AND-TIME-EFFICIENT CODING ALGORITHM FOR LATTICE COMPUTATIONS

GANGULY, DD

doi:10.1109/69.317709

1994-01-01

GANGULY, DD

Chilukuri K. Mohan

Sanjay Ranka

DOI：10.1109/69.317709

原文链接

查看原文

摘要

En 中文

We present an encoding algorithm-for lattices that significantly reduces space requirements while allowing fast computations of least upper bounds and greatest lower bounds of pairs of elements. We analyze the algorithms for encoding, LUB and GLB computations, and prove their correctness. Empirical experiments reveal that our method is significantly more space efficient than the transitive closure method, and the saving becomes increasingly more important as the size of the lattice increases.

Keyword:

LATTICES

LEAST UPPER BOUND

GREATEST LOWER BOUND

ENCODING ALGORITHM

PARTIALLY ORDERED SETS