Assume that we have a non-empty finite lattice $(L,\leq)$ and a monotone Boolean-valued function $f : L \rightarrow \mathbb{B}$ (i.e, for every $x,y \in L$, if $f(x)=\mathbf{true}$ and $x \leq y$, then $f(y) = \mathbf{true}$).
What is an efficient algorithm to compute the frontier set of $f$, i.e., the elements $x \in L$ such that $f(x) = \mathbf{true}$ for but no element $y \leq x$, we have $f(y) = \mathbf{true}$? Alternatively, what is an efficient algorithm to compute the co-frontier set of $f$, i.e., the elements $x \in L$ such that $f(x) = \mathbf{false}$ but for all elements element $y \geq x$, we have $f(y) = \mathbf{true}$?
The algorithm can use the following operations:
- Get the least element of $L$
- Get the maximum element of $L$
- For some element $x \in L$, compute the direct predecessors of $x$, i.e., the elements $y \in X$ with $y \leq x$, but for no $z \in L$, there is $y \leq z \leq x$).
- For some element $x \in L$, compute the direct successors of $x$, i.e., the elements $y \in X$ with $y \geq x$, but for no $z \in L$, there is $y \geq z \geq x$).
- Evaluate $f$ on some element of the lattice
The algorithm should minimize the number of calls to the oracle $f$. It can be assumed that the number of direct successors or predecessors of some element is constant and "small".
Some remarks that shall not be seen as part of the problem formulation:
I did a search on algorithms for this already and found a few papers that are not fully irrelevant for this problem. However, they either do not answer the problem, or they are tied to certain application domains, which makes it hard to even find out with certainty if they are related or not. An example is "Maximal Antichain Lattice Algorithms for Distributed Computations" by Vijay K. Garg.
The types of lattices that I am actually interested in are direct products of subsets of $\mathbb{N}$ and $\mathbb{B}$. The problem is is kind of an optimization problem, where $f$ tells us if some "quality requirement" vector is feasible or not.
Thanks!
