Journal article
Efficient implementation of lattice operations
ACM transactions on programming languages and systems, v 11(1)
Jan 1989
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
Lattice operations such as greatest lower bound (GLB), least upper bound (LUB), and relative complementation (BUTNOT) are becoming more and more important in programming languages supporting object inheritance. We present a general technique for the efficient implementation of such operations based on an encoding method. The effect of the encoding is to plunge the given ordering into a boolean lattice of binary words, leading to an almost constant time complexity of the lattice operations. A first method is described based on a transitive closure approach. Then a more space-efficient method minimizing code-word length is described. Finally a powerful grouping technique called modulation is presented, which drastically reduces code space while keeping all three lattice operations highly efficient. This technique takes into account idiosyncrasies of the topology of the poset being encoded that are quite likely to occur in practice. All methods are formally justified. We see this work as an original contribution towards using semantic (vz., in this case, taxonomic) information in the engineering pragmatics of storage and retrieval of (vz., partially or quasi-ordered) information.
Metrics
Details
- Title
- Efficient implementation of lattice operations
- Creators
- Hassan Aït-Kaci - DEC/Paris Research Laboratory, FranceRobert Boyer - The University of Texas at AustinPatrick Lincoln - Stanford UniversityRoger Nasr - MCC, Austin, TX
- Publication Details
- ACM transactions on programming languages and systems, v 11(1)
- Publisher
- Association for Computing Machinery
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- [Retired Faculty]; Mathematics
- Web of Science ID
- WOS:A1989T191800006
- Scopus ID
- 2-s2.0-0024304651
- Other Identifier
- 991020638507404721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Computer Science, Software Engineering