问题标签 [poset]

在阅读 Bartosz 为程序员编写的优秀类别理论时，我陷入了第二个练习，该练习处理的是 posets 中的产品。给定一个poset，

如何在分类意义上定义产品？什么是按两个对象的乘积分类的？那么副产品呢？

我有一个包含所有空构造函数的简单数据类型，并希望为它定义一个偏序，包括Relation.Binary.IsPartialOrder _≡_.

我的用例：类型是抽象语法树（语句、表达式、文字、项目）中的排序类型，我想要一个 AST 的构造函数，它有效地向上转换一个术语（项目≤语句，表达式≤语句，文字≤表达）。

到目前为止，我有这个：

我可以定义isPreorder但不知道如何定义antisym：

我不确定在最后一个子句（以及所有类似的子句）中该做什么，无论如何这很麻烦。

我是否缺少一种更方便的方法来定义任意偏序？

假设我有两个有限的posets（例如用 构造sage.combinat.posets.posets.FinitePoset）。

我想计算二元关系，它是这些集合的顺序关系的组成。

如何在 Sage 中做到这一点？

（我是圣人新手。）

这是建立在上一个问题Solve a simple packing combination with dependencies 的基础上的，尽管无需查看该问题即可理解这一问题。

这个问题询问计算部分有序集合的线性扩展数量的最快方法。

在给定对象的任意顺序的情况下，可以将这种部分排序的列表可视化为打包配置的可行性。问题是，如果块一旦放置就不能移动，那么交给你的所有块的可能顺序是什么，以实现所示的包装配置？

在这个例子中，所有的块 ABCDEFG 都需要设置，A,B,C,D 的依赖：set{}, E: set{A,B},F: set{B,C} G: set{C, D}。

您可以通过检查 7 个块的所有排列并计算满足依赖关系的数量来获得完成偏序集的所有可能性。גלעד ברקן 在上一篇文章中提供了一个更快的替代方案，他使用了一个图形结构，如果在已经探索的节点中没有满足依赖关系，则终止对分支的进一步搜索。

我的问题是，是否有任何方法可以在不失一般性的情况下进一步优化 גלעד ברקן 的算法？如果依赖项稀缺并且列表可以进一步分解为独立的子列表，我可能会使其更快，但对于这个特定示例，情况并非如此。

我正在寻找一种用于存储 poset 的数据结构，它支持以下具有良好大复杂性的操作（这些操作经常进行）：

• 确定给定元素是否可以始终排在另一个元素之前（最高优先级高于其他元素）
• 添加新的排序约束
• 返回可以在给定元素之前排序的所有元素

数据结构还必须支持从 poset 生成一个完全有序的集合，但这只需要在算法运行后对输出执行一次。

到目前为止，我一直依赖于一个幼稚的 poset 实现，但我已经达到了不再可持续的地步。

我看过https://cstheory.stackexchange.com/questions/8503/what-persistent-data-structure-for-a-set-of-partially-ordered-elements，答案中有一些有趣的论文，但大多数这些数据结构（如ChainMerge）似乎都在考虑排序的情况下进行了优化，对我来说这是最不重要的一步。

在麻省理工学院讲座（计算机科学数学）之后，我正在研究离散结构。在书中，及物性的定义如下：

然后书上说下图 7.8 中的图形不满足传递性：

但我认为它在图 7.8 中已经传递为 v2 -> v3 和 v3 -> v4，然后是 v2 -> v4。

有人能帮我理解我在这里缺少什么吗？非常感谢你提前！！！

• 所有图片均来自课程笔记。