KR Conference 2012 Conference Paper
- Stefan Borgwardt
- Rafael Peñaloza
Armengol, and Esteva 2010) for a survey). In fact, fuzzy DLs have several degrees of freedom for defining their expressiveness. In addition to the choice of concept constructors (such as conjunction u or existential restriction ∃), and the type of axioms allowed (like acyclic concept definitions or general concept inclusions), one must also decide how to interpret the different constructors, through a choice of functions over the domain of fuzzy values [0, 1]. These functions are typically determined by a continuous t-norm (like Gödel, Łukasiewicz, or product) that interprets conjunction; there exist uncountably many such t-norms, each with different properties. For example, under the product t-norm semantics, existential- (∃) and value-restrictions (∀) are not interdefinable, while under the Łukasiewicz t-norm they are. Even after fixing the t-norm, one can choose whether to interpret negation by the involutive negation operator, or using the residual negation. An additional level of liberty comes from selecting the class of models over which reasoning is considered: either all models, or so-called witnessed models only (Hájek 2005). Most existing reasoning algorithms have been developed for the Gödel semantics, either by a reduction to crisp reasoning (Straccia 2001; Bobillo et al. 2009), or by a simple adaptation of the known algorithms for crisp DLs (Stoilos et al. 2005; 2006; Tresp and Molitor 1998). However, methods based on other t-norms have also been explored (Bobillo and Straccia 2007; 2008; 2009; Straccia and Bobillo 2007; Stoilos and Stamou 2009). Usually, these algorithms reason w. r. t. witnessed models. 3 Very recently, it was shown that the tableaux-based algorithms for logics with semantics based on t-norms other than the Gödel t-norm and allowing general concept inclusions were incorrect (Baader and Peñaloza 2011a; Bobillo, Bou, and Straccia 2011). This raised doubts about the decidability of these logics, and eventually led to a series of undecidability results for fuzzy DLs (Baader and Peñaloza 2011a; 2011b; 2011c; Cerami and Straccia 2011). All these papers, except (Baader and Peñaloza 2011c), focus on one specific fuzzy DL; that is, undecidability is proven for a specific set of constructors, axioms, and underlying semantics. A small generalization is made in (Baader and Peñaloza Fuzzy description logics (DLs) have been investigated for over two decades, due to their capacity to formalize and reason with imprecise concepts. Very recently, it has been shown that for several fuzzy DLs, reasoning becomes undecidable. Although the proofs of these results differ in the details of each specific logic considered, they are all based on the same basic idea. In this paper, we formalize this idea and provide sufficient conditions for proving undecidability of a fuzzy DL. We demonstrate the effectiveness of our approach by strengthening all previously-known undecidability results and providing new ones. In particular, we show that undecidability may arise even if only crisp axioms are considered.