From simplification to minimality: Computing the canonical basis of mixed implications

This paper moves beyond simplifying mixed implications to finding the true canonical basis. We define the ‘mixed pseudo-intents’ needed to establish minimality. The goal is a direct algorithm to compute this minimal basis, completing the theory for logical systems with bipolar information.

Keywords

Canonical basis, Mixed implications, Minimality, Simplification logic, Mixed pseudo-intents, Direct algorithm

Previous work on mixed implications (with positive and negative attributes) has focused on simplifying existing rule sets. While effective for reducing redundancy, this does not guarantee the computation of a basis with minimum cardinality, i.e., the canonical basis. This paper addresses the problem of finding such a minimal basis directly. We establish formal conditions for a simplified set of mixed implications to be minimal. Building on these conditions, we investigate direct algorithms for computing the mixed canonical basis without first generating a larger, redundant set. This work moves beyond post-processing and simplification towards a foundational theory of minimality for logical systems with bipolar information.

Introduction

Our previous work introduced a Simplification Logic for Mixed Attributes, providing algorithms to reduce the size of a given set of mixed implications. The resulting “m-simplified” set is more compact but not necessarily of minimal cardinality. The question of what constitutes a “canonical basis” in the mixed setting, and how to compute it directly, remains open.

This paper provides the answer. We aim to:

1. Define formal minimality conditions for a set of m-simplified implications.
2. Develop an algorithm to compute a basis satisfying these conditions directly, potentially by adapting canonical basis algorithms from classical FCA.

Methodology and expected theoretical results

Theoretical foundation

The Duquenne-Guigues basis in classical FCA is built on the notion of pseudo-intents. The core of this paper will be to define and characterize the “mixed pseudo-intents.” * Main theoretical result: We will define a mixed pseudo-intent and prove that the set of implications derived from all such pseudo-intents forms a correct, complete, and minimal basis for the mixed context. This characterization will have to respect the additional axioms of the mixed simplification logic (e.g., the key and reduction rules).

Algorithmic approach

Based on this characterization, we will develop an algorithm to enumerate all mixed pseudo-intents. This could be an adaptation of NextClosure or LinCbO, modified to operate on the mixed attribute set $M \cup \bar{M}$ and to incorporate checks related to the mixed logic.

Work plan

• Months 1-5: Develop the theory of mixed pseudo-intents and prove the canonical basis characterization.
• Months 6-9: Design and implement an algorithm (e.g., “Mixed-LinCbO”) for enumerating mixed pseudo-intents.
• Months 10-12: Write the manuscript.

Potential target journals

1. Information Sciences (Q1): A strong candidate for a paper that solves a fundamental problem in an extended FCA model.
2. Journal of Logic and Computation (Q2): An excellent fit for the paper’s focus on formal logic and its computational aspects.

Minimum viable article (MVA) strategy

• Paper 1 (The MVA):
  • Scope: The complete paper as described. The novelty lies in defining minimality for mixed bases and providing a direct algorithm.
  • Goal: To complete the theory of implication bases for the mixed FCA paradigm.
  • Target venue: Information Sciences.