Sun, 30 Aug 1992 04:05:26 GMT

Related articles |
---|

Representing unions of Cartesian products markjan@cs.kun.nl (1992-08-26) |

Re: Representing unions of Cartesian products graham@maths.su.oz.au (1992-08-30) |

Representing unions of Cartesian products hws@sagitta.csis.dit.csiro.au (1992-09-03) |

Newsgroups: | comp.compilers,comp.compression |

From: | graham@maths.su.oz.au (Graham Matthews) |

Organization: | School of Mathematics and Statistics, University of Sydney |

Date: | Sun, 30 Aug 1992 04:05:26 GMT |

References: | 92-08-159 |

Keywords: | theory, design |

(Mark-Jan Nederhof) writes:

*>I am looking for an efficient way to store and manipulate unions of*

*>Cartesian products. *

...

*>At this moment I am using a representation where a union of Cartesian*

*>products is transformed into another such that the Cartesian products do*

*>no longer overlap (i.e. they have no tuples in common). If possible I*

*>merge two Cartesian products into one. These transformations are however*

*>rather expensive. Does anyone have a better suggestion? references to*

*>papers?*

I may be off the mark here but one way to do this is to represent your

cartesian products as predicates. Then the union of two cartesian products

C1 and C2 is the logical or of their respective predicates, the

intersection is the logical and of their respective predicates, etc.

This scheme allows for fast membership testing of a tuple in a cartesian

product, and allows maintains enumerability. If C1 and C2 are enumerable

then so is C1 union C2, C1 intersect C2, etc.

Efficiency is a bit of an issue here, but given that you don't want to

represent cartesian products explicitly, you don't appear to have much

choice but to sacrifice efficiency.

graham

--

Graham Matthews

Pure Math, Uni.Sydney, Oz

graham@maths.su.oz.au

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.