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

Deb Dutta Ganguly; Chilukuri K. Mohan; Sanjay Ranka

doi:10.1109/69.317709

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

Deb Dutta Ganguly, Chilukuri K. Mohan, Sanjay Ranka

Department of Electrical Engineering & Computer Science

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	819-829
Number of pages	11
Journal	IEEE Transactions on Knowledge and Data Engineering
Volume	6
Issue number	5
DOIs	https://doi.org/10.1109/69.317709
State	Published - 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

Access to Document

10.1109/69.317709

Cite this

@article{6f8c25cdb7fd4c17bea55245416525cd,

title = "A Space-and-Time-Efficient Coding Algorithm for Lattice Computations",

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.",

keywords = "Lattices, encoding algorithm, greatest lower bound, least upper bound, partially ordered sets",

author = "Ganguly, {Deb Dutta} and Mohan, {Chilukuri K.} and Sanjay Ranka",

note = "Funding Information: Manuscript received November 5, 1990; revised May 20, 1992, and July 7, 1993. The work of S. Ranka was supported in part by the National Science Foundation under Research Grant CCR-9110812. The authors are with the School of Computer and Information Science, Syracuse University, Syracuse, NY 132444100 USA. IEEE Log Number 9214380.",

year = "1994",

month = oct,

doi = "10.1109/69.317709",

language = "English (US)",

volume = "6",

pages = "819--829",

journal = "IEEE Transactions on Knowledge and Data Engineering",

issn = "1041-4347",

publisher = "IEEE Computer Society",

number = "5",

}

TY - JOUR

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

AU - Ganguly, Deb Dutta

AU - Mohan, Chilukuri K.

AU - Ranka, Sanjay

N1 - Funding Information: Manuscript received November 5, 1990; revised May 20, 1992, and July 7, 1993. The work of S. Ranka was supported in part by the National Science Foundation under Research Grant CCR-9110812. The authors are with the School of Computer and Information Science, Syracuse University, Syracuse, NY 132444100 USA. IEEE Log Number 9214380.

PY - 1994/10

Y1 - 1994/10

N2 - 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.

AB - 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.

KW - Lattices

KW - encoding algorithm

KW - greatest lower bound

KW - least upper bound

KW - partially ordered sets

UR - http://www.scopus.com/inward/record.url?scp=0028518126&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028518126&partnerID=8YFLogxK

U2 - 10.1109/69.317709

DO - 10.1109/69.317709

M3 - Article

AN - SCOPUS:0028518126

SN - 1041-4347

VL - 6

SP - 819

EP - 829

JO - IEEE Transactions on Knowledge and Data Engineering

JF - IEEE Transactions on Knowledge and Data Engineering

IS - 5

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this