Binary Absorption in Tableaux-Based Reasoning for Description Logics.
Alexander K. Hudek, Grant Weddell · Description Logics · 2006
A fundamental problem in Description Logics (DLs) is satisfiability, the problem of checking if a given DL terminology T remains sufficiently unconstrained to enable at least one instance of a given DL concept C to exist. It has been known for some time that lazy unfolding is an important optimization technique in model building algorithms for satisfiability [2]. It is also imperative for large terminologies to be manipulated by an absorption generation process to maximize the benefits of lazy unfolding in such algorithms, thereby reducing the combinatorial effects of disjunction in underlying chase procedures [5]. In this paper, we propose a generalization of the absorption theory and algorithms developed by Horrocks and Tobies [6, 7]. The generalization, called binary absorption, makes it possible for lazy unfolding to be used for parts of terminologies not handled by current absorption algorithms and theory. The basic idea of binary absorption is to avoid the need to internalize (at least some of the) terminological axioms of the form