Representing unions of Cartesian products (Heinz Schmidt)
Thu, 3 Sep 1992 05:21:51 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
From: (Heinz Schmidt)
Organization: CSIRO Div Info Tech & Australian Ntl Univ, Canberra
Date: Thu, 3 Sep 1992 05:21:51 GMT
Keywords: theory, design
References: 92-08-159

    > I am looking for an efficient way to store and manipulate unions of
    > Cartesian products.

Sounds similar to object-oriented type lattices to me, with your Cartesian
products corresponding to constructor types at the bottom and abstract or
virtual types forming the unions. I may be way off though.

Take a look at Ait-Kaci et al:
                                        Efficient Implementation of Lattice Operations
                                        Toplas 11(1), 1/89.

    > represents C_1 - C_2. (The operator - denotes the subtraction of sets ...

They also consider relative complements (set difference / but-not). At
least for inheritance lattices (which I tend to visualize as low-degree
except for artificial bottom and top, broad and flat, with few outlyers in
depth), they achieve near O(1) meet, join and relative complement
operations on bit vectors representing compressed transitive closures. A
further compaction called modulation results in O(N log N) space
requirements but may hit efficiency of meet and rel complement depending
on the structure of the lattice.

Heinz W. Schmidt
CSIRO, Div Information Technology tel ++61 6 275-0974
and fax ++61 6 257-1052
Aus Natl Univ, Dept Comp Science Canberra, Australia

Post a followup to this message

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