home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / compiler / 1457 < prev    next >
Encoding:
Internet Message Format  |  1992-08-29  |  3.1 KB
  1. Xref: sparky comp.compilers:1457 comp.compression:3121
  2. Path: sparky!uunet!gatech!rutgers!faatcrl!iecc!compilers-sender
  3. From: markjan@cs.kun.nl (Mark-Jan Nederhof)
  4. Newsgroups: comp.compilers,comp.compression
  5. Subject: Representing unions of Cartesian products
  6. Keywords: theory, design, question
  7. Message-ID: <92-08-159@comp.compilers>
  8. Date: 26 Aug 92 15:29:02 GMT
  9. Sender: compilers-sender@iecc.cambridge.ma.us
  10. Reply-To: markjan@cs.kun.nl (Mark-Jan Nederhof)
  11. Organization: University of Nijmegen, The Netherlands
  12. Lines: 59
  13. Approved: compilers@iecc.cambridge.ma.us
  14.  
  15. I am looking for an efficient way to store and manipulate unions of
  16. Cartesian products. 
  17.  
  18. The application domain is abstract evaluation of certain programs (e.g.
  19. datalog programs) and analysis of formal grammars (context-free grammars
  20. extended with features/parameters over a finite domain).
  21.  
  22. Our goal is to determine the set of parameters with which a nonterminal
  23. can generate a terminal string. If this is done by means of bottom-up
  24. analysis then we need the following operations:
  25.  
  26. -For two or more sets of tuples of the form A_1 * A_2 * ... * A_n, for
  27. fixed n, we have to compute the union in an efficient form.  (The operator
  28. * denotes the Cartesian product.)  Here the sets A_i consist of atomic
  29. values.
  30.  
  31. -For two unions of Cartesian products in such an efficient form, call them
  32. C_1 and C_2, we have to compute a third set C_3 in the same form which
  33. represents C_1 - C_2.  (The operator - denotes the subtraction of sets of
  34. tuples.)
  35.  
  36. -Let us consider two unions of Cartesian products in such an efficient
  37. form, call them again C_1 and C_2. We now have to compute the set C_3
  38. which represents the set of tuples
  39.  
  40. {(a_1, a_2, ..., a_n) | (b_1, ..., b_m) <- C_1 AND
  41.                         (c_1, ..., c_k) <- C_2 AND
  42.                          R (a_1, ..., a_n, b_1, ..., b_m, c_1, ..., c_k)},
  43.  
  44. where R is some relation which for some fixed pairs of its arguments says
  45. that they should have the same value. (The operator <- denotes inclusion.)
  46. This operation would be needed in case of a grammar rule with two members
  47. (with m and k parameters respectively; R is determined by ``consistent
  48. substitution''). You can generalise this to arbitrary grammar rules.
  49.  
  50. This query is inspired by two things:
  51.  
  52. -The sets of atomic values are typically too big to represent sets of
  53. tuples in a naive way by one element for every tuple.
  54.  
  55. -When the union of sets of the form A_1 * A_2 * ... * A_n is computed then
  56. very often these sets overlap, and are even ``almost the same but not
  57. quite''.
  58.  
  59. At this moment I am using a representation where a union of Cartesian
  60. products is transformed into another such that the Cartesian products do
  61. no longer overlap (i.e. they have no tuples in common).  If possible I
  62. merge two Cartesian products into one.  These transformations are however
  63. rather expensive.  Does anyone have a better suggestion? references to
  64. papers?
  65.  
  66. I suggest follow-up at comp.compression.
  67.  
  68. Mark-Jan Nederhof
  69. University of Nijmegen
  70. The Netherlands
  71. -- 
  72. Send compilers articles to compilers@iecc.cambridge.ma.us or
  73. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  74.