home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / compiler / 1511 < prev    next >
Encoding:
Internet Message Format  |  1992-09-03  |  1.9 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!rutgers!faatcrl!iecc!compilers-sender
  2. From: hws@sagitta.csis.dit.csiro.au (Heinz Schmidt)
  3. Newsgroups: comp.compilers
  4. Subject: Representing unions of Cartesian products
  5. Keywords: theory, design
  6. Message-ID: <92-09-030@comp.compilers>
  7. Date: 3 Sep 92 05:21:51 GMT
  8. References: <92-08-159@comp.compilers>
  9. Sender: compilers-sender@iecc.cambridge.ma.us
  10. Reply-To: hws@sagitta.csis.dit.csiro.au (Heinz Schmidt)
  11. Organization: CSIRO Div Info Tech & Australian Ntl Univ, Canberra
  12. Lines: 30
  13. Approved: compilers@iecc.cambridge.ma.us
  14.  
  15.  
  16.   > I am looking for an efficient way to store and manipulate unions of
  17.   > Cartesian products. 
  18.  
  19. Sounds similar to object-oriented type lattices to me, with your Cartesian
  20. products corresponding to constructor types at the bottom and abstract or
  21. virtual types forming the unions. I may be way off though.
  22.  
  23. Take a look at      Ait-Kaci et al:
  24.                     Efficient Implementation of Lattice Operations 
  25.                     Toplas 11(1), 1/89.
  26.  
  27.   > represents C_1 - C_2.  (The operator - denotes the subtraction of sets ...
  28.  
  29. They also consider relative complements (set difference / but-not).  At
  30. least for inheritance lattices (which I tend to visualize as low-degree
  31. except for artificial bottom and top, broad and flat, with few outlyers in
  32. depth), they achieve near O(1) meet, join and relative complement
  33. operations on bit vectors representing compressed transitive closures. A
  34. further compaction called modulation results in O(N log N) space
  35. requirements but may hit efficiency of meet and rel complement depending
  36. on the structure of the lattice.
  37.  
  38. Heinz W. Schmidt                  hws@csis.dit.csiro.au
  39. CSIRO, Div Information Technology tel ++61 6 275-0974
  40. and                               fax ++61 6 257-1052
  41. Aus Natl Univ, Dept Comp Science  Canberra, Australia   
  42. -- 
  43. Send compilers articles to compilers@iecc.cambridge.ma.us or
  44. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  45.