home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / compiler / 2063 < prev    next >
Encoding:
Text File  |  1992-12-22  |  1.6 KB  |  46 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!cis.ohio-state.edu!zaphod.mps.ohio-state.edu!darwin.sura.net!paladin.american.edu!gatech!news.byu.edu!eff!world!iecc!compilers-sender
  3. From: bjornc@groucho.csd.uu.se (Bj|rn Carlson)
  4. Subject: Re: Building a Lattice
  5. Reply-To: bjornc@groucho.csd.uu.se (Bj|rn Carlson)
  6. Organization: Computing Science Department, Uppsala University, Sweden
  7. Date: Tue, 22 Dec 1992 19:33:41 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-12-096@comp.compilers>
  10. References: <92-12-090@comp.compilers>
  11. Keywords: theory
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 31
  14.  
  15. >>Can anyone point me to an algorithm for building a lattice?
  16.  
  17. >Go grubbing around in copies of the JACM from the last two or three years.
  18.  
  19. The reference is:
  20. "Efficient Implementation of Lattice Operations"
  21. Hassan Ait-Kaci, Robert Boyer, Patrick Lincoln, and Roger Nasr
  22. ACM Transactions on Programming Languages and Systems
  23. January 1989, vol 11, #1
  24. 115-147
  25.  
  26. >I happen to be specifically interested in a lattice whose meet is set
  27. >intersection, whose join is set union, and whose partial ordering
  28. >function is subset, but of course that shouldn't matter to the
  29. >algorithm.
  30.  
  31. The idea of the algorithm is that a set is encoded as a bit-vector,
  32. where the coding maps meet and join to bitwise-and and bitwise-or.
  33. The article also deals with compact encodings of sparse sets.
  34.  
  35. --
  36. Bjorn Carlson
  37. Computing Science Department
  38. Uppsala University
  39. Box 311 S-751 05
  40. Uppsala Sweden
  41.  
  42. Bjorn.Carlson@csd.uu.se (bjornc@csd.uu.se, bjornc@sics.se)
  43. -- 
  44. Send compilers articles to compilers@iecc.cambridge.ma.us or
  45. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  46.