有限格及高阶单调函数格的高效算法相关文献与具体实现问题问询

我正在寻找关于有限格或偏序集上高效算法的参考资料，尤其关注两个格之间的单调函数格，以及这类结构的高阶拓展——比如单调函数上的单调函数等。

具体问题 #

• 给定两个从格$L$到$L'$的单调函数$f, g$，有没有高效的方法测试$f \leq g$或者$f = g$？
• 是否存在高效算法可以枚举所有这类单调函数？

这里我所说的「高效」指复杂度合理即可，不一定要求最优。比如直接枚举$L$到$L'$的所有函数再过滤非单调函数的方法完全不可取——这种方法复杂度过高，比如从自然数线性序$[0;n]$到$[0;1]$的单调函数，暴力枚举是指数级的，但实际上线性甚至更优的算法是存在的。

线性序场景的已知高效方法 #

在定义域$L$是线性序$[0;m]$、陪域是线性序$[0;n]$的特殊情况下，虽然可以通过遍历$[0;m]$比较两个函数（找到第一个不同的输入就停止），但分治方法效率高得多：
比如当陪域是$[0;1]$时，单调函数的图像必然是一段连续的0后跟一段连续的1，此时可以用二分法同时对$f$和$g$进行查找，验证它们从0切换到1的位置是否一致——这种方法的复杂度是$O(\log m)$，远优于线性遍历。

对一般格的拓展思考 #

我猜想这种分治思路可以拓展到非线序的更一般格$L$上，比如考虑格的链分解。但具体细节并不明确，而且有些天然的格链分解很复杂，如何高效表示它们也是个问题——比如当$A$和$B$是格时，笛卡尔积$A \times B$的格结构即使在$A$、$B$都是线性序或近似线性序时，也高度非线性。

文献查找遇到的困境 #

有没有人详细描述过这类算法？我自己尝试查找文献，但没找到太明确的结果：

• 搜索「lattice algorithms」时，结果大多是密码学领域关于「数格」（$\mathbb{R}^{n$或$\mathbb{Z}}n$的子群）的研究，和我关注的结构完全不同。
• 有限偏序集上的算法通常以邻接矩阵作为输入，但要计算单调函数格的邻接矩阵本身就不简单——这其实已经需要高效的比较算法了。对于某些格（比如单调函数格），甚至连枚举元素、或者给元素分配行列编号这类基础操作都很有挑战性。

备注：内容来源于stack exchange，提问作者gasche