ALC(ID:5616/alc002)

Language substrate for KL-ONE (and KL-TWO?) developed later than the original language

Related languages
KL-ONE => ALC   Subsystem
References:
  • Schmidt-Schauss, M., Smolka, G. Attributive Concept Descriptions with Unions and Complements. SEKI report SR-88-21, FB Informatik, Universit~t Kaiserslautern, Germany, 1988. view details
  • Tammet,Tanel "Using resolution for extending KL-ONE-type languages" view details Extract: Introduction
    Introduction

    We argue that the basic characteristic of deductive database languages (like DATALOG) and knowledge-representation languages (eg KL-ONE) is decidabfity. I.e, any query must terminate and give either a negative or a positive answer. This is in sharp contr=t to using fulf first-order logic or non-decidable sublanguages like Horn clauses (the basis of PROLOG), where nonsucceasfttl queries do not, as a rule, terminate.

    We consider certain decision methods developed in the context of automated theorem proving and show how these methods can be put to immediate use as an efficient inference engine (with the property that every query terminates). Some classes of predicate logic are suggested as languages for knowledge-representation systems. In particular, the ALC language used by KL-ONE systems is just a sublanguage of one the suggested classes. The no-circularities restriction of ALC is removed.

    One of the advantages of the considered decision methods is their efficiency, clearly demonstrated in experiments (see [FLTZ 93]). The principal reason for this is that those methods are just further restrictions of a resolution method, which has been a preferred method for first-order theorem proving since its introduction. Roughly speaking, the decision methods at hand inherit the efficiency of resolution and then extend it further to the point of making a search space finite for decidable classes.

    Another advantage of using resolution-based decision procedures is their usabifity for completing a database, i.e. deriving a finite set of inferred clauses D’ from a database D such that when asking queries or adding new clauses to D in the future, no inferences from D or D’ alone have to be considered. We could say that a dynamic use of D is replaced by the static clause set D’. Extract: Introduction
    The language called ALC which has been introduced in [Schrnidt-Schauss, Smolka 88] can be considered as a basic language for KL-ONE systems, on which different extensions can be built. In [Schmidt-Schauss, Smolka 88] it is shown that satisfiability and KL-ONE-subsumption in ALC are PSPACE-complete.

    ALC contains two kinds of predicates - concepts (unary predicates) and roles (bhary predicates). ALC is meant for writing sets of concept definitions, Any formula in ALC has one of the following forms (we give a form in ALC and a well-known translation into predicate logic):

    • TRUE - top concept in subsumption hierarchy.
      Translation: constant truth value true.
    • FALSE - bottom concept in subsumption hierarchy.
      Translation: constant truth value false.
    • F, where F is an arbitrary concept.
      Translation: F(z), where z is defined by the context.
    • (not F), where F is an arbitrary ALC-formula.
      Translation: TJ, where F’ is the translation of F.
    • (and F G), where F and G are arbitrary ALC formulss.
      Translation: (F’ & G’), where F’ and G’ are translations of F and G.
    • (or F G), where F and G are arbitrary ALCformulas
      Translation: (F’ V G’), analogously to conjunction.
    • (all R F), where R is a role, and F is an arbitrary ALC-formula.
      Translation: (Vy)(R(z, y) s F’[y]), where the free variable s is determined by the context. F’[y] cannot contain any free variables except Y.
    • (exists R F), where R is a role, and F is an arbitrary ALC-formula. Translation: (3y)(R(z, y) & F’[y]), where the free variable z is determined by the context and F’[y] cannot contain any free variables except y.

    The concept definition in ALC has the following form:

    • P = F, where F is an arbitrary ALC-formula.
      Translation; (vZ)(P(z) * F’[z]).


    An important additional restriction to the described language is that no circularities are allowed in concept definitions  - that is, there must be a certain hierarchy of concepts such that all concepts in the right side of any concept definition are lower on the hierarchy than the defined concept. For example, it is not allowed to define a human as an animal whose mother is human: human = (and animal (exists mother human) ), since this definition contains a circularity.


          in Proceedings of the fourth international conference on Information and knowledge management December 1995 view details