Succinctness and tractability of closure operator representations

详细信息    查看全文

• 作者：Sebastian Rudolph ^{sebastian.rudolph@tu-dresden.de}
• 关键词：Closure operators ; Formal contexts ; Implications ; Tractability ; Succinctness ; Computational properties
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：7 January 2017
• 年：2017
• 卷：658
• 期：part_PB
• 页码：327-345
• 全文大小：541 K
• 卷排序：658

文摘

It is widely known that closure operators on finite sets can be represented by sets of implications (also known as inclusion dependencies) as well as by formal contexts. In this article, we consider these two representation types, as well as generalizations of them: extended implication sets and context families. We discuss the mutual succinctness of these four representations and the tractability of certain operations used to compare and modify closure operators.