Deciding the Satisfiability of Combined Qualitative Constraint Networks
This work addresses the challenge of reasoning with imprecise, incomplete information in AI, providing a unified approach for combinations like multi-scale reasoning and temporal sequences, but it is incremental as it builds on existing qualitative formalisms.
The paper tackles the problem of deciding satisfiability for combined qualitative constraint networks by proposing a formal framework that unifies various extensions and combinations, establishing polynomial-time satisfiability theorems and recovering known results for size-topology combinations.
Among the various forms of reasoning studied in the context of artificial intelligence, qualitative reasoning makes it possible to infer new knowledge in the context of imprecise, incomplete information without numerical values. In this paper, we propose a formal framework unifying several forms of extensions and combinations of qualitative formalisms, including multi-scale reasoning, temporal sequences, and loose integrations. This framework makes it possible to reason in the context of each of these combinations and extensions, but also to study in a unified way the satisfiability decision and its complexity. In particular, we establish two complementary theorems guaranteeing that the satisfiability decision is polynomial, and we use them to recover the known results of the size-topology combination. We also generalize the main definition of qualitative formalism to include qualitative formalisms excluded from the definitions of the literature, important in the context of combinations.