Expressivity of General Property Inclusion

Created on March 12, 2013, 1:20 a.m. by Hevok & updated by Hevok on May 2, 2013, 5:33 p.m.

The General Role Inclusion extends the Description Logics. If one extends the Expressivity of Description Logics with new Functionality there is always the possibility that it might become undecidable.

When ever one defines R boxes this is similar to defining formal Languages.

For context free languages there exists cases that are not decidable and not computable, therefore one has to check this.

There are more simpler Languages than the Context free Languages, namely the regular Languages. regular Languages have much simpler and easier construction Rules. For them the problem of the Intersection of the Emptiness is decidable.

So one should consider only those kind of Property or General Role Inclusions that maintain the condition that they are if translated into a Formal Language that they are a Regular Language and not a Context free Language. So one has think about what are the restriction that one has to put on these expressions from Description Logics to maintain Regularity of the induced Grammar that defines a Language.

• With RBoxes formal Languages can be defined

Example Grammar for the (context free*) Language of the words ab, aabb, aaabbb, ..

  L ::= ab becomes Ra i Rb ⊑ L
  L ::= aLb becomes Ra i L Rb ⊑ L

• ∃L.T ≢ ⊥ (" ∃L.T necessarily non-empty") means: "There exists a chain Ra and Rb pertaining to the Language."
• ∃L1.∃L2- ≢ ⊥ for two Languages L1 and L2 means: "There exists a word pertaining to L1 and also to L2."

But from a Formal Language is known: *Emptiness of the Intersection of Context Free Languages is not decidable

OWL with general Property Inclusion is UNDECIDABLE!

Tags: problem, ontology, language, formal
Categories: Concept
Parent: General Role Inclusion

Update entry (Admin) | See changes

---

Back to top

---