Thu, 3 Sep 1992 05:21:51 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 |

From: | hws@sagitta.csis.dit.csiro.au (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 hws@csis.dit.csiro.au

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.