2
$\begingroup$

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: it is unclear to me that this question is research-level, so I first asked it on the Mathematics Stackexchange last week.)

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.
$\endgroup$
1
  • $\begingroup$ You could try adding keywords such as "distributive", "skew" or "finitely presented" to filter out the cryptography-related articles. This yields a few articles such as "Efficient polynomial algorithms for distributive lattices" that are not quite what you want, but ought to be somewhat close to it in the "cited by" graph. $\endgroup$
    – xavierm02
    Aug 7, 2023 at 22:01

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.