Explainability via Short Formulas: the Case of Propositional Logic with Implementation

Reijo Jaakkola; Tomi Janhunen; Antti Kuusisto; Masood Feyzbakhsh Rankooh; Miikka Vilander

Explainability via Short Formulas: the Case of Propositional Logic with Implementation

Reijo Jaakkola, Tomi Janhunen, Antti Kuusisto, Masood Feyzbakhsh Rankooh, Miikka Vilander

Computing Sciences

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

2 Citations (Scopus)

10 Downloads (Pure)

Abstract

We conceptualize explainability in terms of logic and formula size, giving a number of related definitions of explainability in a very general setting. Our main interest is the so-called special explanation problem which aims to explain the truth value of an input formula in an input model. The explanation is a formula of minimal size that (1) agrees with the input formula on the input model and (2) transmits the involved truth value to the input formula globally, i.e., on every model. As an important example case, we study propositional logic in this setting and show that the special explainability problem is complete for the second level of the polynomial hierarchy. We also provide an implementation of this problem in answer set programming and investigate its capacity in relation to explaining answers to the n-queens and dominating set problems.

Original language	English
Title of host publication	Joint Proceedings of the 1st International Workshop on HYbrid Models for Coupling Deductive and Inductive ReAsoning HYDRA} 2022 and the 29th RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion RCRA 2022 co-located with the 16th International Conference on Logic Programming and Non-monotonic Reasoning LPNMR 2022, Genova Nervi, Italy, September 5, 2022
Publisher	CEUR Workshop Proceedings
Pages	64-77
Number of pages	13
Volume	3281
Publication status	Published - 5 Sept 2022
Publication type	A4 Article in conference proceedings
Event	RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion - , Italy Duration: 5 Sept 2022 → 5 Sept 2022

Publication series

Name	CEUR workshop proceedings
ISSN (Electronic)	1613-0073

Conference

Conference	RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion
Country/Territory	Italy
Period	5/09/22 → 5/09/22

Keywords

Explainability
Answer Set Programming
satisfiability checking
Computational complexity

Publication forum classification

Publication forum level 1

Access to Document

paper6-2Final published version, 333 KBLicence: CC BY

http://ceur-ws.org/Vol-3281/paper6.pdfLicence: CC BY
https://urn.fi/URN:NBN:fi:tuni-202308167623Licence: CC BY

Cite this

Jaakkola, R., Janhunen, T., Kuusisto, A., Feyzbakhsh Rankooh, M., & Vilander, M. (2022). Explainability via Short Formulas: the Case of Propositional Logic with Implementation. In Joint Proceedings of the 1st International Workshop on HYbrid Models for Coupling Deductive and Inductive ReAsoning HYDRA} 2022 and the 29th RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion RCRA 2022 co-located with the 16th International Conference on Logic Programming and Non-monotonic Reasoning LPNMR 2022, Genova Nervi, Italy, September 5, 2022 (Vol. 3281, pp. 64-77). ( CEUR workshop proceedings). CEUR Workshop Proceedings. http://ceur-ws.org/Vol-3281/paper6.pdf

Jaakkola, Reijo ; Janhunen, Tomi ; Kuusisto, Antti et al. / Explainability via Short Formulas: the Case of Propositional Logic with Implementation. Joint Proceedings of the 1st International Workshop on HYbrid Models for Coupling Deductive and Inductive ReAsoning HYDRA} 2022 and the 29th RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion RCRA 2022 co-located with the 16th International Conference on Logic Programming and Non-monotonic Reasoning LPNMR 2022, Genova Nervi, Italy, September 5, 2022. Vol. 3281 CEUR Workshop Proceedings, 2022. pp. 64-77 ( CEUR workshop proceedings).

@inproceedings{4a73683bb97f42329512666b2e786a45,

title = "Explainability via Short Formulas: the Case of Propositional Logic with Implementation",

abstract = "We conceptualize explainability in terms of logic and formula size, giving a number of related definitions of explainability in a very general setting. Our main interest is the so-called special explanation problem which aims to explain the truth value of an input formula in an input model. The explanation is a formula of minimal size that (1) agrees with the input formula on the input model and (2) transmits the involved truth value to the input formula globally, i.e., on every model. As an important example case, we study propositional logic in this setting and show that the special explainability problem is complete for the second level of the polynomial hierarchy. We also provide an implementation of this problem in answer set programming and investigate its capacity in relation to explaining answers to the n-queens and dominating set problems.",

keywords = "Explainability, Answer Set Programming, satisfiability checking, Computational complexity",

author = "Reijo Jaakkola and Tomi Janhunen and Antti Kuusisto and {Feyzbakhsh Rankooh}, Masood and Miikka Vilander",

year = "2022",

month = sep,

day = "5",

language = "English",

volume = "3281",

series = " CEUR workshop proceedings",

publisher = "CEUR Workshop Proceedings",

pages = "64--77",

booktitle = "Joint Proceedings of the 1st International Workshop on HYbrid Models for Coupling Deductive and Inductive ReAsoning HYDRA} 2022 and the 29th RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion RCRA 2022 co-located with the 16th International Conference on Logic Programming and Non-monotonic Reasoning LPNMR 2022, Genova Nervi, Italy, September 5, 2022",

note = "RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion ; Conference date: 05-09-2022 Through 05-09-2022",

}

Jaakkola, R , Janhunen, T , Kuusisto, A , Feyzbakhsh Rankooh, M & Vilander, M 2022, Explainability via Short Formulas: the Case of Propositional Logic with Implementation. in Joint Proceedings of the 1st International Workshop on HYbrid Models for Coupling Deductive and Inductive ReAsoning HYDRA} 2022 and the 29th RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion RCRA 2022 co-located with the 16th International Conference on Logic Programming and Non-monotonic Reasoning LPNMR 2022, Genova Nervi, Italy, September 5, 2022. vol. 3281, CEUR workshop proceedings, CEUR Workshop Proceedings, pp. 64-77, RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion, Italy, 5/09/22. <http://ceur-ws.org/Vol-3281/paper6.pdf>

Explainability via Short Formulas: the Case of Propositional Logic with Implementation. / Jaakkola, Reijo ; Janhunen, Tomi ; Kuusisto, Antti et al.
Joint Proceedings of the 1st International Workshop on HYbrid Models for Coupling Deductive and Inductive ReAsoning HYDRA} 2022 and the 29th RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion RCRA 2022 co-located with the 16th International Conference on Logic Programming and Non-monotonic Reasoning LPNMR 2022, Genova Nervi, Italy, September 5, 2022. Vol. 3281 CEUR Workshop Proceedings, 2022. p. 64-77 ( CEUR workshop proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Explainability via Short Formulas: the Case of Propositional Logic with Implementation

AU - Jaakkola, Reijo

AU - Janhunen, Tomi

AU - Kuusisto, Antti

AU - Feyzbakhsh Rankooh, Masood

AU - Vilander, Miikka

PY - 2022/9/5

Y1 - 2022/9/5

N2 - We conceptualize explainability in terms of logic and formula size, giving a number of related definitions of explainability in a very general setting. Our main interest is the so-called special explanation problem which aims to explain the truth value of an input formula in an input model. The explanation is a formula of minimal size that (1) agrees with the input formula on the input model and (2) transmits the involved truth value to the input formula globally, i.e., on every model. As an important example case, we study propositional logic in this setting and show that the special explainability problem is complete for the second level of the polynomial hierarchy. We also provide an implementation of this problem in answer set programming and investigate its capacity in relation to explaining answers to the n-queens and dominating set problems.

AB - We conceptualize explainability in terms of logic and formula size, giving a number of related definitions of explainability in a very general setting. Our main interest is the so-called special explanation problem which aims to explain the truth value of an input formula in an input model. The explanation is a formula of minimal size that (1) agrees with the input formula on the input model and (2) transmits the involved truth value to the input formula globally, i.e., on every model. As an important example case, we study propositional logic in this setting and show that the special explainability problem is complete for the second level of the polynomial hierarchy. We also provide an implementation of this problem in answer set programming and investigate its capacity in relation to explaining answers to the n-queens and dominating set problems.

KW - Explainability

KW - Answer Set Programming

KW - satisfiability checking

KW - Computational complexity

M3 - Conference contribution

VL - 3281

T3 - CEUR workshop proceedings

SP - 64

EP - 77

BT - Joint Proceedings of the 1st International Workshop on HYbrid Models for Coupling Deductive and Inductive ReAsoning HYDRA} 2022 and the 29th RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion RCRA 2022 co-located with the 16th International Conference on Logic Programming and Non-monotonic Reasoning LPNMR 2022, Genova Nervi, Italy, September 5, 2022

PB - CEUR Workshop Proceedings

T2 - RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion

Y2 - 5 September 2022 through 5 September 2022

ER -

Jaakkola R , Janhunen T , Kuusisto A , Feyzbakhsh Rankooh M , Vilander M. Explainability via Short Formulas: the Case of Propositional Logic with Implementation. In Joint Proceedings of the 1st International Workshop on HYbrid Models for Coupling Deductive and Inductive ReAsoning HYDRA} 2022 and the 29th RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion RCRA 2022 co-located with the 16th International Conference on Logic Programming and Non-monotonic Reasoning LPNMR 2022, Genova Nervi, Italy, September 5, 2022. Vol. 3281. CEUR Workshop Proceedings. 2022. p. 64-77. ( CEUR workshop proceedings).

Explainability via Short Formulas: the Case of Propositional Logic with Implementation

Abstract

Publication series

Conference

Keywords

Publication forum classification

Access to Document

Fingerprint

Cite this