home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / compiler / 1480 < prev    next >
Encoding:
Internet Message Format  |  1992-08-30  |  2.0 KB
  1. Xref: sparky comp.compilers:1480 comp.compression:3136
  2. Path: sparky!uunet!centerline!noc.near.net!news.Brown.EDU!qt.cs.utexas.edu!cs.utexas.edu!sun-barr!ames!agate!stanford.edu!rutgers!faatcrl!iecc!compilers-sender
  3. From: graham@maths.su.oz.au (Graham Matthews)
  4. Newsgroups: comp.compilers,comp.compression
  5. Subject: Re: Representing unions of Cartesian products
  6. Keywords: theory, design
  7. Message-ID: <92-08-180@comp.compilers>
  8. Date: 30 Aug 92 04:05:26 GMT
  9. References: <92-08-159@comp.compilers>
  10. Sender: compilers-sender@iecc.cambridge.ma.us
  11. Reply-To: graham@maths.su.oz.au (Graham Matthews)
  12. Organization: School of Mathematics and Statistics, University of Sydney
  13. Lines: 32
  14. Approved: compilers@iecc.cambridge.ma.us
  15.  
  16. (Mark-Jan Nederhof) writes:
  17. >I am looking for an efficient way to store and manipulate unions of
  18. >Cartesian products. 
  19. ...
  20. >At this moment I am using a representation where a union of Cartesian
  21. >products is transformed into another such that the Cartesian products do
  22. >no longer overlap (i.e. they have no tuples in common).  If possible I
  23. >merge two Cartesian products into one.  These transformations are however
  24. >rather expensive.  Does anyone have a better suggestion? references to
  25. >papers?
  26.  
  27. I may be off the mark here but one way to do this is to represent your
  28. cartesian products as predicates. Then the union of two cartesian products
  29. C1 and C2 is the logical or of their respective predicates, the
  30. intersection is the logical and of their respective predicates, etc.
  31.  
  32. This scheme allows for fast membership testing of a tuple in a cartesian
  33. product, and allows maintains enumerability. If C1 and C2 are enumerable
  34. then so is C1 union C2, C1 intersect C2, etc.
  35.  
  36. Efficiency is a bit of an issue here, but given that you don't want to
  37. represent cartesian products explicitly, you don't appear to have much
  38. choice but to sacrifice efficiency.
  39.  
  40. graham
  41. --
  42. Graham Matthews
  43. Pure Math, Uni.Sydney, Oz
  44. graham@maths.su.oz.au
  45. -- 
  46. Send compilers articles to compilers@iecc.cambridge.ma.us or
  47. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  48.