introduction

basic building blocks

three kinds of entities :

  • concepts (set of individuals)(similar to unary predicates in First Order Logic)
  • roles (similar to binary relations between individuals)
  • individual names ( similar to constants )

It contains a set of statements, called Axioms. They describe partial knowldge of the world

ABox axioms

capture knowledge about named individuals using concept assertions (for example and role assertions

TBox axioms

describe relationship between concepts. Example :

RBox axioms

Express relations between roles.

  • Role inclusion
  • Role equivalence
  • role composition

constructors for concepts and roles

  • Boolean concept constructors
  • Role restrictions
  • Number restrictions
  • Local reflexivity

Attributive concept language with Complements

Complex Concepts where

Interpretation

= (domain set, interpretation function)

Concept satisfiability problem:

Input: A (complex) concept C in ALC. Question: Is there an interpretation such that ? This is PSPACE Complete.

  • It has finite interpretation property

Subsumption problem

PSPACE Complete

Knowledge base consistency problem

EXPTIME-complete