统一多种定性约束推理框架，高效判断组合系统是否可满足。
Deciding the Satisfiability of Combined Qualitative Constraint Networks
- 构建统一形式框架，整合多尺度、时序与松散组合的定性推理
- 证明满足性判定在特定条件下为多项式时间可解
- 扩展经典定义，涵盖更多实际应用中的定性形式
在人工智能的各类推理研究中，定性推理可在缺乏精确数值和完整信息的背景下推断新知识。本文提出一个形式化框架，统一多种定性形式的扩展与组合，包括多尺度推理、时间序列以及松散集成。该框架不仅支持对每种组合进行推理，还可统一研究其满足性判定及其复杂性。特别地，我们建立了两个互补定理，保证满足性判定在特定条件下为多项式时间可解，并用其重新获得已知的大小-拓扑组合结果。同时，我们推广了定性形式的基本定义，包含文献定义中被排除但组合场景中重要的形式。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。