Introduction
In the field of Artificial Intelligence, belief merging is a well-established process: it involves taking multiple, potentially conflicting sources of information and synthesizing them into a single, coherent knowledge base. This paper introduces the concept of knowledge distribution, effectively the "reverse engineering" of belief merging. The central question is whether a complex, arbitrary knowledge base $K$ can be decomposed into a set of simpler components—drawn from restricted logic fragments like Horn or 2CNF—such that a standard merging operator can perfectly reconstruct the original information.
This research is driven by three primary motivations. First, it addresses limited expressivity in scenarios where data must be stored across legacy systems or simple sensors that only handle restricted logic. Second, it explores information hiding, where distribution acts as a form of encryption; the original knowledge can only be reconstructed if the specific merging operator (the "key") is known. Finally, it probes the theoretical limits of merging operators, helping researchers understand whether an operator adds information during the merge or acts merely as a filter.
Methodology and Framework
The authors employ a formal framework grounded in propositional logic fragments and IC-merging operators. They focus on three specific fragments:
- 1CNF: Conjunctions of literals.
- 2CNF: Clauses containing at most two literals.
- Horn: Clauses with at most one positive literal.
These fragments are computationally simpler than general logic. To evaluate merging, the authors analyze operators based on two distance metrics between "possible worlds": Drastic Distance (a binary match/no-match metric) and Hamming Distance (counting differing facts). These distances are then aggregated using functions such as summation ($\Sigma$), GMax, or GMin to identify the optimal merged result.
The core of the study involves mathematical proofs to determine if a knowledge base $K$ is distributable (splittable into multiple simple bases) or simplifiable (representable by one simple base plus a constraint).
Key Insights
The research yields several significant findings regarding the expressive power of different fragments and operators:
- Drastic Distance as a Universal Distributor: The authors demonstrate that merging operators based on drastic distance allow any knowledge base to be distributed across almost any fragment. While highly flexible, this makes it less suitable for information hiding due to its simplicity.
- The 1CNF Bottleneck: 1CNF is the most restrictive fragment. Under standard Hamming distance with summation ($\Sigma$), a knowledge base can only be distributed into 1CNF if it was already simple enough to be expressed in 1CNF. Hamming/Sum merging does not provide additional expressive power in this context.
- The Power of 2CNF: In contrast, 2CNF proves surprisingly robust. Every knowledge base can be simplified into the 2CNF fragment using Hamming distance, provided a few auxiliary variables (atoms) are added. This allows a 2CNF base to emulate much more complex theories.
- The Horn Middle Ground: The Horn fragment occupies a middle position; while some complex bases can be distributed into Horn profiles, they cannot all be simplified into a single Horn base.
Summary of Results
The following table summarizes the distributability and simplifiability of various logic fragments under different merging operators.
As shown, Drastic Distance ($D$) consistently allows for distribution across all tested fragments. Hamming Distance ($H, \Sigma$) is effective for 2CNF but fails for 1CNF distribution in non-trivial cases. Notably, 2CNF is powerful enough to simplify any arbitrary base under Hamming distance.
Limitations and Future Directions
While the paper establishes the existence of these distributions, several areas remain for future exploration. The computational complexity of finding these distributions algorithmically is not deeply investigated. Additionally, the required size of a profile—the number of bases needed for distribution—remains an open question. The study is also limited to classical propositional logic; extending these concepts to non-monotonic reasoning or logic programs could provide further insights. Finally, the reliance on adding new atoms for 2CNF simplification may not be feasible in all real-world applications.
Summary updated