ged@batserver.cs.uq.oz.au (Gerard Ellis) (04/11/90)
I am interested in any pointers to the literature on the following problem.
Problem: Given the set S, a p.o. R on S defined by an oracle, and an element
top, give efficient implementations of the following set of operations:
(i) member(u, S)
(ii) specializations(u, S); returns the ordered set T = {v in S| v R u}
An obvious method would be to construct a Hasse diagram representing R on S,
and search from top, selecting a node of which u is a specialization from
adjacent nodes, at each step, resulting in a deterministic search for u.
This solves (i) and also (ii) given u in S.
Associated Problem: Given a set S, a p.o. R on S defined by an oracle, and
an element top, give efficient implementations of :
(i) construct(S) - construct a Hasse diagram representing R on S.
(ii) insert(u) - insert u into the Hasse diagram.
The second problem is of particular interest since elements of S will
arrive interspersed with queries (member, specializations).
Of particular interest are examples where elements of S are complex objects
(such as graphs) which minimize queries to the oracle.
Thankyou, Gerard.
email: ged@batserver.cs.uq.oz.au (overseas)
ged@batserver.cs.uq.oz (within Australia)
Gerard Ellis
Key Centre for Information Technology
University of Queensland, Qld, 4072
Australia