Linear Algebraic Abduction with Partial Evaluation
Tuan Nguyen Quoc, Katsumi Inoue, and Chiaki Sakama
Proceedings of the 25th International Symposium on Practical Aspects of Declarative Languages (PADL 2023), pages 197-215, 2023.
Abstract
Linear algebra is an ideal tool to redefine symbolic methods with the goal to achieve better scalability.
In solving the abductive Horn propositional problem, the transpose of a program matrix has been exploited to
develop an efficient exhaustive method. While it is competitive with other symbolic methods,
there is much room for improvement in practice. In this paper, we propose to optimize the linear algebraic method for
abduction using partial evaluation. This improvement considerably reduces the number of iterations in the main loop of
the previous algorithm. Therefore, it improves practical performance especially with sparse representation in case
there are multiple subgraphs of conjunctive conditions that can be computed in advance. The positive effect of partial
evaluation has been confirmed using artificial benchmarks and real FMEA-based datasets.
Full Paper (PDF 463K)
Slide