论文标题
列举列出的列表列出了会议元素
Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements
论文作者
论文摘要
我们对在闭合系统的两个表示之间进行翻译的问题感兴趣，即含义的基础和会议元素。尽管它的重要性是开放的，尽管它的重要性是开放的。在这个问题的激励下，我们引入了一个含义基础的分裂。这是对含义的分区操作，我们递归地将其应用于代表含义基础的分解的二进制树。我们表明，这种分解可以在输入含义基础的大小的多项式时间和空间中进行。为了将我们的分解用于翻译任务，我们专注于无环形分裂的情况。在这种情况下，我们获得了相关闭合系统的会议元素的递归表征。我们使用这种表征和超图偶化来为环形凸几何形状中的翻译问题得出新的结果。
We are interested in the problem of translating between two representations of closure systems, namely implicational bases and meet-irreducible elements. Albeit its importance, the problem is open. Motivated by this problem, we introduce splits of an implicational base. It is a partitioning operation of the implications which we apply recursively to obtain a binary tree representing a decomposition of the implicational base. We show that this decomposition can be conducted in polynomial time and space in the size of the input implicational base. In order to use our decomposition for the translation task, we focus on the case of acyclic splits. In this case, we obtain a recursive characterization of the meet-irreducible elements of the associated closure system. We use this characterization and hypergraph dualization to derive new results for the translation problem in acyclic convex geometries.
