DocumentCode
1167840
Title
A space-and-time-efficient coding algorithm for lattice computations
Author
Ganguly, Deb Dutta ; Mohan, Chilukuri K. ; Ranka, Sanjay
Author_Institution
Sch. of Comput. & Inf. Sci., Syracuse Univ., NY, USA
Volume
6
Issue
5
fYear
1994
fDate
10/1/1994 12:00:00 AM
Firstpage
819
Lastpage
829
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
encoding; inference mechanisms; inheritance; encoding algorithm; lattice computations; space requirements; space-and-time-efficient coding algorithm; Algebra; Algorithm design and analysis; Computer applications; Computer networks; Encoding; Lattices; Logic programming; Object oriented databases; Object oriented programming; Upper bound;
fLanguage
English
Journal_Title
Knowledge and Data Engineering, IEEE Transactions on
Publisher
ieee
ISSN
1041-4347
Type
jour
DOI
10.1109/69.317709
Filename
317709
Link To Document