Encoding the satisfiability of modal and description logic into SAT: the case study of K(m)/ALC

In the last two decades, modal and description logics have been applied to numerous areas of computer science, including artificial intelligence, formal verification, database theory, and distributed computing. For this reason, the problem of automated reasoning in modal and description logics has been throughly investigated. In particular, many approaches have been proposed for efficiently handling the satisfiability of the core normal modal logic K m, and of its notational variant, the description logic ALC. Although simple in structure, Km/script A signℒC is computationally very hard to reason on, its satisfiability being PSPACE-complete. In this paper we explore the idea of encoding Km/script A signℒC-satisfiability into SAT, so that to be handled by state-of-the-art SAT tools. We propose an efficient encoding, and we test it on an extensive set of benchmarks, comparing the approach with the main state-of-the-art tools available. Although the encoding is necessarily worst-case expo...