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

Title:
Complexity and scalability of defeasible reasoning in many-valued weighted knowledge bases with typicality
Authors:
Mario Alviano, Laura Giordano, Daniele Theseider Dupré
Contributors:
Alviano, Mario, Giordano, Laura, Theseider Dupre', Daniele
Source:
Journal of Logic and Computation. 34:1469-1499
Publication Status:
Preprint
Publisher Information:
Oxford University Press (OUP), 2024.
Publication Year:
2024
Subject Terms:
FOS: Computer and information sciences, typicality, I.2.4, Computer Science - Artificial Intelligence, many-valued logic, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, 68T27, Preferential logic, Artificial Intelligence (cs.AI), 0202 electrical engineering, electronic engineering, information engineering, answer set programming
Document Type:
Fachzeitschrift Article
Language:
English
ISSN:
1465-363X
0955-792X
DOI:
10.1093/logcom/exae038
DOI:
10.48550/arxiv.2303.04534
Access URL:
http://arxiv.org/abs/2303.04534
Rights:
CC BY NC ND
arXiv Non-Exclusive Distribution
Accession Number:
edsair.doi.dedup.....45a1aa8c6e1f2cfd0c76e3a03c5354d3
Database:
OpenAIRE

Weitere Informationen

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 $\varPi ^{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 fulfills the lack by providing a ${P^{NP[log]}}$-completeness result and new ASP encodings that deal with both acyclic and cyclic weighted knowledge bases with large search spaces, as assessed empirically on synthetic test cases. The encodings are used to empower a reasoner for computing solutions and answering queries, possibly interacting with ASP Chef for obtaining an interactive visualization.