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

arXiv: https://arxiv.org/abs/2303.04534 · HTML: https://mlsanity.com/paper/2303.04534/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 37 references that are in the map.
- First posted on arXiv 8 Mar 2023.

## Builds on (most cited first, 6 of 6)

- [An ASP approach for reasoning in a concept-aware multipreferential lightweight DL](https://mlsanity.com/paper/2006.04387/) (2020)
- [Weighted defeasible knowledge bases and a multipreference semantics for a deep neural network model](https://mlsanity.com/paper/2012.13421/) (2020)
- [On the KLM properties of a fuzzy DL with Typicality](https://mlsanity.com/paper/2106.00390/) (2021)
- [Reasoning on Multi-Relational Contextual Hierarchies via Answer Set Programming with Algebraic Measures](https://mlsanity.com/paper/2108.03100/) (2021)
- [An ASP approach for reasoning on neural networks under a finitely many-valued semantics for weighted conditional knowledge bases](https://mlsanity.com/paper/2202.01123/) (2022)
- [Many-valued Argumentation, Conditionals and a Probabilistic Semantics for Gradual Argumentation](https://mlsanity.com/paper/2212.07523/) (2022)

## Built on by (most cited first, 2 of 2)

- [A preferential interpretation of MultiLayer Perceptrons in a conditional logic with typicality](https://mlsanity.com/paper/2305.00304/) (2023)
- [A framework for Conditional Reasoning in Answer Set Programming](https://mlsanity.com/paper/2506.03997/) (2025)

## Abstract (arXiv)

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 Pip2 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 PNP[log]-completeness result and new ASP encodings that deal with weighted knowledge bases with large search spaces.