Paper Info
Title
Reinventing known results in FCA: Notes on two recently published algorithms for computation of formal concepts
Abstract
Two recently published algorithms for computation of formal concepts are analyzed. The first algorithm, by Ma et al. (2016), is claimed to provide a new and efficient algorithm for generating all object-oriented concepts. We recall that the generating of all object-oriented concepts and generating of all standard concepts is basically the same problem, since the object-oriented case and the standard case are easily reducible to each other via the set complement. Taking this reducibility into account, Ma et al. merely repeat results by Qian and Wei (2014). The algorithm is not efficient due to its exponential space complexity. Furthermore, we show that the space complexity can be significantly improved by a simple tweak. The algorithm then becomes equivalent to Chein’s algorithm, initially published in 1969. The second analyzed algorithm was published by Singh (2017), who proposes an extension of Formal Concept Analysis which handles vague (fuzzy interval valued) data and provides a method for computation of the associated concept lattice. We show that the same extension has been proposed before by Djouadi and Prade in 2009; that the proposed algorithm is incorrect and that it becomes an already known algorithm when we fix it. Additionally, we fix multiple errors in information about related literature committed by Singh.
Year
DOI
Venue
2020
10.1016/j.dam.2019.01.017
Discrete Applied Mathematics
Keywords
Field
DocType
Formal concept analysis,Algorithm,Enumeration of concepts,Galois connections
Exponential function,Lattice (order),Fuzzy logic,Algorithm,Formal concept analysis,Mathematics,Computation
Journal
Volume
ISSN
Citations 
273
0166-218X
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Jan Konecny111517.20