Tractable concept languages.

*(English)*Zbl 0742.68066
Artificial intelligence, IJCAI-91, Proc. 12th Int. Conf., Sydney/Australia 1991, 458-463 (1991).

[For the entire collection see Zbl 0741.68016.]

The goal of the present paper is the design of concept languages including the most powerful set of constructs, while retaining the tractability of subsumption, in particular extending the basic polynomial language \(FL^ -\) [R. J. Brachman and H. J. Levesque, The tractability of subsumption in frame-based description languages, Proc. of the Fourth Nat. Conf. on Artif. Intell., Austin/Texas, 34-37 (1984)]. In the specific literature there are considered the following constructs incorporated within the concept languages:

(1) the empty concept and the universal concept;

(2) disjunction of concepts;

(3) negation of concepts (or complement);

(4) qualified existential role quantification;

(5) number restrictions;

(6) role conjunction;

(7) inverse of roles;

(8) role chainging.

The language \(FL^ -\) includes conjunction of concepts, universal role quantification, and unqualitified existential role quantification. The paper defines two new extensions of \(FL^ -\), called \(PL_ 1\) and \(PF_ 2\), which are maximally expressive in the sense that no construct can be added to them without losing the tractability (polynomial time complexity) of subsumption. More precise, \(PL_ 1\) extends \(FL^ -\) with the constructs (5), (3), and (7), therefore is maximally expressive to the constructs available for concepts, while \(PL_ 2\) extends \(FL^ -\) with the constructs (6), (8), and (7), thus is maximally expressive concerning the roles. Another result is that both \(PL_ 1\) and \(PL_ 2\) can be extended with functional roles, the functional role value map, and the disjunction of primitive concepts, without endangering the tractability of subsumption. The algorithms for checking subsumption in \(PL_ 1\) and \(PL_ 2\) have been designed by exploiting a general technique for satisfiability checking in concept languages. These results allow to derive lower bounds for the complexity of almost all mentioned constructs in concept languages.

The goal of the present paper is the design of concept languages including the most powerful set of constructs, while retaining the tractability of subsumption, in particular extending the basic polynomial language \(FL^ -\) [R. J. Brachman and H. J. Levesque, The tractability of subsumption in frame-based description languages, Proc. of the Fourth Nat. Conf. on Artif. Intell., Austin/Texas, 34-37 (1984)]. In the specific literature there are considered the following constructs incorporated within the concept languages:

(1) the empty concept and the universal concept;

(2) disjunction of concepts;

(3) negation of concepts (or complement);

(4) qualified existential role quantification;

(5) number restrictions;

(6) role conjunction;

(7) inverse of roles;

(8) role chainging.

The language \(FL^ -\) includes conjunction of concepts, universal role quantification, and unqualitified existential role quantification. The paper defines two new extensions of \(FL^ -\), called \(PL_ 1\) and \(PF_ 2\), which are maximally expressive in the sense that no construct can be added to them without losing the tractability (polynomial time complexity) of subsumption. More precise, \(PL_ 1\) extends \(FL^ -\) with the constructs (5), (3), and (7), therefore is maximally expressive to the constructs available for concepts, while \(PL_ 2\) extends \(FL^ -\) with the constructs (6), (8), and (7), thus is maximally expressive concerning the roles. Another result is that both \(PL_ 1\) and \(PL_ 2\) can be extended with functional roles, the functional role value map, and the disjunction of primitive concepts, without endangering the tractability of subsumption. The algorithms for checking subsumption in \(PL_ 1\) and \(PL_ 2\) have been designed by exploiting a general technique for satisfiability checking in concept languages. These results allow to derive lower bounds for the complexity of almost all mentioned constructs in concept languages.

Reviewer: N.Curteanu (Iaşi)