I am looking for references on effective algorithms on finite lattices or posets, and in particular on lattices of monotonous functions between two lattices, with higher-order structure -- monotonous functions on monotonous functions, etc.
For example, consider two monotonous functions $f, g$ from $L$ to $L'$, what is an effective way to test whether $f \leq g$ or $f = g$? Is there an effective algorithm to enumerate all such functions?
(By effective I mean: reasonably good complexity, even if not necessarily optimal. It is possible to enumerate all functions from the carrier sets of $L$ to $L'$, and then filter out those that are not monotone, but this is unreasonably inefficient. For example it is exponential rather than linear for functions from a linear order on natural numbers [0; n] to the linear order [0; 1])
(Note: I also asked this question on cstheory.stackexchange.)
In the specific case where the domain $L$ is a linear order $[0; m]$ and the codomain a linear order $[0; n]$, two functions can of course be compared by a linear search in $[0; m]$ (stop at the first distinct input), but a divide-and-conquer approach is much more efficient. For example if the codomain $[0; m]$ is just $[0; 1]$, the image of any monotone function looks like $0..01...1$, and the divide-and-conquer approach specializes into a dichotomy on $f$ and $g$ in parallel to check that they switch from $0$ to $1$ at the same index -- this is logarithmic rather than linear in $m$.
I suppose that this approach could be extended to more general domains $L$ which are not a linear order, by considering their chain decomposition. But the details are not obvious. Also, some natural lattices have complex chain decompositions, and how to represent them effectively is not obvious -- for example, if $A$ and $B$ are lattices, the cartesian product $A \times B$ has a lattice structure which is highly non-linear even when $A$, $B$ are linear or almost-linear orders.
Have people described such algorithms precisely somewhere?
I have tried to look for literature myself, but didn't find anything conclusive:
- "lattice algorithms" often seem to refer to cryptography-related work on "number lattices" (subgroups of $\mathbb{R}^n$ or $\mathbb{Z}^n$), which have a very different structure.
- Algorithms on finite posets seem to be often presented as taking the adjacency matrix as input. But computing the adjacency matrix of a lattice of monotonous functions seems non-trivial in the first place -- doing this effectively already requires an effective comparison algorithm. For some lattices, for example lattices of monotonous functions, even performing an enumeration / bijecting into row/column numbers may be non-trivial.
