Complexity and scalability of defeasible reasoning in many-valued weighted knowledge bases with typicality
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.
Code (1)
Similar Papers 제목 키워드 기반
Many-valued Argumentation, Conditionals and a Probabilistic Semantics for Gradual Argumentation
In this paper we propose a general approach to define a many-valued preferential interpretation of gradual argumentation semantics. The approach allows for conditional reasoning over arguments and boolean combination of …
Temporal Many-valued Conditional Logics: a Preliminary Report
In this paper we propose a many-valued temporal conditional logic. We start from a many-valued logic with typicality, and extend it with the temporal operators of the Linear Time Temporal Logic (LTL), thus providing a fo…
Theoretical Foundations of Defeasible Description Logics
We extend description logics (DLs) with non-monotonic reasoning features. We start by investigating a notion of defeasible subsumption in the spirit of defeasible conditionals as studied by Kraus, Lehmann and Magidor in …
A preferential interpretation of MultiLayer Perceptrons in a conditional logic with typicality
In this paper we investigate the relationships between a multipreferential semantics for defeasible reasoning in knowledge representation and a multilayer neural network model. Weighted knowledge bases for a simple descr…
Defeasible Reasoning via Datalog$^\neg$
We address the problem of compiling defeasible theories to Datalog$^\neg$ programs. We prove the correctness of this compilation, for the defeasible logic $DL(\partial_{||})$, but the techniques we use apply to many othe…