From decomposition to deduction: Computing the canonical basis with AUGMENTED CARVE

This paper extends the AUGMENTED CARVE algorithm to compute the minimal (canonical) basis of implications directly. We propose new synthesis rules and a method for ‘pseudo-intent propagation’ to filter redundancies during the divide-and-conquer process, aiming to be faster than monolithic algorithms.

Keywords

AUGMENTED CARVE, Canonical basis, Duquenne-Guigues, Pseudo-intents, Decomposition, Knowledge-Based Systems

The AUGMENTED CARVE algorithm has demonstrated that context decomposition can dramatically accelerate the computation of a complete implication system. However, the system it generates is not minimal, often containing redundant implications. This paper addresses this final gap by extending the framework to compute the Duquenne-Guigues (canonical) basis directly from the decomposition. We explore two complementary strategies: (1) adapting the synthesis phase of AUGMENTED CARVE with new rules to filter out redundant implications during the reconstruction process, and (2) analyzing the propagation and transformation of pseudo-intents from the leaf nodes of the CARVE tree up to the root. We prove that this extended synthesis process correctly yields the canonical basis of the original context and demonstrate that this decomposition-based approach is orders of magnitude faster than monolithic algorithms on highly structured contexts.

Introduction

Our recent work on AUGMENTED CARVE showed that a divide-and-conquer approach is highly effective for computing a correct and complete set of implications. The algorithm computes bases for small, simple sub-contexts and then “synthesizes” them to produce a system for the original context. While the resulting system is complete, it is not guaranteed to be minimal (i.e., it is not the canonical basis).

This paper presents the final step in this research line: modifying the synthesis phase to produce the canonical basis directly. Achieving this would establish CARVE-based decomposition as the unequivocally superior method for structured contexts for all major FCA computation tasks.

Our contributions are:

1. A set of new synthesis rules for AUGMENTED CARVE designed to preserve basis minimality.
2. A theoretical analysis of how pseudo-intents from sub-contexts can be combined or transformed to form the pseudo-intents of the parent context.
3. A complete algorithm, Canonical-ACARVE, that computes the canonical basis from a CARVE decomposition.

Methodology and expected theoretical results

The research will focus on the synthesis phase of the algorithm, which reconstructs the knowledge from the decomposed parts.

Strategy 1: Redundancy-filtering synthesis

The current AUGMENTED CARVE synthesis rules can generate implications that are deducible from others. We will develop a new set of refined synthesis rules. * Expected result: A new set of theorems of the form: “If $\Sigma_1$ and $\Sigma_2$ are the canonical bases for sub-contexts $\mathbb{K}_1$ and $\mathbb{K}_2$, then the canonical basis for the combined context $\mathbb{K}$ is exactly the minimal, non-redundant subset of $f(\Sigma_1, \Sigma_2)$,” where $f$ is our new set of synthesis functions.

Strategy 2: Pseudo-intent propagation

This is a more fundamental approach. Instead of synthesizing implications, we synthesize the pseudo-intents themselves. * Main theoretical result: We will characterize how the pseudo-intents of a context $\mathbb{K}$ relate to the pseudo-intents of its CARVE sub-contexts. For example, if $\mathbb{K}$ is decomposed by removing a universal attribute $m$, what is the relationship between the pseudo-intents of $\mathbb{K}$ and the pseudo-intents of the smaller context? We will prove a set of propagation rules for pseudo-intents that mirror the synthesis steps of CARVE.

Work plan

• Months 1-5: Intensive theoretical work on both strategies. The pseudo-intent propagation approach is more fundamental and will likely be the primary focus. This will be the core of the collaboration with the co-authors.
• Months 6-8: Implement the Canonical-ACARVE algorithm based on the proven pseudo-intent propagation rules.
• Months 9-11: Benchmark the new algorithm against the original AUGMENTED CARVE (to show the overhead of ensuring canonicity) and against monolithic algorithms like LinCbO (to show the net performance gain).
• Month 12: Write the manuscript.

Potential target journals

1. Knowledge-Based Systems (Q1): The perfect venue, as the original paper was published there. This would be a direct and high-impact follow-up.
2. Information Sciences (Q1): Another top choice, given the paper’s strong algorithmic and performance focus.
3. Discrete Applied Mathematics (Q1): Suitable if the theoretical analysis of pseudo-intent propagation is particularly deep and elegant.

Minimum viable article (MVA) strategy

The goal is a single, powerful journal paper that completes the CARVE-for-implications storyline.

• Paper 1 (The MVA - the definitive paper):
  • Scope: Present the full theory of pseudo-intent propagation through the CARVE synthesis tree. Provide the complete Canonical-ACARVE algorithm and an exhaustive empirical evaluation. The paper’s narrative will be “From a complete system to the minimal basis: the final step.”
  • Goal: To establish CARVE decomposition as the definitive state-of-the-art method for computing the canonical basis in structured contexts.
  • Target venue: Knowledge-Based Systems, as a direct sequel to the previous work.