|Representing unions of Cartesian products email@example.com (1992-08-26)|
|Re: Representing unions of Cartesian products firstname.lastname@example.org (1992-08-30)|
|Representing unions of Cartesian products email@example.com (1992-09-03)|
|From:||firstname.lastname@example.org (Heinz Schmidt)|
|Organization:||CSIRO Div Info Tech & Australian Ntl Univ, Canberra|
|Date:||Thu, 3 Sep 1992 05:21:51 GMT|
> 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 email@example.com
CSIRO, Div Information Technology tel ++61 6 275-0974
and fax ++61 6 257-1052
Aus Natl Univ, Dept Comp Science Canberra, Australia
Return to the
Search the comp.compilers archives again.