Computing the Duquenne–Guigues basis: an algorithm for choosing the order

Abstract

This paper presents an algorithm for choosing the order in which pseudo-intents are enumerated when computing the Duquenne–Guigues basis of a formal context. Sets are constructed through the use of a spanning tree to ensure they are all found once. The time and space complexities of the algorithm are empirically evaluated using, respectively, the number of logical closures and the number of sets in memory as measures. It is found that only the space complexity depends on the enumeration order.

Keywords:

• Formal concept analysis
• Duquenne–Guigues basis
• pseudo-intents

Notes

No potential conflict of interest was reported by the authors.