Binary search generalizations for posets? Suppose I have a poset "S" and a monotonic predicate "P" on S.
I want to find one or all maximal elements of S satisfying P.

EDIT: I'm interested in minimizing the number of evaluations of P.

What algorithms do there exist for this problem and what properties and additional operations do they require on S?

What about important special cases, such as:


 S is a linear order - then regular binary search works, as long as you have a "find middle" operation
 S is a lattice
 S is a subset lattice
 S is a multiset lattice
 ...


The two latter cases seem particularly important e.g. for experiment design - you have a set of boolean or real parameters, and you wish to find the smallest possible combination of them that reproduces a particular pattern (e.g. a failing test).
I have not thought this through very much, so please correct me if I am wrong.

Say $w$ is the width of the poset.


For the poset which is the union of $w$ disjoint chains you need at least $w\log n$ evaluations of $P$ by just applying the standard lower bound on the query complexity of binary search to each chain.
Since you give comparisons for free, you can compute a chain decomposition of the poset into $w$ chains for free. Do binary search on each chain to identify the first element that satisfies $P$. Then go over the identified elements and remove any dominated ones. Number of evaluations of $P$ is $O(w\log n)$. This identifies all maximal elements, as there can be at most one maximal element per chain.




ADDED: Actually I am seeing a simple recursive algorithm to do much better ($O(n)$) for the lattice of subsets $2^{[n]}$ (EDIT: domotor described the general strategy in his answer). Here I am assuming $P$ is monotonic downwards (i.e. the subsets $\{X: P(X) = 1\}$ form a lower set), which is I think what you mean. So, here is the algorithm to find a member of the lower set:

a) Test $P(\emptyset)$. If 0, then stop.

b) Test $P(\{n\})$.  

b.i) If 0, then recurse on $2^{[n-1]}$ (OK, since no set containing $n$ can be in the lower set). 

b.ii) If 1, then there exists a member of the lower set in the sublattice $\{X: n \in X\}$. This sublattice is isomorphic to $2^{[n-1]}$ so once again we can recurse. More precisely, we can run the algorithm for $2^{[n-1]}$, but when the algorithm asks to evaluate $P(Y)$, we evaluate $P(X)$ where $X = Y \cup \{n\}$.

So in each step we recurse on a sublattice which is half the size of original one. Overall, we need to evaluate $P$ at most $2n$ times (in fact you can implement the algorithm to evaluate the predicate $n+1$ times as Yoshio points out, since you only need to check $\emptyset$ once).