Complexity and Scalability of Defeasible Reasoning with Typicality in Many-Valued Weighted Knowledge Bases

Mario Alviano; Laura Giordano; Daniele Theseider Dupré

doi:10.1007/978-3-031-43619-2_33

Complexity and Scalability of Defeasible Reasoning with Typicality in Many-Valued Weighted Knowledge Bases

Mario Alviano, Laura Giordano, Daniele Theseider Dupré

Dipartimento di Scienze e Innovazione Tecnologica

Risultato della ricerca: Capitolo in libro/report/atti di convegno › Contributo a conferenza › peer review

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 Π2p 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^N ^P ^[ ^l ^o ^g ^] -completeness result and new ASP encodings that deal with weighted knowledge bases with large search spaces.

Lingua originale	Inglese
Titolo della pubblicazione ospite	Logics in Artificial Intelligence - 18th European Conference, JELIA 2023, Proceedings
Editor	Sarah Gaggl, Maria Vanina Martinez, Magdalena Ortiz, Magdalena Ortiz
Editore	Springer Science and Business Media Deutschland GmbH
Pagine	481-497
Numero di pagine	17
ISBN (stampa)	9783031436185
DOI	https://doi.org/10.1007/978-3-031-43619-2_33
Stato di pubblicazione	Pubblicato - 2023
Evento	18th European Conference on Logics in Artificial Intelligence, JELIA 2023 - Dresden, Germany Durata: 20 set 2023 → 22 set 2023

Serie di pubblicazioni

Nome	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14281 LNAI
ISSN (stampa)	0302-9743
ISSN (elettronico)	1611-3349

???event.eventtypes.event.conference???

???event.eventtypes.event.conference???	18th European Conference on Logics in Artificial Intelligence, JELIA 2023
Paese/Territorio	Germany
Città	Dresden
Periodo	20/09/23 → 22/09/23

Accesso al documento

10.1007/978-3-031-43619-2_33

Altri file e collegamenti

Link to publication in Scopus

Cita questo

Alviano, M., Giordano, L., & Theseider Dupré, D. (2023). Complexity and Scalability of Defeasible Reasoning with Typicality in Many-Valued Weighted Knowledge Bases. In S. Gaggl, M. V. Martinez, M. Ortiz, & M. Ortiz (Edd.), Logics in Artificial Intelligence - 18th European Conference, JELIA 2023, Proceedings (pagg. 481-497). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14281 LNAI). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-43619-2_33

Alviano, Mario ; Giordano, Laura ; Theseider Dupré, Daniele. / Complexity and Scalability of Defeasible Reasoning with Typicality in Many-Valued Weighted Knowledge Bases. Logics in Artificial Intelligence - 18th European Conference, JELIA 2023, Proceedings. curatore / Sarah Gaggl ; Maria Vanina Martinez ; Magdalena Ortiz ; Magdalena Ortiz. Springer Science and Business Media Deutschland GmbH, 2023. pagg. 481-497 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c71e953a9c684894aafec129f2a6bdb2,

title = "Complexity and Scalability of Defeasible Reasoning with Typicality in Many-Valued Weighted Knowledge Bases",

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 Π2p 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 PN P [ l o g ] -completeness result and new ASP encodings that deal with weighted knowledge bases with large search spaces.",

keywords = "Answer Set Programming, Multi-valued Logics, Typicality Logics",

author = "Mario Alviano and Laura Giordano and \{Theseider Dupr{\'e}\}, Daniele",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.; 18th European Conference on Logics in Artificial Intelligence, JELIA 2023 ; Conference date: 20-09-2023 Through 22-09-2023",

year = "2023",

doi = "10.1007/978-3-031-43619-2\_33",

language = "English",

isbn = "9783031436185",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "481--497",

editor = "Sarah Gaggl and Martinez, \{Maria Vanina\} and Magdalena Ortiz and Magdalena Ortiz",

booktitle = "Logics in Artificial Intelligence - 18th European Conference, JELIA 2023, Proceedings",

address = "Germany",

}

Alviano, M, Giordano, L & Theseider Dupré, D 2023, Complexity and Scalability of Defeasible Reasoning with Typicality in Many-Valued Weighted Knowledge Bases. in S Gaggl, MV Martinez, M Ortiz & M Ortiz (edd.), Logics in Artificial Intelligence - 18th European Conference, JELIA 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14281 LNAI, Springer Science and Business Media Deutschland GmbH, pagg. 481-497, 18th European Conference on Logics in Artificial Intelligence, JELIA 2023, Dresden, Germany, 20/09/23. https://doi.org/10.1007/978-3-031-43619-2_33

Complexity and Scalability of Defeasible Reasoning with Typicality in Many-Valued Weighted Knowledge Bases. / Alviano, Mario; Giordano, Laura ; Theseider Dupré, Daniele.
Logics in Artificial Intelligence - 18th European Conference, JELIA 2023, Proceedings. a cura di / Sarah Gaggl; Maria Vanina Martinez; Magdalena Ortiz; Magdalena Ortiz. Springer Science and Business Media Deutschland GmbH, 2023. pag. 481-497 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14281 LNAI).

Risultato della ricerca: Capitolo in libro/report/atti di convegno › Contributo a conferenza › peer review

TY - GEN

T1 - Complexity and Scalability of Defeasible Reasoning with Typicality in Many-Valued Weighted Knowledge Bases

AU - Alviano, Mario

AU - Giordano, Laura

AU - Theseider Dupré, Daniele

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.

PY - 2023

Y1 - 2023

N2 - 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 Π2p 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 PN P [ l o g ] -completeness result and new ASP encodings that deal with weighted knowledge bases with large search spaces.

AB - 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 Π2p 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 PN P [ l o g ] -completeness result and new ASP encodings that deal with weighted knowledge bases with large search spaces.

KW - Answer Set Programming

KW - Multi-valued Logics

KW - Typicality Logics

UR - https://www.scopus.com/pages/publications/85174523991

U2 - 10.1007/978-3-031-43619-2_33

DO - 10.1007/978-3-031-43619-2_33

M3 - Conference contribution

AN - SCOPUS:85174523991

SN - 9783031436185

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 481

EP - 497

BT - Logics in Artificial Intelligence - 18th European Conference, JELIA 2023, Proceedings

A2 - Gaggl, Sarah

A2 - Martinez, Maria Vanina

A2 - Ortiz, Magdalena

PB - Springer Science and Business Media Deutschland GmbH

T2 - 18th European Conference on Logics in Artificial Intelligence, JELIA 2023

Y2 - 20 September 2023 through 22 September 2023

ER -

Alviano M, Giordano L , Theseider Dupré D. Complexity and Scalability of Defeasible Reasoning with Typicality in Many-Valued Weighted Knowledge Bases. In Gaggl S, Martinez MV, Ortiz M, Ortiz M, editor, Logics in Artificial Intelligence - 18th European Conference, JELIA 2023, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. pag. 481-497. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-43619-2_33