论文标题
封闭系统最大扩展的表示形式
Representations for the largest Extension of a closure system
论文作者
论文摘要
我们将闭合系统在有限集S上的扩展作为封闭系统作为封闭系统，该系统包含给定的系统作为sublattice。封闭系统可以以不同的方式表示，例如通过一个含义的基础，或者通过其会议式元素的集合。当闭合系统由含义基础描述时，我们为最大扩展的含义基础提供了特征。我们还表明，最大的扩展可以通过对输入闭合系统的含义基础的小修改来处理。这回答了[12]中提出的问题。其次，我们有兴趣计算最大的扩展，当闭合系统由其所有可召开的元素组成的集合给出。我们给出一个增量的多项式时间算法来计算闭合系统的最大扩展，如果会议元素的数量呈指数增长，则保持打开状态。
We consider extension of a closure system on a finite set S as a closure system on the same set S containing the given one as a sublattice. A closure system can be represented in different ways, e.g. by an implicational base or by the set of its meet-irreducible elements. When a closure system is described by an implicational base, we provide a characterization of the implicational base for the largest extension. We also show that the largest extension can be handled by a small modification of the implicational base of the input closure system. This answers a question asked in [12]. Second, we are interested in computing the largest extension when the closure system is given by the set of all its meet-irreducible elements. We give an incremental polynomial time algorithm to compute the largest extension of a closure system, and left open if the number of meet-irreducible elements grows exponentially.
