Mining minimal generators with Close-by-One: A unified algorithm for binary and L-fuzzy contexts

This paper proposes a unified algorithm for computing minimal generators by integrating the computation directly into the Close-by-One (CbO) framework. This single-pass approach works for both binary and L-fuzzy contexts, providing the first CbO-based method for fuzzy minimal generator computation.

Keywords

Minimal generators, Direct basis, Close-by-One, InClose, FastCbO, Unified algorithm, L-FCA

Minimal generators are fundamental to FCA, representing the most compact premises for deriving a concept. They are key to constructing direct implication bases. However, algorithms for their computation are often separate from those for lattice construction. This paper proposes a unified approach by integrating minimal generator computation directly into the Close-by-One (CbO) framework. We show how the search tree built by CbO algorithms (like InClose or FastCbO) contains all the necessary information to identify minimal generators with minimal overhead. We present a modified CbO algorithm that outputs both the concept lattice and all minimal generators in a single pass. Furthermore, we extend this approach to the L-fuzzy setting, providing the first CbO-based algorithm for fuzzy minimal generator computation.

Introduction

A minimal generator of a closed set C is a minimal set G \subseteq C such that G^{++}=C. They are crucial for building direct bases, which allow for linear-time closure computation. While algorithms exist for their computation, they often require the full lattice as input or perform a separate, complex search.

This paper demonstrates that the CbO search itself can be leveraged for this task. The CbO tree explores potential generators; our goal is to add a check to identify which of these are minimal.

Our contributions are:

1. An extension to the CbO algorithm that allows for the simultaneous computation of the concept lattice and all minimal generators.
2. A generalization of this algorithm to L-FCA.

Methodology and expected theoretical results

Theoretical foundation

The key is to find a condition for minimality that can be checked during the CbO traversal. * Main theoretical result: We will prove a theorem stating that a set G explored at a certain point in the CbO tree is a minimal generator of G^{++} if and only if no proper subset of G encountered earlier in the search generates the same closure. We will formalize this “first encounter” principle as a check within the algorithm.

Algorithmic design

The adapted CbO algorithm will maintain a data structure (e.g., a hash map) of already found closures. When generating a new candidate set G, before computing its closure, it checks if any subset of G has already been processed. This allows the identification of minimality. The extension to L-FCA will involve adapting this check for fuzzy sets of attributes.

Work plan

• Months 1-3: Prove the “first encounter” theorem for minimal generators in the CbO traversal.
• Months 4-6: Implement the modified CbO algorithm for both binary and L-fuzzy cases.
• Months 7-9: Evaluate the performance overhead of the additional checks compared to running a standard CbO.
• Months 10-12: Write the manuscript.

Potential target journals

1. Discrete Applied Mathematics (Q1): Excellent for a novel algorithm with a strong theoretical computer science foundation.
2. Information Sciences (Q1): A strong choice for a new, efficient core FCA algorithm.

Minimum viable article (MVA) strategy

• Paper 1 (The MVA):
  • Scope: The full paper as described, covering both the binary and the fuzzy case. The unified approach is the main novelty.
  • Goal: To provide a new, efficient, and integrated method for computing one of FCA’s most fundamental building blocks.
  • Target venue: Discrete Applied Mathematics.