Re: Representing unions of Cartesian products (Graham Matthews)
Sun, 30 Aug 1992 04:05:26 GMT

          From comp.compilers

Related articles
Representing unions of Cartesian products (1992-08-26)
Re: Representing unions of Cartesian products (1992-08-30)
Representing unions of Cartesian products (1992-09-03)
| List of all articles for this month |

Newsgroups: comp.compilers,comp.compression
From: (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

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 Matthews
Pure Math, Uni.Sydney, Oz

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.