Complexity and scalability of defeasible reasoning in many-valued weighted knowledge bases with typicality

2023/03/08 by Mario Alviano, Laura Giordano, Alviano, Mario +3 · 1 citation
Computer Science · #68T27 #Advanced Algebra and Logic #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #I.2.4 #Logic, Reasoning, and Knowledge #Multi-Agent Systems and Negotiation

paper · pdf · doi:10.48550/arxiv.2303.04534

openalex publication_date 2023/03/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 Π^p₂ 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.

Cited by

• A framework for Conditional Reasoning in Answer Set Programming

Related

• Weighted defeasible knowledge bases and a multipreference semantics for a deep neural network model
• Epistemic Logic Programs: Non-Ground and Counting Complexity
• An ASP approach for reasoning on neural networks under a finitely many-valued semantics for weighted conditional knowledge bases
• A preferential interpretation of MultiLayer Perceptrons in a conditional logic with typicality
• An ASP approach for reasoning in a concept-aware multipreferential\n lightweight DL