<p>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}$).</p>

<p>What is an efficient algorithm to compute the <em>frontier set</em> 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 <em>co-frontier set</em> 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}$?</p>

<p>The algorithm can use the following operations:</p>

<ul>
<li>Get the least element of $L$</li>
<li>Get the maximum element of $L$</li>
<li>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$). </li>
<li>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$). </li>
<li>Evaluate $f$ on some element of the lattice</li>
</ul>

<p>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".</p>

<hr>

<p><em>Some remarks that shall not be seen as part of the problem formulation:</em></p>

<p>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.</p>

<p>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.</p>

<p>Thanks! </p>

CC BY-SA 3.0
2013-06-17T18:46:40.673Z
I think we had a similar question sometime ago but I might be mistaken. I will post a link if I find it.
Kaveh
CC BY-SA 3.0
2013-06-18T04:43:06.140Z
http://cstheory.stackexchange.com/questions/8923/binary-search-generalizations-for-posets/8943#8943
Sasho Nikolov
CC BY-SA 3.0
2013-06-18T20:42:45.547Z
close as duplicate ?
Suresh Venkat
CC BY-SA 3.0
2013-06-19T19:20:22.970Z
Suresh, go ahead with closing it if you want. By the way: I ended up using an algorithm that works bottom-up instead of the ones given in the other thread. The reason is that for the application that I have in mind, the complexity of evaluating the function actually rises with the position of an element in the lattice. Note that I couldn't find the other other post on google as it was using terms like "monotonic predicate" rather than "monotone function" and "poset" rather than "partially ordered set", which I simply didn't recognize as being good search words.
DCTLib
CC BY-SA 3.0
2013-06-20T18:32:14.960Z
it appears to me to be equivalent to finding the minterms and maxterms of a monotone boolean function?
vzn
<ds.algorithms><lattice>
Computing a frontier set for some Boolean-valued function in a lattice?
DCTLib
# Computing a frontier set for some Boolean-valued function in a lattice?

(Asked by: username_0 on 2013-06-17)

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!

**Tags:** ds.algorithms, lattice
> **Comments:**
> **username_1**: I think we had a similar question sometime ago but I might be mistaken. I will post a link if I find it.  
> **username_2**: http://cstheory.stackexchange.com/questions/8923/binary-search-generalizations-for-posets/8943#8943  
> **username_3**: close as duplicate ?  
> **username_0**: Suresh, go ahead with closing it if you want. By the way: I ended up using an algorithm that works bottom-up instead of the ones given in the other thread. The reason is that for the application that I have in mind, the complexity of evaluating the function actually rises with the position of an element in the lattice. Note that I couldn't find the other other post on google as it was using terms like "monotonic predicate" rather than "monotone function" and "poset" rather than "partially ordered set", which I simply didn't recognize as being good search words.  
> **username_4**: it appears to me to be equivalent to finding the minterms and maxterms of a monotone boolean function?  

---

## 0 answers

