A Space-and-Time-Efficient Coding Algorithm for Lattice Computations

Deb Dutta Ganguly, Chilukuri K. Mohan, Sanjay Ranka

Research output: Contribution to journalArticle

9 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)819-829
Number of pages11
JournalIEEE Transactions on Knowledge and Data Engineering
Volume6
Issue number5
DOIs
StatePublished - Oct 1994

Keywords

  • Lattices
  • encoding algorithm
  • greatest lower bound
  • least upper bound
  • partially ordered sets

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'A Space-and-Time-Efficient Coding Algorithm for Lattice Computations'. Together they form a unique fingerprint.

  • Cite this