Weighted knowledge bases for description logics with typicality under a "concept-wise" multi-preferential semantics provide a logical interpretation of MultiLayer Perceptrons. In this context, Answer Set Programming (ASP) has been shown to be suitable for addressing defeasible reasoning in the finitely many-valued case, providing a $\Pi^p_2$ upper bound on the complexity of the problem, nonetheless leaving unknown the exact complexity and only providing a proof-of-concept implementation. This paper fulfils the lack by providing a $P^{NP[log]}$-completeness result and new ASP encodings that deal with weighted knowledge bases with large search spaces.
翻译：具有典型性的多值加权知识库中可撤销推理的复杂性和可扩展性
摘要：
本文研究具有典型性的多值加权知识库中的可撤销推理及其描述逻辑的“概念方式”多重优选语义。这种方法为多层感知机(MultiLayer Perceptrons)提供了逻辑解释。在这种情况下，已经证明了答案集编程(ASP)适用于解决有限多值情况下的可撤销推理问题，并提供了一个算法复杂度为$\Pi^p_2$的上界，尽管仅提供了概念验证实现。该文通过提供$P^{NP[log]}$完备性结果和新的ASP编码来解决大型搜索空间中的加权知识库。
相关内容
微信扫码咨询专知VIP会员