Re: Building a Lattice (Bj|rn Carlson)
Tue, 22 Dec 1992 19:33:41 GMT

          From comp.compilers

Related articles
Building a Lattice (1992-12-15)
Re: Building a Lattice chased@rbbb.Eng.Sun.COM (1992-12-18)
Re: Building a Lattice (1992-12-19)
Re: Building a Lattice (1992-12-22)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Bj|rn Carlson)
Organization: Computing Science Department, Uppsala University, Sweden
Date: Tue, 22 Dec 1992 19:33:41 GMT
References: 92-12-090
Keywords: theory

>>Can anyone point me to an algorithm for building a lattice?

>Go grubbing around in copies of the JACM from the last two or three years.

The reference is:
"Efficient Implementation of Lattice Operations"
Hassan Ait-Kaci, Robert Boyer, Patrick Lincoln, and Roger Nasr
ACM Transactions on Programming Languages and Systems
January 1989, vol 11, #1

>I happen to be specifically interested in a lattice whose meet is set
>intersection, whose join is set union, and whose partial ordering
>function is subset, but of course that shouldn't matter to the

The idea of the algorithm is that a set is encoded as a bit-vector,
where the coding maps meet and join to bitwise-and and bitwise-or.
The article also deals with compact encodings of sparse sets.

Bjorn Carlson
Computing Science Department
Uppsala University
Box 311 S-751 05
Uppsala Sweden (,

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.