Tuesday, September 28, 2004
On the Relative Expressiveness of Description Logics and Predicate Logics
On the Relative Expressiveness of Description Logics and Predicate Logics
"It is natural to view concept and role definitions in Description Logics as expressing monadic and dyadic predicates in Predicate Calculus. We show that the descriptions built using the constructors usually considered in the DL literature are characterized exactly as the predicates definable by formulas in ¨L3, the subset of First Order Predicate Calculus with monadic and dyadic predicates which allows only three variable symbols. In order to handle \number bounds", we allow numeric quantifiers, and for transitive closure of roles we use in nitary disjunction. Using previous results in the literature concerning languages with limited numbers of variables, we get as corollaries the existence of formulae of FOPC which cannot be expressed as descriptions. We also show that by omitting role composition, descriptions express exactly the formulae in ¨L2, which is known to be decidable."
"It is natural to view concept and role definitions in Description Logics as expressing monadic and dyadic predicates in Predicate Calculus. We show that the descriptions built using the constructors usually considered in the DL literature are characterized exactly as the predicates definable by formulas in ¨L3, the subset of First Order Predicate Calculus with monadic and dyadic predicates which allows only three variable symbols. In order to handle \number bounds", we allow numeric quantifiers, and for transitive closure of roles we use in nitary disjunction. Using previous results in the literature concerning languages with limited numbers of variables, we get as corollaries the existence of formulae of FOPC which cannot be expressed as descriptions. We also show that by omitting role composition, descriptions express exactly the formulae in ¨L2, which is known to be decidable."
0 Comments:
