2
$\begingroup$

We will consider a set whose elements I call "precedences". Precedences are related by two relations: "is subclass of" and "higher than", which are specified by some pairs (given on algorithm input) of precedences conforming to these relations and by the below rules. All sets in consideration are finite.

Let "is subclass of" be the finite partial order on the set of precedences, generated as the smallest partial order containing specified pairs of precedences, these pairs are specified in algorithm input.

Let "higher than" be the smallest partial order conforming to the following rules:

  • We have (as an algorithm input) a set of pairs of precedences, the first element of which is higher than the second one.
  • If A is strictly higher than B then A1 is strictly higher than B1 for every their respective subclasses (that is objects related by "is subclass of" relation) A1 and B1. [Added strictly.]

I need:

  • check if the partial orders (conforming to the above) "is subclass of" and "higher than" exist;
  • calculate (based on algorithm input) the relations, especially the relation of being "higher than".

The sets of pairs of both "is subclass of" and "higher than" are added to the algorithm input in chunks (several pairs of them are specified and added to the current sets of pairs). I want the algorithm to be reasonably fast and so not to recalculate everything when new data is added.

Please help me to conceive a reasonably efficient algorithm. I am writing in Java.

Remark: I am afraid that finding a reasonably fast algorithm may take me several years. I am going to work on this problem nevertheless until I find a solution. Your help is appreciated. (Well, I also consider that I need to think how to change the question if it does not always have a solution (minimum $>_U$).)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.