Tue, 22 Dec 1992 19:33:41 GMT

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) |

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.