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

doi:10.1109/69.317709

Return

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

1994-01-01

GANGULY, DD

Chilukuri K. Mohan

Sanjay Ranka

DOI：10.1109/69.317709

Original

Save

View PDF

Abstract

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.

Keywords:

LATTICES

LEAST UPPER BOUND

GREATEST LOWER BOUND

ENCODING ALGORITHM

PARTIALLY ORDERED SETS

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.