Re: Building a Lattice

bjornc@groucho.csd.uu.se (Bj|rn Carlson)
Tue, 22 Dec 1992 19:33:41 GMT

          From comp.compilers
Related articles
Building a Lattice un027705@wvnvms.wvnet.edu (1992-12-15)
Re: Building a Lattice chased@rbbb.Eng.Sun.COM (1992-12-18)
Re: Building a Lattice preston@dawn.cs.rice.edu (1992-12-19)
Re: Building a Lattice bjornc@groucho.csd.uu.se (1992-12-22)
| List of all articles for this month |
Newsgroups: comp.compilers
From: bjornc@groucho.csd.uu.se (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
115-147


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


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


Bjorn.Carlson@csd.uu.se (bjornc@csd.uu.se, bjornc@sics.se)
--

Post a followup to this message

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