研究知识库中计数查询的可能取值范围，发现其结构有规律可循。
Spectra of Cardinality Queries over Description Logic Knowledge Bases
- 针对原子计数查询，分析其在逻辑模型中的取值集合形态。
- 在ALCIF等逻辑体系下，取值集本质是自然数与无穷闭包的子集。
- 结果适用于推理优化，适合形式化验证与知识库理论研究者。
近期研究探讨了将计数查询与描述逻辑本体结合的应用。知识库模型中此类查询的答案为整数或∞，其谱是指所有模型下的答案集合。尽管一般情况下难以计算和操作该集合，本文识别出一类可有效表示谱的计数查询。聚焦于原子计数查询，我们确定了在ALCIF本体上谱的可能形状：本质上是ℕ ∪ {∞}中对加法封闭的子集。对于ALCIF的多数子逻辑，谱的形状更简单，表现为[ m, ∞ ]或其变体。为获得结果，我们改进了有限模型推理的构造方法，尤其依赖于ALCIF的霍恩片段的环反转技术。此外，我们研究了所提有效表示的数据复杂性，证明在若干设定下该任务为FP^NP[log]-完全。
原文摘要 · Abstract (English)
Recent works have explored the use of counting queries coupled with Description Logic ontologies. The answer to such a query in a model of a knowledge base is either an integer or $\infty$, and its spectrum is the set of its answers over all models. While it is unclear how to compute and manipulate such a set in general, we identify a class of counting queries whose spectra can be effectively represented. Focusing on atomic counting queries, we pinpoint the possible shapes of a spectrum over $\mathcal{ALCIF}$ ontologies: they are essentially the subsets of $\mathbb{N} \cup \{ \infty \}$ closed under addition. For most sublogics of $\mathcal{ALCIF}$, we show that possible spectra enjoy simpler shapes, being $[ m, \infty ]$ or variations thereof. To obtain our results, we refine constructions used for finite model reasoning and notably rely on a cycle-reversion technique for the Horn fragment of $\mathcal{ALCIF}$. We also study the data complexity of computing the proposed effective representation and establish the $\mathsf{FP}^{\mathsf{NP}[\log]}$-completeness of this task under several settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。