形式背景同构判定的等价类算法  

Context Isomorphism Detection Algorithm: Equivalence Classes Algorithm

作　　者：沈夏炯[1,2] 贾培艳[1] 刘宗田[3] 

机构地区：[1]河南大学计算机与信息工程学院 [2]上海大学计算机工程与科学学院上海200072 [3]上海大学计算机工程与科学学院

出　　处：《计算机科学》2006年第12期148-151,155,共5页Computer Science

基　　金：国家自然科学基金(60275022);上海市高等学校青年发展基金(03AQ99);河南省自然科学基金(0311011700)资助。

摘　　要：同构生成概念格是获取概念格的另一途径,而形式背景同构判定是这一方法的前提,也是决定整个算法时间复杂度的关键。本文提出的基于等价类法的形式背景同构判定算法,有效地提高了同构判定的效率。结合形式背景的分解和约简等手段,为概念格的构造提供了一种有实用价值的方法。本文对该方法的原理和算法设计进行了较详细的讨论,并通过实验,验证了算法的正确性和有效性。Isomorphic generating is a new way to obtain concept lattices. Isomorphism detecting of context is not only the presupposition of the methodology but also the key procedure to decline the complexity of time. This paper suggests an isomorphism detecting algorithm based on equivalent class, which improves the efficiency of context isomorphism detection. The method provides a practical way to construct concept lattices by combining means such as decomposition and reduction of contexts. The authors discuss the detail of the principles and designs of the algorithm, and verify the validities by implementing the algorithrm .

关 键 词：形式概念分析 形式背景 同构 概念格 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]