Change: Restrictions for Simple Properties

created on March 12, 2013, 1:26 a.m. by Hevok & updated on March 12, 2013, 1:27 a.m. by Hevok

As the Problem of General Role Inclusion can be undecidable one need to restrict to regular RBoxes. One restricts to regular Languages by introduction a strict partial ordering on the names of the Properties that will be connected with the General Role Inclusion. Then only Rules according to these Schematas are allowed. In a regular RBox it is allowed to connect a Role with itself and the Role is the Subset of itself. On the other hand one can also state the inverse of a Role is subset of a Role which is also regular. If on both sites on the Subsumption sites are Roles which are not of the same type, then it is also no Problem if S is only an Atomic Role and R is involved.

The complicated cases are whenever R also occurs on the other Site of the Subsumption sign. There are only two cases allowed. The first case if when R is right at the Front or R is somewhere right at the end. It is not allowed to stay somewhere in the middle, only on the front or the end. More important all of the other Roles that are part of this Role Inclusion, for them it must hold that they are smaller than R according to the ordering. Then if an RBox complies to this Rules, the RBox is then regular, but only if such a strict ordering exists.

  • Can Property Inclusion be restricted in some way to stay decidable?
  • Rboxes are like Grammars for Context-Free Languages
  • Intersection of Context Free Languages is problematic
  • Therefore Restriction to Regular Languages!

Regular RBoxes Property names are ordered with < (strict partial Ordering). Each RBox Inclusion must be formed like: - R i R ⊑ R - R- ⊑ R - S1 o S2 o S3 o ... o Sn ⊑ R - R o S1 o S2 o S3 o ... o Sn ⊑ R - S1 o S2 o S3 o ... o Sn o R ⊑ R Where: Si < R for all i=1,2,...,n An RBox is called regular, if such an (strict) Ordering < exists.

Considering a simple example that is not regular although it looks simple. If hasParent is connected to hasHusband which is a subset of hasFather. So one would state that the husband of a Parent is a father. So there is no Role constitution at the same time on each other site. However given a second Rule in the Knowledge Base which says that hasFather is Subproperty of hasParent. The it becomes complicated as hasParent can be substituted by hasFather which causes a Problem.

This is not regular because regularity would enforce both. From the first rule it would deduce that hasParent is smaller than hasFather and from the second one it would deduce that hasFather is smaller than hasPerent. This is no strict ordering as in both the same order must be applied. Therefore this is not a regular RBox.

When ever one tries to use the General Rule Inclusion the Rules have to be obeyed. One can only use Roles in the Role Inclusions that obey this Regularity, otherwise it would be undecidbale and uncomputable.

  • Example

    hasParent o hasHusband ⊑ hasFather
    hasFather ⊑ hasParent
    
  • is not regular because Regularity would enforce both

hasParent < hasFather

and

hasFather < hasParent

which is impossible because < must be strict

Parliament_of_Owls.png

Categories: Concept

Comment: Updated entry

See entry | Admin

Comment on This Data Unit